New Game Plus!
题意翻译
【题目大意】
你有 $n$ 个数 $c_{1 \cdots n}$ 和 $1$ 个初始为 $0$ 的计数器 `boss bonus`。
你可以任意选择一个**尚未被选择过的** $c_{i}$,把 `boss bonus` 加上 $c_{i}$。
你也有 $k$ 次机会把 `boss bonus` 变成 $0$。
每次**选择数字前的 `boss bonus` 的和**记为你的收获。求收获的最大值。
$1 \leq n \leq 5 \times 10^5,0 \leq k \leq 5 \times 10^5,-1 \times 10^6 \leq c_{i} \leq 1 \times 10^6$。
**注意 $c_{i}$ 和最后的收获可以为负数。**
【输入输出】
输入的第 $1$ 行两个整数,分别是 $n,k$。
输入的第 $2$ 行 $n$ 个整数,表示 $c_{1 \cdots n}$。
输出 $1$ 行,最大收获。
The translation provider is @HPXXZYY.
题目描述
Wabbit is playing a game with $ n $ bosses numbered from $ 1 $ to $ n $ . The bosses can be fought in any order. Each boss needs to be defeated exactly once. There is a parameter called boss bonus which is initially $ 0 $ .
When the $ i $ -th boss is defeated, the current boss bonus is added to Wabbit's score, and then the value of the boss bonus increases by the point increment $ c_i $ . Note that $ c_i $ can be negative, which means that other bosses now give fewer points.
However, Wabbit has found a glitch in the game. At any point in time, he can reset the playthrough and start a New Game Plus playthrough. This will set the current boss bonus to $ 0 $ , while all defeated bosses remain defeated. The current score is also saved and does not reset to zero after this operation. This glitch can be used at most $ k $ times. He can reset after defeating any number of bosses (including before or after defeating all of them), and he also can reset the game several times in a row without defeating any boss.
Help Wabbit determine the maximum score he can obtain if he has to defeat all $ n $ bosses.
输入输出格式
输入格式
The first line of input contains two spaced integers $ n $ and $ k $ ( $ 1 \leq n \leq 5 \cdot 10^5 $ , $ 0 \leq k \leq 5 \cdot 10^5 $ ), representing the number of bosses and the number of resets allowed.
The next line of input contains $ n $ spaced integers $ c_1,c_2,\ldots,c_n $ ( $ -10^6 \leq c_i \leq 10^6 $ ), the point increments of the $ n $ bosses.
输出格式
Output a single integer, the maximum score Wabbit can obtain by defeating all $ n $ bosses (this value may be negative).
输入输出样例
输入样例 #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
说明
In the first test case, no resets are allowed. An optimal sequence of fights would be
- Fight the first boss $ (+0) $ . Boss bonus becomes equal to $ 1 $ .
- Fight the second boss $ (+1) $ . Boss bonus becomes equal to $ 2 $ .
- Fight the third boss $ (+2) $ . Boss bonus becomes equal to $ 3 $ .
Thus the answer for the first test case is $ 0+1+2=3 $ .
In the second test case, it can be shown that one possible optimal sequence of fights is
- Fight the fifth boss $ (+0) $ . Boss bonus becomes equal to $ 5 $ .
- Fight the first boss $ (+5) $ . Boss bonus becomes equal to $ 4 $ .
- Fight the second boss $ (+4) $ . Boss bonus becomes equal to $ 2 $ .
- Fight the third boss $ (+2) $ . Boss bonus becomes equal to $ -1 $ .
- Reset. Boss bonus becomes equal to $ 0 $ .
- Fight the fourth boss $ (+0) $ . Boss bonus becomes equal to $ -4 $ .
Hence the answer for the second test case is $ 0+5+4+2+0=11 $ .