#A. [CZOJ 一周一测 R2 A] 美食诱惑 I

    传统题 1000ms 256MiB

[CZOJ 一周一测 R2 A] 美食诱惑 I

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

美食一窝,诱惑你我。

题目背景

邹锦舒特别喜欢吃垃圾食品,如可乐,冰淇淋,肯德基等。而这些东西一吃多,渐渐会在他的脑子里形成一个固定的快乐值。

我们知道,对于一瓶养乐多和一块巧克力来说,如果你先喝养乐多,再吃巧克力的话,会感觉养乐多是甜的,巧克力也是甜的。但如果先吃巧克力,再喝养乐多的话,会感觉巧克力是很甜,但养乐多是酸的。

这一天,陈煜轩来邹锦舒家里 蹭吃蹭喝 吃饭了。

题目描述

邹锦舒给了陈煜轩 nn 种食品,第 ii 样东西吃下去的快乐值为 ii。当然,正如题目背景的第二段所说,如果先吃一个快乐值为 ii 的食品,再吃一个快乐值为 jj 的食品(i>ji>j),先会得到 ii 的快乐值,然后就会得到 iji-j 的痛苦值。(如果iji \leq j,得到快乐值 jij-i

当然了,痛苦值和快乐值是可以抵消的。xx 点痛苦值可以与 xx 点快乐值抵消。

现在摆在陈煜轩面前有各种各样的美食,陈煜轩想吃。但是,讨厌的邹锦舒会在陈煜轩每一次吃完以后抢走当前所有食品中快乐值最大的。因此,陈煜轩决定每次要吃掉快乐值最大的那个。

陈煜轩请你帮他算算:他能得到的最大快乐值是多少?

输入格式

一行,一个整数 nn,表示有 nn 种食品。第 ii 种食品的快乐值为 ii

输出格式

一行,一个整数 xx,表示陈煜轩能得到的最大快乐值。

4
2

样例解释

现在有 44 种食品快乐值为 1,2,3,41,2,3,4

第一步,陈煜轩先把快乐值为 44 的食品拿走。此时他的快乐值为 44。然后邹锦舒拿走快乐值为 33 的食品。

第二步,陈煜轩先把快乐值为 22 的食品拿走。此时他得到了 42=24-2=2 点痛苦值。他的快乐值为 42=24-2=2。然后邹锦舒拿走快乐值为 11 的食品。

最后陈煜轩的快乐值为 22

注:操作方式不一定相同,但无法得到比 22 更大的快乐值。

数据范围

对于 70%70\% 的数据,n108n\le 10^8

对于 100%100\% 的数据,n1018n\le 10^{18}

[CZR-002] CZOJ Weekly Exercise Round 2

未参加
状态
已结束
规则
IOI
题目
6
开始于
2023-7-14 17:00
结束于
2023-7-14 22:00
持续时间
5 小时
主持人
参赛人数
30