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
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <unordered_map>

#define LL long long
#define PI pair<int, int>

using namespace std;

constexpr int M = 10000000;

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

    int n;
    cin >> n;

    vector<int> arr(n);
    unordered_map<int, int> cnt;
    vector<PI> S;

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

    for (int i = 0; i < n; ++i)
    {
        int s = 0;
        for (int j = i; j < n; ++j)
        {
            s += arr[j];
            ++cnt[s];
        }
    }

    LL res = 0ll;
    res += (LL) cnt[0] * (LL) (cnt[0] - 1ll) * (LL) (cnt[0] - 2ll) / 6ll;

    for (auto &[a, b] : cnt)
    {
        S.emplace_back(a, b);
        if (b > 1 && a && cnt.count(-2 * a))
        {
            res += (LL) b * (LL) (b - 1) * (LL) cnt[-2 * b];
        }
    }

    sort(S.begin(), S.end());
    int m = (int) S.size();

    for (int i = 0; i <= m - 2; ++i)
    {
        int j = i + 1;
        int k = m - 1;
        while (j < k)
        {
            if (S[i].first + S[j].first + S[k].first == 0)
            {
                res += (LL) S[i].second * (LL) S[j].second * (LL) S[k].second;
                ++j;
                --k;
            }
            else if (S[i].first + S[j].first + S[k].first > 0) --k;
            else ++j;
        }
    }

    cout << res;
}