【SSL_2884】假期

在这里插入图片描述

思路:

用单调队列,至于假期长度的处理只需要在到i时将i-p插入到队列就行了

c o d e code code

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