Maximum Subarray Sum II

1#include<bits/stdc++.h>
2using namespace std;
3#define int long long
4signed main(){
5  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
6  int n,a,b; cin>>n>>a>>b;
7  priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
8  int res=-3e18,ps[n+1]{};
9  for(int i=1;i<=n;++i){
10    cin>>ps[i];
11    ps[i]+=ps[i-1];
12    while(pq.size()&&i-pq.top().second>b) pq.pop();
13    if(i>=a){
14      pq.emplace(ps[i-a],i-a);
15      res=max(res,ps[i]-pq.top().first);
16    }
17  }
18  cout<<res<<'\n';
19  return 0;
20}