数据过水

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using sh=short;
const int N=5005;
const int inf=5055;

//bool ST;

int n;
ll a[N];
ll suma[N];
ll Suma(int x){
	if(x<0){
		return 0;
	}
	return suma[x];
}

sh dp[N][N];
sh trans[N][N];

pair<sh,sh> tr[N][N*4];

void build(int id,int k,int L,int R){
	if(L==R){
		tr[id][k]={dp[id][L],L};
		return;
	}
	int mid=(L+R)>>1;
	build(id,k<<1,L,mid);
	build(id,k<<1|1,mid+1,R);
	tr[id][k]=max(tr[id][k<<1],tr[id][k<<1|1]);
}
void Print(int id,int k,int L,int R){
	cerr<<"TR("<<id<<","<<k<<"["<<L<<","<<R<<"]):"<<tr[id][k].first<<","<<tr[id][k].second<<"\n";
	if(L==R){
		return ;
	}
	int mid=(L+R)>>1;
	Print(id,k<<1,L,mid);
	Print(id,k<<1|1,mid+1,R);
	
}
pair<sh,sh> qmax(int id,int k,int L,int R,int ql,int qr){
	if(ql<=L&&R<=qr){
		return tr[id][k];
	}
	int mid=(L+R)>>1;
	pair<sh,sh> ans={-inf,-inf};
	if(ql<=mid){
		ans=max(ans,qmax(id,k<<1,L,mid,ql,qr));
	}
	if(qr>mid){
		ans=max(ans,qmax(id,k<<1|1,mid+1,R,ql,qr));
	}
	return ans;
}

int main(){
//	freopen("rastuci.in","r",stdin);
//	freopen("rastuci.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>a[i];
		suma[i]=suma[i-1]+a[i];
	}
	for(int i=0;i<=n;++i){
		for(int j=0;j<=n;++j){
			dp[i][j]=-inf;
		}
	}
	dp[0][0]=0;
	build(0,1,0,n);
	for(int i=1;i<=n;++i){
		for(int j=max(1,i-1000);j<=i;++j){//Here!!!
			int L=0,R=j-1,ans=-1;
			while(L<=R){
				int mid=(L+R)>>1;
				if(suma[j-1]-Suma(mid-1)<=suma[i]-suma[j-1]){
					ans=mid;
					R=mid-1;
				}else{
					L=mid+1;
				}
			}
			if(ans==-1){
				continue;
			}
			auto t=qmax(j-1,1,0,j-1,ans,j-1);
			dp[i][j]=t.first+1;
			trans[i][j]=t.second;
		}
		dp[i][0]=0;
		build(i,1,0,i);
	}
	auto furina=qmax(n,1,0,n,0,n);
	cout<<furina.first<<"\n";
	int t=furina.second,now=n;
	vector<ll> Ans;
	while(now){
		Ans.emplace_back(suma[now]-Suma(t-1));
		sh nxt=trans[now][t];
		now=t-1;
		t=nxt;
	}
	reverse(Ans.begin(),Ans.end());
	for(ll f:Ans){
		cout<<f<<" ";
	}
	return 0;
}
/*

*/