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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;
    vector<int> val(n);
    for(int i = 0; i < n; i++) cin >> val[i];

    ll result = 0;
    vector<int> suffs(n);
    vector<int> sums(int(2e7) + 1, 0);
    vector<int> q;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j <= i; j++) {
            suffs[j] += val[i];
            for(int k = 0; k < q.size(); k++) {
                int v = q[k];
                if(v > -suffs[j] -v) {
                    result += sums[v + int(1e7)] * sums[int(1e7) -suffs[j] - v];
                } else if(0 == suffs[j] + 2*v) result += sums[v + int(1e7)] * (sums[v + int(1e7)] - 1) / 2;
            }
        }

        for(int j = 0; j <= i; j++) {
            if(sums[suffs[j] + int(1e7)] == 0) q.push_back(suffs[j]);
            sums[suffs[j] + int(1e7)]++;
        }
    }

    fill(suffs.begin(), suffs.end(), 0);
    fill(sums.begin(), sums.end(), 0);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j <= i; j++) {
            suffs[j] += val[i];
        }

        for(int j = 0; j <= i; j++) {
            for(int k = j + 1; k <= i; k++) {
                result += sums[int(1e7) - suffs[j] - suffs[k]];
            }
            sums[suffs[j] + int(1e7)]++;
        }
    }

    cout << result << '\n';
}