脚本宝典收集整理的这篇文章主要介绍了【SSL_2884】假期,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
思路:
用单调队列,至于假期长度的处理只需要在到i时将i-p插入到队列就行了
#include<iostream>
#include<cstdio>
using namespace std;
long long n, p, q, b[101010], ans=-1e18;
long long a[1010101], q1[101010];
int main()
{
scanf("%lld%lld%lld", &n, &p, &q);
for(long long i=1; i<=n; i++)
scanf("%lld", &a[i]), b[i]=b[i-1]+a[i];
long long tl=0, hd=1;
for(long long i=1; i<=n; i++)
{
if(i>=p)
{
while(hd<=tl&&b[q1[tl]]>=b[i-p])
tl--;
q1[++tl]=i-p;
}
while(hd<=tl&&q1[hd]<i-q)
hd++;
if(hd<=tl)
ans=max(ans, b[i]-b[q1[hd]]);
}
printf("%lld", ans);
return 0;
}
以上是脚本宝典为你收集整理的【SSL_2884】假期全部内容,希望文章能够帮你解决【SSL_2884】假期所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。