记录编号	608875	评测结果	AAAAAAAAAAAAAAA
题目名称	4186.Chocolate Bar Partition	最终得分	100
用户昵称	梦那边的美好TT	是否通过	通过
代码语言	C++	运行时间	0.598 s
提交时间	2025-10-29 21:59:17	内存使用	8.62 MiB

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=4e5+5;
int n,m,f[2][N],g[N],hd[2][N];
ll a[2][N],w,b[N];
int main() {
    freopen("Chocolate.in","r",stdin);
    freopen("Chocolate.out","w",stdout);
	scanf("%d",&n);
	for(int i=0;i<2;++i)
		for(int j=1;j<=n;++j)
			scanf("%lld",&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;
	m=0;
	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;
			int i1=lower_bound(b+1,b+m+1,a[i][j])-b;
			int 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];
			f[i][j]=0;
			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]));
	}
	printf("%d\n",g[n]);
	return 0;
}