st表72pts RE 求条 玄关
查看原帖
st表72pts RE 求条 玄关
935574
dulinfan2023楼主2025/1/19 19:18
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define debug() cout<<"come on"<<'\n'
int n,m,ans=-2147483647,a[500005],s[500005],st[500005][22],maxn=-2147483647;
int lrmin(int l,int r){
	int lg=log2(r-l+1);
	return min(st[l][lg],st[l+(1<<lg)][lg]);
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i],s[i]=s[i-1]+a[i],st[i][0]=s[i],maxn=max(maxn,a[i]);
	st[0][0]=0;
	if(m==0){
		return cout<<0,0;
	}
	for(int j=1;j<=20;j++){
		for(int i=1;i<=n-(1<<j)+1;i++){
			st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
		}
	}
//	for(int i=1;i<=n;i++)cout<<s[i]<<" \n"[i==n];
	for(int i=1;i<=n;i++){
		ans=max(ans,s[i]-lrmin(max(0ll,i-m),i-1));
//		cout<<max(0ll,i-m)<<" "<<i-1<<" "<<lrmin(max(0ll,i-m),i-1)<<" "<<s[i]<<" "<<s[i]-lrmin(max(0ll,i-m),i-1)<<'\n';
	}
	cout<<max(ans,0ll);
	return 0;
}
2025/1/19 19:18
加载中...