P1714

题目

题目描述：

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

小 Z 作为寿星，自然希望吃到的蛋糕的幸运值总和最大，但小 Z 最多又只能吃 m(m≤n)m(m\le n) 小块的蛋糕。

请你帮他从这 nn 小块中找出连续的 k(1≤k≤m)k(1 \le k\le m) 块蛋糕，使得其上的总幸运值最大。

形式化地，在数列 {pn}\{p_n\} 中，找出一个子段 [l,r](r−l+1≤m)[l,r](r-l+1\le m)，最大化 ∑i=lrpi\sum\limits_{i=l}^rp_i。

输入格式：

第一行两个整数 n,mn,m。分别代表共有 nn 小块蛋糕，小 Z 最多只能吃 mm 小块。

第二行 nn 个整数，第 ii 个整数 pip_i 代表第 ii 小块蛋糕的幸运值。

输出格式：

仅一行一个整数，即小 Z 能够得到的最大幸运值。

数据范围与说明：

数据规模与约定

  • 对于 20%20\% 的数据，有 1≤n≤1001\le n\le100。
  • 对于 100%100\% 的数据，有 1≤n≤5×1051\le n\le5\times 10^5，∣pi∣≤500|p_i|≤500。

保证答案的绝对值在 [0,231−1][0,2^{31}-1] 之内。

输入输出样例 #1

输入：

1
2
5 2
1 2 3 4 5

输出：

1
9

输入输出样例 #2

输入：

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

输出：

1
5

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
int ans=-233333333,n,m,a,sum[500006];
deque<int>q;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a;
        sum[i]=sum[i-1]+a;
    }
    q.push_back(0);
    for(int i=1;i<=n;i++){
        while(q.front()+m<i){
            q.pop_front();
        }
        ans=max(ans,sum[i]-sum[q.front()]);
        while(!q.empty()&&sum[q.back()]>=sum[i])
        {
            q.pop_back();
        }
        q.push_back(i);
    }
     cout<<ans;
}