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
91
92
93
94
95
#include <bits/stdc++.h>
using namespace std;
int * s;
map <int, int> c;
int tab[500];
int indeks0 = -1;
// returns true if there is triplet with sum equal
// to 'sum' present in A[]. Also, prints the triplet
long long find3Numbers(int A[], int arr_size, int sum)
{
    int l, r, j, i; 
	long long wyn = 0;
    /* Sort the elements */
    sort(A, A + arr_size);
    /* Now fix the first element one by one and find the
       other two elements */
    for (i = 0; i < arr_size - 2; i++) {
 
        // To find the other two elements, start two index
        // variables from two corners of the array and move
        // them toward each other
        l = i + 1; // index of the first element in the
        // remaining elements
        if (A[l] == 0) indeks0 = l;
        r = arr_size - 1; // index of the last element
        while (l < r) {
            if (A[i] + A[l] + A[r] == sum) {
                //printf("Triplet is %d, %d, %d\n", A[i], A[l],A[r]);
                wyn += (long long)c[A[i]]*c[A[l]] *c[A[r]] ;
                l++;
            }
            else if (A[i] + A[l] + A[r] < sum)
                l++;
            else // A[i] + A[l] + A[r] > sum
                r--;
        }
    }
    r =  min(indeks0,arr_size-1);
    for(i = 0; i < r; i++) {
    	for(j = r + 1; j < arr_size; j++){
    		if (c[A[j]] > 1 && A[i] == -2*A[j]) wyn += (long long)c[A[i]]*c[A[j]]*(c[A[j]]-1)/2;
    		if (c[A[i]] > 1 && A[j] == -2*A[i]) wyn += (long long)c[A[j]]*c[A[i]]*(c[A[i]]-1)/2;
		}
	}
	long long m = (long long)c[0];
	wyn += m *(m-1 )*(m-2)/6;
    return wyn;
}
 
int main()
{
	ios_base::sync_with_stdio(0); cin.tie();cout.tie();
	int n, i, j ,suma = 0;
	cin >> n;
	if (n == 1) {
		cout << 0; return 0;
	}
	for(i = 0; i < n; i++){
		cin >> tab[i];
	}
	for(i = 0; i < n; i++){
		suma = 0;
		for(j = i; j < n; j++){
			suma += tab[j];
			//cout << suma <<" ";
			c[suma]++;
		}
	}
	
    int arr_size = c.size();
    s = new int [arr_size];
    if (arr_size == 1 && c.begin()->first == 0){
    	long long m = (long long)(n+1)*n/2;
		cout << m *(m-1 )*(m-2)/6 << endl;//kombinacje
	}
	/*
	else if (arr_size == 2 && c.begin()->first == 0){
    	n = (c.begin()->second+1)*(c.begin()->second)/2;
		cout << n *(n-1 )*(n-2)/6;//nie zajdzie
	}*/
    else{
    	i =0;
    	for(map <int, int>::iterator it = c.begin(); it != c.end(); it++){
    		s[i] = it-> first; i++;
    		//cout << it->first <<" " << it->second << endl;
		}
		//cout << indeks0 << endl;
		cout<<find3Numbers(s, arr_size, 0)<<endl;
	}
    
    
	//for(i = 0; i < arr_size;i++) cout << s[i] << " "; cout << endl;
    
    return 0;
}