小超手123 @ 2022-08-31 15:57:51
#include<bits/stdc++.h>
using namespace std;
int n,l,r,ans=-1e9,a[300005],f[300005]; //f[i]表示跳到i
int que[300005],head=1,tail=0; //head~tail
int main() {
scanf("%d %d %d",&n,&l,&r);
for(int i=0;i<=n;i++){
scanf("%d",&a[i]);
f[i]=-1e9;
}
f[0]=0;
for(int i=0;i<l;i++)
for(int i=0;i<=n;i++){
//单调队列求最大值(i-r~i-l)
while(tail>=head&&i-que[head]+1>r-l+1)head++; //过期的
while(tail>=head&&f[que[tail]]<f[i-l+1]&&i>=l)tail--;
que[++tail]=i-l+1;
f[i]=f[que[tail]]+a[i];
/*for(int j=i-r;j<=i-l;j++){ //j->i
if(j>=0)
f[i]=max(f[i],f[j]+a[i]);
}*/
if(i>=n-r+1)
ans=max(ans,f[i]);
}
cout<<ans;
return 0;
}