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
#include <iostream>
#include <cstdint>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define MAX 510
#define MAX_S1 (501*502/2)
#define MAX_S2 (20001*2*500)
#define ZERO_S2 (MAX_S2/2)

int64_t A[MAX],n;

int64_t result = 0;
int64_t S2[MAX_S2];

//int64_t Sa[MAX];
//int64_t Sa_ile = 0;

int64_t S2a[MAX_S1];
int64_t S2a_ile = 0;

int64_t S3a[MAX_S1];
int64_t S3a_ile = 0;
int64_t S3a_min[MAX_S1];
int64_t S3a_max[MAX_S1];

unordered_map<int64_t, int64_t> S1;

int64_t S1_ile = 0, Amin = 20001*500, Amax = -20001*500;

int main() {
    cin >> n;

    for(int i=0;i<n;i++) cin >> A[i];

    for(int ai=n-1;ai>=0;ai--) {
        //cout << "ai: " << A[ai] << "\n";
        S2a_ile++;
        for(int i=0;i<S2a_ile;i++) {
            S2a[i]+=A[ai];
            S3a[S3a_ile++] = S2a[i];
            if(Amin > S2a[i]) Amin = S2a[i];
            if(Amax < S2a[i]) Amax = S2a[i];
        }
    }

    S3a_min[S3a_ile] = 20001*500;
    S3a_max[S3a_ile] = -20001*500;
    for(int i=S3a_ile-1;i>=0;i--) {
        S3a_min[i] = min(S3a[i], S3a_min[i+1]);
        S3a_max[i] = max(S3a[i], S3a_max[i+1]);
    }

    S1.reserve(3*125250);

    for(int i=0;i<S3a_ile;i++) {
        //cout << "ai: " << A[ai] << "\n";
            int x = S3a[i];
            result+=S2[ZERO_S2-x];
            for(auto s1: S1) {
                int64_t v = s1.first+x;
                //if (v >=0 && v <MAX_S2) 
                if(v+S3a_min[i] > 0) continue;
                if(v+S3a_max[i] < 0) continue;    
                S2[v + ZERO_S2] += s1.second;
            }

            if(x+2*S3a_min[i] > 0) continue;
            if(x+2*S3a_max[i] < 0) continue;
            S1[x] += 1;
          //  cout << "S1: " << Sa[i] << "\n";
    }
    //for(int j=0;j<S1_ile;j++) cout << S1[j] << "\n";
//    cout << "SAlll:" << S2all.size() << "\n";
    cerr << "S1:" << S1.size() << "\n";
    cout << result << "\n";
}