LG#P1714. 切蛋糕
切蛋糕
P1714 切蛋糕
题目描述
今天是小 Z 的生日,同学们为他带来了一块蛋糕。这块蛋糕是一个长方体,被用不同色彩分成了 个相同的小块,每小块都有对应的幸运值。
小 Z 作为寿星,自然希望吃到的蛋糕的幸运值总和最大,但他最多只能吃 小块。
请你帮他从这 小块中找出连续的 块蛋糕,使得其上的幸运值总和最大。
形式化地,给定数列 ,请找出一个子段 $\left[l, r\right] \left(1 \leqq l \leqq r \leqq n;\ r-l+1 \leqq m\right)$,使得 最大,并输出这个最大值。
输入格式
第一行输入两个整数 $n, m \left(1 \leqq m \leqq n \leqq 5 \times 10^5\right)$ 代表共有 小块蛋糕,小 Z 最多只能吃 小块。
第二行输入 个整数 $p_1, p_2, \dots, p_n \left(-500 \leqq p_i \leqq 500\right)$,其中 代表第 小块蛋糕的幸运值。
输出格式
在一行上输出一个整数,代表小 Z 能够得到的最大幸运值。
测试样例
5 2
1 2 3 4 5
9
样例 1 解释
数列为 ,,即最多只能吃 块连续的蛋糕。
若只吃 块,最优选择第 块,幸运值为 ;
若吃 块,最优选择第 块,幸运值为 。
因为所有幸运值都是正数,吃得越多总和越大,所以最大值为 。
6 3
1 -2 3 -4 5 -6
5
提示
对于 的数据,。
对于 的数据,,。
保证答案的绝对值不超过 。