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
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i = a; i < b;++i)
#define pb emplace_back
#define mp make_pair
#define f first
#define s second
#define int long long
using namespace std;
const int prze = 1000 * 1000 * 20;
int tab[prze * 2];
int32_t main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n;
    cin>>n;
    vector<int> V;
    int max1 = 0,min1 = 0;
    vector<pair<int,int>> V1;
    FOR(i,0,n){
        int x;
        cin>>x;
        V.pb(x);
    }
    FOR(i,0,n){
        int suma = V[i];
        ++tab[suma + prze];
        max1 = max(max1,suma);
        min1 = min(min1,suma);
        FOR(j,i + 1,n){
            suma+=V[j];
            ++tab[suma + prze];
            max1 = max(max1,suma);
            min1 = min(min1,suma);
        }
    }
    min1 = max(min1,0 - (prze / 2));
    max1 = min(max1,prze / 2);
    FOR(i,prze + min1,prze + max1 + 1){
        if(tab[i] > 0){
            V1.pb(mp(i - prze,tab[i]));
        }
    }
    int wyn = 0,z1 = 0,wyn1 = 0;
    FOR(i,0,V1.size()){
        int x = tab[prze + V1[i].f];
        --tab[prze + V1[i].f];
        FOR(j,i,V1.size()){
            int w2 = 1;
            if(i == j && V1[i].f == 0){
                w2 = 2;
            }
            int y = max(tab[prze + V1[j].f],z1);
            --tab[prze + V1[j].f];
            int k = max(tab[prze - V1[i].f - V1[j].f],z1);
            wyn1+=((x * y * k) / w2);
            ++tab[prze + V1[j].f];
        }
        ++tab[prze + V1[i].f];
    }
    wyn1/=3;
    wyn+=wyn1;
    cout<<wyn;
}