0分求调
查看原帖
0分求调
469470
EurekaStriker楼主2022/11/9 16:46
#include<bits/stdc++.h>
using namespace std;
long long n,k,ans,f[250010],a[250010],h=1,r=1,q[250010],sum[250010];
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]),sum[i]=sum[i-1]+max(a[i],(long long)0);
    f[1]=a[1];
	for(int i=2;i<=n;i++)
    {
        while(h<=r&&i-q[h]>k) h++;
	    f[i]=a[i]+a[i-1]+f[q[h]]+sum[i-2]-sum[q[h]];
	    while(h<=r&&f[i-1]-sum[i-1]>=f[q[r]]-sum[q[r]])
	    	r--;
		q[++r]=i;
    }	
	for(int i=1;i<=n;i++)
		ans=max(f[i]+sum[min(i+k-1,n)]-sum[i],ans);
	cout<<max(ans,sum[k]);
	return 0;
}

2022/11/9 16:46
加载中...