1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
#include <bits/stdc++.h>

using namespace std;

#define int long long

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<array<int, 2>> sc;
    {
        vector<int> sums;
        int m = n * (n - 1) / 2;
        sums.reserve(m);
        for (int i = 0; i < n; i++) {
            int s = 0;
            for (int j = i; j < n; j++) {
                s += a[j];
                sums.push_back(s);
            }
        }
// for (int v : sums) cerr << v << ' '; cerr << endl;
        sort(sums.begin(), sums.end());
// for (int v : sums) cerr << v << ' '; cerr << endl;
        int prev = sums[0];
        int cnt = 0;
        for (int v : sums) {
            if (v == prev) cnt++;
            else {
                sc.push_back({prev, cnt});
                prev = v;
                cnt = 1;
            }
        }
        sc.push_back({prev, cnt});
    }
    int m = size(sc);
    int res = 0;
    for (int b = 0; b < m; b++) {
        int target = -sc[b][0];
        if (!target) {
            if (sc[b][1] > 2) res += sc[b][1] * (sc[b][1] - 1) * (sc[b][1] - 2) / 6;
// cerr << sc[b][0] << ' ' << sc[b][0] << ' ' << sc[b][0] << ' ' << sc[b][1] * (sc[b][1] - 1) * (sc[b][1] - 2) / 6 << endl;
            continue;
        }
        int l = b + 1;
        int r = m - 1;
        while (l <= r) {
            if (target == 2 * sc[l][0]) {
                res += sc[b][1] * sc[l][1] * (sc[l][1] - 1) / 2;
// cerr << sc[b][0] << ' ' << sc[l][0] << ' ' << sc[l][0] << ' ' << sc[b][1] * sc[l][1] * (sc[l][1] - 1) / 2 << endl;
                l++;
                continue;
            } 
            if (target == 2 * sc[r][0]) {
                res += sc[b][1] * sc[r][1] * (sc[r][1] - 1) / 2;
// cerr << sc[b][0] << ' ' << sc[r][0] << ' ' << sc[r][0] << ' ' << sc[b][1] * sc[r][1] * (sc[r][1] - 1) / 2 << endl;
                r--;
                continue;
            }
            if (l == r) break;
            int s = sc[l][0] + sc[r][0];
            if (s == target) {
                res += sc[b][1] * sc[l][1] * sc[r][1];
// cerr << sc[b][0] << ' ' << sc[l][0] << ' ' << sc[r][0] << ' ' << sc[b][1] * sc[l][1] * sc[r][1] << endl;
                l++;
                r--;
            }
            else if (s < target) {
                l++;
            } else {
                r--;
            }
        }
        if (sc[b][1] == 1) continue;
        target = -2 * sc[b][0];
        for (l = b + 1; l < m; l++) {
            if (target == sc[l][0]) {
                res += sc[b][1] * (sc[b][1] - 1) / 2 * sc[l][1];
// cerr << sc[b][0] << ' ' << sc[b][0] << ' ' << sc[l][0] << ' ' << sc[b][1] * (sc[b][1] - 1) / 2 * sc[l][1] << endl;
                break;
            } 
        }
    }
    cout << res << endl;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

// #ifdef LOCAL
//     int t; cin >> t; while (t--)
// #endif

    solve();

    cout.flush();
}