比赛 csp2025模拟练习2 评测结果 AAAAAAAAAAAAAAA
题目名称 Chocolate Bar Partition 最终得分 100
用户昵称 wdsjl 运行时间 1.540 s
代码语言 C++ 内存使用 15.36 MiB
提交时间 2025-10-29 11:11:39
显示代码纯文本
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e5+10;
const int inf = 1e9;

int dp[N][3],s[N][3],n,a[N][3],sum;
struct node{
	int v;
	node(){
		v=-inf;
	}
};

map<int,node>mp[4];

signed main(){
    freopen("Chocolate.in","r",stdin);
    freopen("Chocolate.out","w",stdout);
    scanf("%lld",&n);
    for(int i=0;i<=1;i++){
		for(int j=1;j<=n;j++){
			scanf("%lld",&a[j][i]);
			sum+=a[j][i];
			a[j][i]*=2*n;
		} 
	}
    for(int i=0;i<=1;i++){
		for(int j=1;j<=n;j++){
			a[j][i]-=sum;
		} 
	}
    for(int i=0;i<=1;i++){
		for(int j=1;j<=n;j++){
			s[j][i]=s[j-1][i]+a[j][i];
		}
	}
    for(int i=1;i<=n;i++){
        for(int j=0;j<=1;j++){
        	if(mp[j][s[i-1][j]].v<dp[i-1][j^1]){
        		mp[j][s[i-1][j]].v=dp[i-1][j^1];
			}
			if(mp[j|2][s[i-1][j^1]].v<dp[i-1][j]){
				mp[j|2][s[i-1][j^1]].v=dp[i-1][j];
			}
		}
        for(int j=0;j<=1;j++){
        	dp[i][j]=max(dp[i-1][0],dp[i-1][1]);//当前列两格均划入非零连通块
			dp[i][j]=max(dp[i][j],mp[j^1][s[i][j^1]].v+1);//另一行末尾若干格子单独成块 
			dp[i][j]=max(dp[i][j],mp[(j^1)|2][-s[i][j^1]].v+1);//另一行末尾格子与前非零连通块拼合
		}
        if(s[i][0]+s[i][1]==0){//前 i 列总和平为 0 
			dp[i][0]=dp[i][1]=max(dp[i][0],dp[i][1])+1;
		}
    }
    printf("%lld\n",dp[n][0]);
	return 0;
}