单调队列 , 零分 , 求助

P1725 琪露诺

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;
} 

|