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
#include <bits/stdc++.h>
using namespace std;
const int OFF=500*20'000*3;
int mapa[501*20'000*3*2];
int main()
{
	int n; cin>>n;
	vector<int>a(n+1);
	//~ mt19937 rng(0); uniform_int_distribution<>los(-20'000, 20'000);
	for (int i=1; i<=n; i++) cin>>a[i], a[i]+=a[i-1];
	long long ans=0;
	for (int i=1; i<=n; i++)
		for (int j=1; j<=i; j++)
		{
			if (a[i]-a[j-1]==0)
				ans+=2;
			mapa[OFF+a[i]-a[j-1]]++;
		}
	//~ cout<<ans<<endl;
	for (int i=1; i<=n; i++)
		for (int j=1; j<=i; j++)
			ans-=3*mapa[OFF-2*(a[i]-a[j-1])];
	//~ cout<<ans<<endl;
	for (int i=1; i<=n; i++)
	{
		for (int j=1; j<=n; j++)
			for (int l=1; l<=j; l++)
				ans+=mapa[OFF-(a[j]-a[l-1]+a[i])];
		for (int j=1; j<=n; j++)
			for (int l=1; l<=j; l++)
				mapa[OFF+a[j]-a[l-1]-a[i]]++;
	}
	cout<<ans/6<<"\n";
}