abc_de @ 2022-09-02 22:36:40
wa两个测试点 80pts 求dalao帮忙看看 谢谢
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int n,l,r;
int w[maxn];
int dp[maxn],ans=-0x3f3f3f3f;
struct node{
int p,a;
}q[maxn];
int rd(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+ch-'0';
ch=getchar();
}
return x*f;
}
int main(){
// freopen("A.in","r",stdin);
// freopen("A.out","w",stdout);
n=rd();l=rd();r=rd();
for(int i=0;i<=n;i++) w[i]=rd();
int l1=0,r1=0;
for(int i=1;i<=n+r;i++) dp[i]=-0x3f3f3f3f;
for(int i=l;i<=n+r;i++){
while(l1<=r1&&q[r1].p>i-l) r1--;
while(l1<=r1&&q[l1].p<i-r) l1++;
dp[i]=q[l1].a+w[i];
while(l1<=r1&&dp[i-l+1]>q[r1].a) r1--;
q[++r1].a=dp[i-l+1];
q[r1].p=i-l+1;
}
for(int i=n+1;i<=n+r;i++) ans=max(ans,dp[i]);
cout<<ans;
return 0;
}