← 返回题目列表

Codeforces · 1415/E

E. 新游戏加!

中文机器翻译题面 查看原题

Wabbit 正在与 $$$n$$$ 老板玩游戏,老板编号从 $$$1$$$ 到 $$$n$$$。 Boss 可以按任意顺序进行战斗。每个 Boss 都需要被击败一次。有一个参数叫做老板奖金,最初是$$$0$$$。

当第$$$i$$$个boss被击败时,当前boss奖励会添加到Wabbit的分数中,然后boss奖励的值会增加点增量$$$c_i$$$。请注意,$$$c_i$$$ 可以为负数,这意味着其他老板现在给出的分数更少。

然而,Wabbit 在游戏中发现了一个故障。在任何时间点,他都可以重置游戏流程并开始“新游戏+”游戏流程。这会将当前的 Boss 奖励设置为 $$$0$$$,而所有被击败的 Boss 仍然被击败。当前分数也会被保存,并且在此操作后不会重置为零。此故障最多可使用 $$$k$$$ 次。他可以在击败任意数量的 Boss 后(包括击败所有 Boss 之前或之后)重置游戏,也可以在不击败任何 Boss 的情况下连续多次重置游戏。

帮助 Wabbit 确定如果他必须击败所有 $$$n$$$ 头目,他可以获得的最高分数。

输入

输入的第一行包含两个空格整数$$$n$$$和$$$k$$$($$$1 \leq n \leq 5 \cdot 10^5$$$, $$$0 \leq k \leq 5 \cdot 10^5$$$),代表Boss的数量和允许的重置次数。

输入的下一行包含 $$$n$$$ 间隔整数 $$$c_1,c_2,\ldots,c_n$$$ ($$$-10^6 \leq c_i \leq 10^6$$$),$$$n$$$ 老板的点增量。

输出

输出单个整数,Wabbit击败所有$$$n$$$个boss可以获得的最大分数(该值可能为负数)。

示例

输入 #1

3 0
1 1 1

输出 #1

3

输入 #2

5 1
-1 -2 -3 -4 5

输出 #2

11

输入 #3

13 2
3 1 4 1 5 -9 -2 -6 -5 -3 -5 -8 -9

输出 #3

71

注意

在第一个测试用例中,不允许重置。最佳的战斗顺序是

- 与第一个boss战斗$$$(+0)$$$。老板奖金等于 $$$1$$$。
- 与第二个 boss $$$(+1)$$$ 战斗。老板奖金等于 $$$2$$$。
- 与第三个 boss $$$(+2)$$$ 战斗。老板奖金等于 $$$3$$$。

因此第一个测试用例的答案是 $$$0+1+2=3$$$。

在第二个测试用例中,可以证明一种可能的最佳战斗序列是

- 与第五个 boss $$$(+0)$$$ 战斗。老板奖金等于 $$$5$$$。
- 与第一个 Boss $$$(+5)$$$ 战斗。老板奖金等于 $$$4$$$。
- 与第二个 boss $$$(+4)$$$ 战斗。老板奖金等于 $$$2$$$。
- 与第三个 boss $$$(+2)$$$ 战斗。老板奖金变为$$$-1$$$。
- 重置。老板奖金变为$$$0$$$。
- 与第四个 boss $$$(+0)$$$ 战斗。老板奖金变为$$$-4$$$。

因此第二个测试用例的答案是$$$0+5+4+2+0=11$$$。