记录编号	608869	评测结果	AAAAAAAAAAAAAAA
题目名称	4186.Chocolate Bar Partition	最终得分	100
用户昵称	李奇文	是否通过	通过
代码语言	C++	运行时间	0.579 s
提交时间	2025-10-29 21:40:01	内存使用	8.49 MiB

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=4e5+5;
int n,m,p[2],hd[2][N],f[2][N],g[N];
ll a[2][N],w,b[N];
int main(){
	freopen("Chocolate.in","r",stdin);
	freopen("Chocolate.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=0;i<2;++i){
		for(int j=1;j<=n;++j){
			cin>>a[i][j];
			w+=a[i][j];
		}
	}
	for(int i=0;i<2;++i)for(int j=1;j<=n;++j)a[i][j]=a[i][j-1]+2ll*n*a[i][j]-w;
	for(int i=0;i<2;++i)for(int j=0;j<=n;++j)b[++m]=a[i][j];
	sort(b+1,b+m+1);
	m=unique(b+1,b+m+1)-b-1;
	memset(hd,-1,sizeof(hd));
	int u=lower_bound(b+1,b+m+1,0)-b;
	hd[0][u]=hd[1][u]=0;
	for(int j=1;j<=n;++j){
		for(int i=0;i<2;++i){
			int o=i^1,i1=lower_bound(b+1,b+m+1,a[i][j])-b,i2=lower_bound(b+1,b+m+1,-a[i][j])-b;
			if(b[i2]!=-a[i][j])i2=0;
			int u1=hd[i][i1],u2=hd[o][i2];
			if(~u2)f[i][j]=max(f[i][j],f[o][u2]+1);
			if(~u1)f[i][j]=max(f[i][j],f[i][u1]+1);
			if(max(u1,u2)>0)f[i][j]=max(f[i][j],g[max(u1,u2)-1]+1);
			hd[i][i1]=j;
		}
		g[j]=max(g[j-1],max(f[0][j],f[1][j]));
	}
	cout<<g[n];
	return 0;
}