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

using namespace std;

int n;
int tab[MAXN];
int sub[MAXN][MAXN];
map<int, vector<short> > sum;
map<int, vector<short> > sum2;
map<int, int> sum3;
long long w1, w2, w3;

int main() {
	
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	w1 = w2 = w3 = 0;
	
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> tab[i];
		sub[i][i] = tab[i];
	}
	
	if(n == 1) {
		cout<<0<<"\n";
		return 0;
	}
	
	if(n == 2) {
		cout<<(tab[0] == -tab[1])<<"\n";
		return 0;
	}
	
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			sub[i][j] = sub[i][j - 1] + tab[j];
		}
	}
	
	for (int k = 0; k < n; k++) {
		for (int i = 0; i < n; i++) {
			for (int j = i; j < n; j++) {
				sum[sub[i][j] + sub[k][n - 1]].push_back(k);
				sum2[sub[k + 1][n - 1] - sub[i][j]].push_back(k);
			}
		}
	}
	
	for (int i = 0; i < n; i++) {
		for (int j = i; j < n; j++) {
			sum3[sub[i][j] << 1]++;
			if (sub[i][j] == 0) {
				w3++;
			}
		}
	}
	
	for (pair<int, vector<short> > e : sum) {
		vector<short> left = e.second;
		vector<short> right = sum2[e.first];
		
		int j = 0;
		for (int i = 0; i < left.size(); i++) {
			while(j < right.size() && left[i] > right[j]) {
				j++;
				if(j == right.size()) {
					goto g;
				}
			}
			w1 += right.size() - j;
		}
		g:
		continue;
	}
	
	for (int i = 0; i < n; i++) {
		for (int j = i; j < n; j++) {
			w2 += sum3[-sub[i][j]];
		}
	}
	cout<<(w1 - 3 * w2 + 2 * w3) / 6<<"\n";
	
	return 0;
}