Kniqht @ 2020-12-13 14:04:11
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,l,r,ans,q[N],hh,tt,f[N],a[N];
int main(){
memset(f,0xcf,sizeof(f));//赋值
f[0]=0,ans=f[1];
scanf("%d%d%d",&n,&l,&r);
scanf("%d",&a[0]);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++){
while(hh<=tt&&q[hh]+r-1>=i&&q[hh]+l-1<=i) hh++;//hh<=tt队列非空,后两个是越界判断
f[i]=max(f[i],f[q[hh]]+a[i]);//dp
while(hh<=tt&&f[q[tt]]<f[q[i]]) tt--;//更新
q[++tt]=i;/入队
}
for(int i=n-r+1;i<=n;i++) ans=max(ans,f[i]);
printf("%d",ans);
return 0;
}```