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

using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n;
	cin >> n;

	vector<int> input(n);
	for (int i = 0; i < n; i++) {
		cin >> input[i];
	}

	vector<int> prefix_sums(n + 1);	
	for (int i = 0; i < n; i++) {
		prefix_sums[i + 1] = prefix_sums[i] + input[i];
	}

	unordered_map<int, long long> sums_1;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < i; j++) {
			sums_1[prefix_sums[i] - prefix_sums[j]]++;
		}
	}

	auto sums_copy = sums_1;

	long long res{};
	for (auto it = sums_1.begin(); it != sums_1.end(); it++) {
	    for (auto it2 = it; it2 != sums_1.end(); it2++) {
            if (it != it2 && ((it->first >= 0 && it2->first >= 0) || (it->first < 0 && it2->first < 0))) {
				res += (it->second * it2->second) * sums_copy[-it->first - it2->first];
			} else if (it == it2) {
				if (it->first == 0)
					res += ((it->second - 1) * (it2->second - 2)) * sums_copy[-it->first - it2->first] / 6;
				else
					res += ((it->second - 1) * (it2->second - 1)) * sums_copy[-it->first - it2->first];
			}
		}
	}

	cout << res << endl;

	return 0;
}