关于P8975

#include<bits/stdc++.h>
using namespace std;
constexpr int maxn=1e7+5;
int n,k,a[maxn],bit[maxn],tot,L,cur,nw,pre[maxn];
int smax[maxn],pmax[maxn],pos[maxn],neg[maxn],ans;
deque<int>que;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>k;
	for (int i=1;i<=n;i++)
		cin>>a[i];
	for (int i=1;i<=n;i++){
		pre[i]=tot;
		if (a[i]==0){
			pos[i]=1;
			neg[i]=-1;
			bit[++tot]=i;
		}else{
			pos[i]=a[i];
			neg[i]=a[i];
		}
	}
	for (int i=1;i<=n;i++){
		pos[i]+=pos[i-1];
		neg[i]+=neg[i-1];
	}
	pmax[n+1]=smax[n+1]=-2e9;
	for (int i=n;i>=1;i--){
		pmax[i]=max(pmax[i+1],pos[i]);
		smax[i]=max(smax[i+1],neg[i]);
	}
	que.push_back(n+2);
	for (int i=0;i<=n;i++){
		while (!que.empty() && que.front()<i)
			que.pop_front();
		L=pre[i];
		if (L+k+1>tot){
			int tmp1=pmax[i+1]-pos[i];
			ans=max(ans,tmp1);
			//cout<<i<<' '<<tmp1<<'\n';
		}else{
			cur=bit[L+k+1];
			for (int j=nw+1;j<cur;j++){
				while(!que.empty() && pos[que.back()]<pos[j])
					que.pop_back();
				que.push_back(j);
			}
			nw=cur-1;
			int tmp1=pos[que.front()]-pos[i];
			int tmp2=smax[cur]-neg[i]+k*2;
			ans=max({ans,tmp1,tmp2});
			//cout<<i<<' '<<tmp1<<' '<<tmp2<<'\n';
		}
	}
	cout<<ans;
	return 0;
}