return_dirt @ 2020-10-28 22:56:28
过样例了,然而全WA
#include <cstdio>
#include <algorithm>
using namespace std;
int n,l,r;
int line[300000];
int dp[300000],a[300000];
int ans;
int main()
{
scanf("%d%d%d",&n,&l,&r);
for(int i=0;i<=n;i++)
{
scanf("%d",&a[i]);
dp[i]=a[i];
}
int end=0;
int head=0;
for(int i=l;i<=n;i++)
{
while(line[head+1]<i+l-r&&head<end)head++;
while(end!=head&&dp[i]>dp[line[end]])end--;
line[++end]=i;
for(int j=head+1;j<=end;j++)
dp[i+l]=max(dp[i]+a[i+l],dp[i+l]);
}
for(int i=n-r+1;i<=n;i++)
ans=max(ans,dp[i]);
printf("%d",ans);
return 0;
}