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

using namespace std;

#ifdef D
#define DEBUG(x)        \
    do {                \
        x               \
        cout.flush();   \
    } while (0)
#else
#define DEBUG(x)
#endif

using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

const int NMAX = 507;
int n;
int uc[NMAX], pref[NMAX];
vector<int> buc;
unordered_multiset<int> sbuc;
ull res;
map<int, int> cnt;
vector<pii> cntd;

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

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> uc[i];
        pref[i] = pref[i - 1] + uc[i];
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = i; j <= n; ++j) {
            int a = pref[j] - pref[i - 1];
            buc.push_back(a);
            sbuc.insert(a);
        }
    }

    for (int a : buc) {
        cnt[a]++;
    }

    for (auto &p : cnt) {
        cntd.emplace_back(p);
    }

    for (int i = 0; i < cntd.size(); ++i) {
        if (cntd[i].first == 0) {
            res += (ull)cntd[i].second * (cntd[i].second - 1) * (cntd[i].second - 2) / 6;
            continue;
        }
        for (int j = i + 1; j < cntd.size(); ++j) {
            int s = -cntd[i].first - cntd[j].first;
            if (s == cntd[i].first) {
                res += (ull)cntd[j].second * (ull)cntd[i].second * ((ull)cntd[i].second - 1) / 2;
            }
            else if (s == cntd[j].first) {
                res += (ull)cntd[i].second * (ull)cntd[j].second * ((ull)cntd[j].second - 1) / 2;
            }
            else if (s > cntd[j].first) {
                ull d = sbuc.count(s);
                res += d * (ull)cntd[i].second * (ull)cntd[j].second;
                // DEBUG(
                //     cout << i << " " << j << "\n";
                // );
            }
        }
    }

    cout << res << "\n";

    return 0;
}