记录编号	608868	评测结果	AAAAAAAAAAAAAAA
题目名称	4186.Chocolate Bar Partition	最终得分	100
用户昵称	淮淮清子	是否通过	通过
代码语言	C++	运行时间	1.176 s
提交时间	2025-10-29 21:39:53	内存使用	11.42 MiB

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
using ll = long long;
const int INF = 1e9;

ll a[MAXN][2], s[MAXN][2];
int f[MAXN][2];
map<ll, int> mp[4];
int n;ll sum = 0;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    auto gmx = [](int &x, int y) { if (y > x) x = y; };
    
    cin >> n;
    for(int i = 0; i < 2; ++i) {
        for(int j = 1; j <= n; ++j) {
            cin >> a[j][i];
            sum += a[j][i];
        }
    }

    ll mul = 2 * n;
    for (int i = 0; i < 2; ++i) {
        for (int j = 1; j <= n; ++j) {
            a[j][i] = a[j][i] * mul - sum;
        }
    }

    for (int i = 0; i < 2; ++i) {
        s[0][i] = 0;
        for (int j = 1; j <= n; ++j) {
            s[j][i] = s[j-1][i] + a[j][i];
        }
    }

    for (int i = 0; i < 4; ++i) mp[i].clear();
    f[0][0] = f[0][1] = 0;

    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < 2; ++j) {
            ll k1 = s[i - 1][j];
            gmx(mp[j][k1], f[i - 1][1 - j]);
            ll k2 = s[i - 1][1 - j];
            gmx(mp[j|2][k2], f[i - 1][j]);
        }

        for(int j = 0;j < 2;j ++){
            f[i][j] = max(f[i - 1][0], f[i - 1][1]);
            ll k = s[i][1 - j];
            int v1 = mp[1 - j].count(k) ? mp[1 - j][k] : -INF;
            gmx(f[i][j], v1 + 1);
            k = -s[i][1 - j];
            int v2 = mp[(1 - j)|2].count(k) ? mp[(1 - j)|2][k] : -INF;
            gmx(f[i][j], v2 + 1);
        }

        if (s[i][0] + s[i][1] == 0) {
            int mx = max(f[i][0], f[i][1]) + 1;
            f[i][0] = f[i][1] = mx;
        }
    }

    cout << f[n][0] << '\n';
    return 0;
}