蛋糕的最大幸运值
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
Description
[洛谷 P1714]
今天是小Z的生日，同学们为他带来了一块蛋糕。
这块蛋糕是一个长方体，被用不同色彩分成了N个相同的小块，每小块都有对应的幸运值。
小Z希望吃到的蛋糕的幸运值总和最大，但小Z最多又只能吃M小块(M≤N)的蛋糕。
请你帮他从这N小块中找出连续的k块蛋糕(k≤M)，使得其上的幸运值最大。
Input Format
第一行包含两个整数N和M，表示共有N小块蛋糕，小Z最多只能吃M小块。
第二行包含空格隔开的N个整数，第i个整数Pi代表第 i 小块蛋糕的幸运值。
数据范围：
1 ≤ N ≤ 500000
−500 ≤ Pi ≤ 500
Output Format
输出包含一个整数，为小Z能够得到的最大幸运值。
5 2
1 2 3 4 5
9
6 3
1 -2 3 -4 5 -6
5
Hint
题意分析：
在长度为N的区间里找一个长度不超过M的区间,要求区间和最大。
Source
单调队列
NCST CCPC赛前训练2 单调栈/队列、堆、Hash、Huffman树、Trie、KMP
- 状态
- 已结束
- 规则
- ACM/ICPC
- 题目
- 25
- 开始于
- 2019-4-12 21:40
- 结束于
- 2019-5-13 1:00
- 持续时间
- 723.3 小时
- 主持人
-
2080226675@qq.com
- 参赛人数
- 10
