该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

T2 菜地补水

时间限制：1 s　　内存限制：128 MB

题目描述

小 B 有一排 $n$ 块菜地，从左到右依次编号为 $1,2,\dots,n$。第 $i$ 块菜地当前水量与适宜水量相差 $a_i$：若 $a_i>0$，表示还缺 $a_i$ 单位水；若 $a_i<0$，表示多出 $|a_i|$ 单位水。

菜地最右端（第 $n$ 块）旁装有一台喷灌机。每次使用时，小 B 需要选择：

• 一个功率等级 $L$（$1\le L\le n$）；
• 一种模式：补水 或 抽水。

其效果为：

• 补水模式：第 $n$ 块补 $L$ 单位，第 $n-1$ 块补 $L-1$ 单位，第 $n-2$ 块补 $L-2$ 单位，……，第 $n-L+1$ 块补 $1$ 单位；第 $1$ 到 $n-L$ 块不受影响。
• 抽水模式：与补水模式影响的田块和数量完全相同，只是把相应的水抽走。

也就是说，当功率等级为 $L$ 时，离喷灌机越近的菜地受影响越大，距离每远一块，影响就减少 $1$ 单位，直到不再受影响。

请你计算：最少需要使用喷灌机多少次，才能使所有菜地的水量都恰好达到适宜水量（即每块菜地的偏差都变为 $0$）。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$，相邻整数之间用空格分隔，表示每块菜地的水量偏差。

输出格式

输出一行一个整数，表示最少需要使用的次数。

样例 1

输入

2
-1 3

输出

6

解释

对第 2 块菜地（也就是喷灌机所在位置）使用抽水模式、功率等级 $1$，共执行 $5$ 次：每次给第 $2$ 块抽走 $1$ 单位，使 $a_2$ 由 $3$ 变为 $-2$。

再使用补水模式、功率等级 $2$，执行 $1$ 次：第 $2$ 块补 $2$ 单位，第 $1$ 块补 $1$ 单位。

此时两块菜地的偏差分别为 $-1+1=0$、$-2+2=0$，共使用 $6$ 次。

样例 2

输入

5
1 3 -2 -7 5

输出

26

数据范围与提示

对于 $100\%$ 的数据：

• $1\le n\le 2\times 10^5$；
• $-10^{15}\le a_i\le 10^{15}$；
• 保证答案不超过 $10^9$。

提示：涉及的整数可能超过 32 位，请使用 64 位整数（例如 C/C++ 中的 long long）存储。

T3 集训分组

时间限制：1 s　　内存限制：128 MB

题目描述

集训队里有 $n$ 名学员排成一排，从左到右依次编号为 $1,2,\dots,n$。第 $i$ 名学员的能力值为 $s_i$。

教练打算把学员分成若干个连续的小组进行合作训练。每个小组可以包含不超过 $K$ 名学员，且每名学员恰属于一个小组。

由于同组学员会互相交流，训练结束后，小组内每名学员的能力值都会变成该小组中最高的能力值。

请你帮助教练安排分组方案，使得训练结束后所有学员能力值之和最大。

输入格式

第一行两个整数 $n,K$，相邻整数之间用空格分隔。

第二行 $n$ 个整数 $s_1,s_2,\dots,s_n$，表示每名学员的能力值。

输出格式

输出一行一个整数，表示所有学员能力值之和的最大可能值。

样例 1

输入

7 3
1 15 7 9 2 5 10

输出

84

解释

最优分组为：$\{1,2,3\}$、$\{4\}$、$\{5,6,7\}$。

• 第一组最高能力值为 $15$，组内 3 人能力值均变为 $15$；
• 第二组仅学员 4，能力值保持 $9$；
• 第三组最高能力值为 $10$，组内 3 人能力值均变为 $10$。

总和为 $15\times3+9+10\times3=45+9+30=84$。注意每个小组的人数可以小于 $K$。

样例 2

输入

3 5
4 4 4

输出

12

数据范围与提示

对于 $100\%$ 的数据：

• $1\le n\le 10^4$；
• $1\le K\le 10^3$；
• $1\le s_i\le 10^5$。

提示：答案可能超过 32 位整数的范围，请使用 64 位整数。