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
#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

const int SIZE = 500;

map<long long, long long> m;

long long counter(long long key) {
    if (m.count(key) > 0) {
        return m.at(key);
    }
    return 0;
}

int main(int argc, char const *argv[])
{
    int n;
    int a[SIZE];
    cin >> n;
    for (int i=0; i<n; i++) {
        cin >> a[i];
    }

    long long b[SIZE*SIZE];
    int count = 0;
    for (int i=0; i<n; i++) {
        b[count++] = a[i];
        for (int j=i+1; j<n; j++) {
            b[count++] = b[count-1] + a[j];
        }
    }
    sort(b, b+count);

    long long c[SIZE*SIZE];
    long long d[SIZE*SIZE];
    int count2 = 0;
    c[0] = b[0];
    d[0] = 1;
    for (int i=1; i<count; i++) {
        if (b[i] == c[count2]) {
            d[count2]++;
        } else {
            count2++;
            c[count2] = b[i];
            d[count2] = 1;
        }
    }
    count2++;

    for (int i=0; i<count2; i++) {
        m[c[i]] = d[i];
    }

    long long result = 0;
    for (int i=0; i<count2; i++) {
        if (c[i] > 0) {
            break;
        } else if (c[i] == 0) {
            if (d[i] >= 3) {
                result += d[i]*(d[i]-1)*(d[i]-2)/6;
            }
        } else {
            if (d[i] > 1) {
                result += d[i]*(d[i]-1)/2 * counter(-c[i]*2);
            }
            for (int j=i+1; j<count2; j++) {
                if (c[i] + c[j]*2 > 0) {
                    break;
                }
                if (c[i] + c[j]*2 == 0) {
                    result += d[i] * d[j]*(d[j]-1)/2;
                    break;
                }
                result += d[i] * d[j] * counter(-c[i]-c[j]);
            }
        }
    }

    cout << result << endl;

    return 0;
}