renxiaoyao36 @ 2019-11-14 19:56:41
#include <bits/stdc++.h>
using namespace std;
long long n,l,r;
long long am[210000];
long long dp[210000];
int main(void)
{
//freopen("in.txt","r",stdin);
long long ans=-0x7FFFFFFFFF;
scanf("%lld %lld %lld",&n,&l,&r);
for(long long i=0;i<=n;i++)
{
scanf("%lld",am+i);
}
for(long long i=0;i<=n+r;i++)
{
dp[i]=-0x7FFFFFFFFF;
}
dp[0]=am[0];
deque<long long> dui;
dui.push_back(0);
for(long long i=l;i<=n;i++)
{
if((dui.front()+r<i)&&!dui.empty())dui.pop_front();
long long lastmax=dp[dui.front()];
//printf("CHECK:i=%lld,using:%lld=%lld,now=%lld\n",i,dui.front(),dp[dui.front()],am[i]);
dp[i]=lastmax+am[i];
if(i+r>n)
{
ans=max(ans,dp[i]);
}
if((dp[dui.back()]<dp[i-l])&&!dui.empty())dui.pop_back();
dui.push_back(i-l);
}
printf("%lld",ans);
return 0;
}
用的单调队列,我没法下载数据了,因为下载到上限了,急求帮助!
by renxiaoyao36 @ 2019-11-14 22:08:21
更新:已自行解决,通过暴力对拍发现,在Pop Back的时候没有使用while循环导致POP的不干净