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
 96
 97
 98
 99
100
101
102
103
104
105
106
#include <algorithm>
#include <iostream>
#include <vector>
#include <unordered_map>
#include <map>
#include <utility>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin>>n;
	if(n==1) {
		cout<<"0\n";
		return 0;
	}

	vector<int> in(n);
	unordered_map<int,int> h;
	//map<int,int> h;
	for(int i = 0; i < n; i++) {
		cin>>in[i];
	}
	int m = (n+1)*n/2;
	vector<int> r(m);
	int k = 0;
	for(int i = 0; i < n; i++) {
		r[k++] = in[i];
		for(int j = i+1; j < n; j++) {
			r[k] = r[k-1] + in[j];
			k++;
		}
	}
	for(const auto& i: r) {
		h[i]++;
	}
	//cout<<h.size()<<"\n";
	vector<pair<int,int>> num(h.begin(), h.end());
	sort(num.begin(), num.end());

	long long c = 0;

	if((num.size() == 1)&&(num[0].first == 0)) {
		c += 1LL * num[0].second* (num[0].second-1) * (num[0].second-2) / 6;

	}
	else if(num.size() == 2) {
		for(auto& i:{0,1}) {
			if((num[i].second >= 3) &&(num[i].first == 0)) {
				c += 1LL * num[i].second* (num[i].second-1) * (num[i].second-2) / 6;
			}
			if(num[i].second >= 2) {
				if(2*num[i].first + num[(i+1)%2].first == 0) {
					c += num[(i+1)%2].second;
				}
			}

		}
	}
	else {
		for(int i = 0; i < (int)num.size()-1; i++) {
			if(num[i].second >= 2){
				for(int j = i+1; j < (int)num.size(); j++) {
					if(2 * num[i].first + num[j].first == 0) {
						c += 1LL * num[i].second * (num[i].second-1) * num[j].second / 2;
					}
				}
			}
			for(int j = i+1; j < (int)num.size(); j++) {
				if(num[i].first + 2 * num[j].first == 0) {
					c += 1LL * num[j].second * num[j].second  * (num[j].second-1)/ 2;
				}
			}
		}
	
		for(int i = 0; i < (int)num.size()-2; i++) {
			if((num[i].second >= 3) &&(num[i].first == 0)) {
					c += 1LL * num[i].second* (num[i].second-1) * (num[i].second-2) / 6;
			}
			else {

				int j = i + 1;
				int k = (int)num.size() - 1;
				while(j < k) {
					if(num[i].first + num[j].first + num[k].first == 0) {
						c += 1LL * num[i].second * num[j].second * num[k].second;
						j++;
						k--;
					}
					else if(num[i].first + num[j].first + num[k].first > 0) {
						k--;
					}
					else
						j++;
				}
			}



		}
	}
	cout<<c<<"\n";
	return 0;
}