记录编号	608872	评测结果	AAAAAAAAAAAAAAA
题目名称	4186.Chocolate Bar Partition	最终得分	100
用户昵称	陆晨洗	是否通过	通过
代码语言	C++	运行时间	0.894 s
提交时间	2025-10-29 21:50:02	内存使用	8.47 MiB

#include<bits/stdc++.h>
using namespace std;
const int N=4e5+5;
int n,m,p[2],hd[2][N],f[2][N],g[N];
long long a[2][N],w,b[N];
int main()
{
    freopen("Chocolate.in","r",stdin);
    freopen("Chocolate.out","w",stdout);
    int u,u1,u2,o,i,i1,i2,j;
	cin>>n;
	for(i=0;i<2;i++)
    {
        for(j=1;j<=n;j++)
        {
            cin>>a[i][j];
            w=w+a[i][j];
        }
    }
	for(i=0;i<2;i++)
    {
        for(j=1;j<=n;j++)
        {
            a[i][j]=a[i][j-1]+2ll*n*a[i][j]-w;
        }
    }
	for(i=0;i<2;i++)
    {
        for(j=0;j<=n;j++)
        {
            m++;
            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));
	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)
        {
			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;
            }
			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;
}