LG#P1714. 切蛋糕

切蛋糕

P1714 切蛋糕

题目描述

\hspace{15pt}今天是小 Z 的生日,同学们为他带来了一块蛋糕。这块蛋糕是一个长方体,被用不同色彩分成了 nn 个相同的小块,每小块都有对应的幸运值。

\hspace{15pt}小 Z 作为寿星,自然希望吃到的蛋糕的幸运值总和最大,但他最多只能吃 mm 小块。

\hspace{15pt}请你帮他从这 nn 小块中找出连续的 k(1≦k≦m)k \left(1 \leqq k \leqq m\right) 块蛋糕,使得其上的幸运值总和最大。

\hspace{15pt}形式化地,给定数列 {p1,p2,…,pn}\{p_1, p_2, \dots, p_n\},请找出一个子段 $\left[l, r\right] \left(1 \leqq l \leqq r \leqq n;\ r-l+1 \leqq m\right)$,使得 ∑i=lrpi\sum\limits_{i=l}^{r} p_i 最大,并输出这个最大值。

输入格式

\hspace{15pt}第一行输入两个整数 $n, m \left(1 \leqq m \leqq n \leqq 5 \times 10^5\right)$ 代表共有 nn 小块蛋糕,小 Z 最多只能吃 mm 小块。

\hspace{15pt}第二行输入 nn 个整数 $p_1, p_2, \dots, p_n \left(-500 \leqq p_i \leqq 500\right)$,其中 pip_i 代表第 ii 小块蛋糕的幸运值。

输出格式

\hspace{15pt}在一行上输出一个整数,代表小 Z 能够得到的最大幸运值。

测试样例

5 2
1 2 3 4 5
9

样例 1 解释

\hspace{15pt}数列为 {1,2,3,4,5}\{1, 2, 3, 4, 5\},m=2m=2,即最多只能吃 22 块连续的蛋糕。

∙ \hspace{23pt}\bullet\,若只吃 11 块,最优选择第 55 块,幸运值为 55;

∙ \hspace{23pt}\bullet\,若吃 22 块,最优选择第 4,54, 5 块,幸运值为 4+5=94+5=9。

\hspace{15pt}因为所有幸运值都是正数,吃得越多总和越大,所以最大值为 99。

6 3
1 -2 3 -4 5 -6
5

提示

\hspace{15pt}对于 20%20\% 的数据,1≦n≦1001 \leqq n \leqq 100。

\hspace{15pt}对于 100%100\% 的数据,1≦n≦5×1051 \leqq n \leqq 5 \times 10^5,∣pi∣≦500\left|p_i\right| \leqq 500。

\hspace{15pt}保证答案的绝对值不超过 231−12^{31}-1。