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

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;cin>>n;
    vector<int>in(n);
    for(int i = 0;i<n;++i){
        cin>>in[i];
    }
    vector<int>tab;
    int to_beg=0;
    for(int i = 0;i<n;++i){
        int temp_sum=to_beg;
        for(int j = i;j<n;++j){
            temp_sum+=in[j];
            tab.push_back(temp_sum-to_beg);
        }
        to_beg+=in[i];
    }
    int maks=n*40000;
    //vector<vector<int>>one(n*20000*2+1);
    vector<vector<pair<int,int>>>two(maks*2+9);
    for(int i = 0;i<tab.size();++i){
        //one[tab[i]].push_back(i);
        for(int j = i+1;j<tab.size();++j){
            //if(i==j)continue;
            two[maks+(tab[i]+tab[j])].push_back({i,j});
        }
    }
    /*for(int y : tab){
        cout<<y<<" ";
    }cout<<endl;
    int c = 0;
    for (vector<pair<int,int>>v : two){
        for(pair<int,int>p:v){
            cout<<c<<": "<<p.first<<" "<<p.second<<" "<<p.first+p.second<<" | ";
        }
        ++c;
        if(!v.empty())cout<<endl;
    }
    cout<<endl;*/
    long long ile=0;
    for(int i = 0;i<tab.size();++i){
        //cout<<-tab[i]+maks<<endl;
        for(int j = 0;j<two[-tab[i]+maks].size();++j){
            if(i!=two[-tab[i]+maks][j].first && i!=two[-tab[i]+maks][j].second){
                ++ile;
            }
        }
    }
    cout<<ile/3;
}