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
//#include <iostream>
//#include <fstream>
#include <vector>

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <unordered_map>
#include <unordered_set>

using namespace std;


long long countZeroSumTriplets(vector<long long>& S) {
	long long result = 0;
	unordered_map<long long, long long> freq;
    for (long long num : S) {
        freq[num]++;
    }
    sort(S.begin(), S.end());
    long long n = S.size();
    for (long long i = 0; i < n - 2; ++i) {
        long long a = S[i];
        if (a > 0) {
        	break;
		}
        long long start = i + 1;
        long long end = n - 1;
        while (start < end) {
            long long b = S[start];
            long long c = S[end];
            if (a + b + c == 0) {
				if (S[start] == S[end]) {
					//end-start+1 to ilosc
					result = result + ((end-start + 1) * (end-start)) / 2;
				} else {
					result = result + (freq[S[start]]*freq[S[end]]);
				}
				
                start += freq[S[start]];
                end -= freq[S[end]];
            } else if (a + b + c > 0) {
                end--;
            } else {
                start++;
            }
        }
    }
    return result;
}

int main(int argc, char** argv) {
	std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    long long result = 0;
    
//    ifstream fin;
//    fin.open("sample4.txt");
    
    long long n;
    vector<long long> vec;
    cin >> n;
//    fin >> n;
    long long kaczka;
    for (long long i=0; i<n; i++) {
    	cin >> kaczka;
//    	fin >> kaczka;
    	vec.push_back(kaczka);
	}
//	fin.close();
	
	vector<long long> ciagi;

	int tmp;
	for (long long i=0; i<n; i++) {
		for (long long j=i; j<n; j++) {
			tmp = 0;
			for (long long k=i; k<=j; k++) {
				tmp += vec[k];
			}
			ciagi.push_back(tmp);
		}
	}
	//cout<<ciagi.size()<<endl;
	result = countZeroSumTriplets(ciagi);
	cout << result;
	return 0;
}