【SSL_P2521】数数

数数

---

数据

输入

3 2
1 2 3

输出

5

解题思路

也是前缀和，然后就没有然后了

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

long long n,k,a[100010],ans=-0x3f3f3f3f;
long long hd=1,tl=1,t[100010];

int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		a[i]+=a[i-1];
	}
	memset(t,-0x3f3f3f3f,sizeof(t));
	t[1]=0;
	for(int i=1;i<=n;i++)
	{
		while(hd<=tl&&a[i]<a[t[tl]]) tl--;
		t[++tl]=i;
		while(hd<=tl&&t[hd]<i-k) hd++;
		ans=max(ans,a[i]-a[t[hd]]);
	}
	cout<<ans<<endl;
	return 0;
}