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
107
108
109
110
111
112
113
114
115
116
#include<bits/stdc++.h>
using namespace std;

const int n_max = 500 * 500 + 7;
const int n_max_2 = 20000 * 500 + 7;
long long tab_plus[n_max_2];
long long tab_minus[n_max_2];

int tab[n_max];


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> tab[i];
    }
    vector<int> plus_first;
    vector<int> minus_first;


    long long zeros = 0;
    // Powstawanie elemntow
    for(int i = 0; i < n; i++){
        int sum = 0;
        for(int j = i; j < n; j++){
            sum += tab[j];
            if(sum > 0){
                tab_plus[sum]++;
                if(tab_plus[sum] != 1){
                    continue;
                }
                plus_first.push_back(sum);
            }
            if(sum < 0){
                tab_minus[-1 * sum]++;
                if(tab_minus[-1 * sum] != 1){
                    continue;
                }
                minus_first.push_back(sum);
            }
            if(sum == 0){
                zeros++;
            }
        }
    }
    long long ans = zeros * (zeros - 1) * (zeros - 2) / 6;
    if(plus_first.empty() or minus_first.empty()){
        cout << ans << '\n';
        return 0;
    } 
 
    tab_plus[0] = zeros;
    tab_minus[0] = zeros;
    sort(plus_first.begin(), plus_first.end());
    sort(minus_first.begin(), minus_first.end());

    reverse(plus_first.begin(), plus_first.end());
    plus_first.push_back(0);
    minus_first.push_back(0);
    int id_plus_begin = 0;
    int id_minus_begin = 0;
    while(plus_first[id_plus_begin] != 0 or minus_first[id_minus_begin] != 0){
        if(plus_first[id_plus_begin] >= -1 * minus_first[id_minus_begin]){
            // Obsluda plusa
 
            int base = plus_first[id_plus_begin];
            int s = minus_first.size() - 1;
            for(int i = id_minus_begin; i < s; i++){
                int tmp = minus_first[i];
                int left = base + tmp;
                if(-1 * left == tmp){
                    ans = ans + tab_plus[base] * tab_minus[-1 * tmp] * (tab_minus[-1 * tmp] - 1) / 2; 
                    continue;
                }
                if(-1 * left < tmp){
                    break;
                }
                if(tab_minus[left] == 0){
                    continue;
                }
                ans = ans + tab_plus[base] * tab_minus[-1 * tmp] * tab_minus[left]; 
            }
            id_plus_begin++;

        }else{
            // Obsluga minusa

            int base = minus_first[id_minus_begin];
            int s = plus_first.size() - 1;
            for(int i = id_plus_begin; i < s; i++){
                int tmp = plus_first[i];
                int left = base + tmp;
                left *= -1;
                if(left == tmp){
                    ans = ans + tab_minus[-1 * base] * tab_plus[tmp] * (tab_plus[tmp] - 1) / 2; 
                    continue;
                }
                if(left > tmp){
                    break;
                }
                if(tab_plus[left] == 0){
                    continue;
                }
                ans = ans + tab_minus[-1 * base] * tab_plus[tmp] * tab_plus[left]; 
            }
            id_minus_begin++;
        }
    }
    cout << ans << '\n';


    return 0;
}