记录编号	578545	评测结果	AAAAAAAAAAAAAA
题目名称	[USACO23 Feb Gold] Equal Sum Subarrays	最终得分	100
用户昵称	ムラサメ	是否通过	通过
代码语言	C++	运行时间	1.803 s
提交时间	2023-03-29 19:00:07	内存使用	9.00 MiB

#include<bits/stdc++.h>
using namespace std;
const long long INF=8e18;
long long n,a[510],ans[510],sum[510];
struct Node{
	long long l,r,x;
	bool operator<(const Node&a)const{
		return x<a.x;
	}
}xx[200010];
vector<long long> ADD[510],RMV[510];
bool bj[510];
void tag(long long a,long long b,long long v){
	memset(bj,0,sizeof(bj));
	long long l=xx[a].l,r=xx[a].r;
	for(int i=l;i<=r;i++){
		bj[i]^=1;
	}
	l=xx[b].l;
	r=xx[b].r;
	for(int i=l;i<=r;i++){
		bj[i]^=1;
	}
	for(int i=1;i<=n;i++){
		if(bj[i]){
			ans[i]=min(ans[i],v);
		}
	}
}
int main(){
	freopen("dhzsz.in","r",stdin);
	freopen("dhzsz.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];
	}
	long long cnt=0;
	for(int i=1;i<=n;i++){
		for(int j=i;j<=n;j++){
			long long x=sum[j]-sum[i-1];
			xx[++cnt]=(Node){i,j,x};
		}
	}
	sort(xx+1,xx+1+cnt);
	fill(ans,ans+1+n,INF);
	for(int i=1;i<=cnt;i++){
		long long nw=INF,id=0;
		if(i!=1){
			long long cost=xx[i].x-xx[i-1].x;
			tag(i-1,i,cost);
		}
		if(i!=cnt){
			long long cost=xx[i+1].x-xx[i].x;
			tag(i,i+1,cost);
		}
	}
	for(int i=1;i<=n;i++){
		cout<<ans[i]<<endl;
	}
	return 0;
}