分蛋糕（前缀和 单调队列）

#include<bits/stdc++.h>
#define int long long
typedef long long ll;
using namespace std;
const int N = 2e3 + 10;
const int mod  = 1e9 + 7;
void solve(){
    int n,m;
    cin>>n>>m;
    vector<int> a(n+1,0),sum(n+1,0);
    for (int i = 1; i <= n; ++i) {
        cin>>a[i];
        sum[i] = sum[i-1] + a[i];
    }
    int maxx = 0;
    deque<int> dq;    //用来维护i-m+1 -- i-1的sum最小值
        dq.push_back(0);
    for (int i = 1; i <= n; ++i) {
        if(!dq.empty() && dq.front() < i - m) 
        dq.pop_front();
        while (!dq.empty() && sum[i] <= sum[dq.back()]){
            dq.pop_back();
        }
        dq.push_back(i);
        if (dq.size())maxx = max(maxx,sum[i] - sum[dq.front()]);
    }
    cout<<maxx<<endl;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int t = 1;
    //cin>>t;
    while(t--){
        solve();//1 2 3 4 5
    }
    return 0 ;
}