CF1415E New Game Plus!

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.

N/A

N/A

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 $ .