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

constexpr int maxn = 507;
int n, uc[maxn], prefSum[maxn];
std::unordered_map<int, int> zlicz;

void input() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
        scanf("%d", uc + i);
}

void calcPrefSum() {
    prefSum[0] = uc[0];
    for(int i = 1; i < n; i++)
        prefSum[i] = prefSum[i - 1] + uc[i];
}
int sum(int l, int r) {
    if(l == 0)
        return prefSum[r];
    return prefSum[r] - prefSum[l - 1];
}

void calcZlicz() {
    for(int i = 0; i < n; i++)
        for(int j = i; j < n; j++)
            zlicz[sum(i, j)]++;
}

long long answer() {
    long long ans1 = 0, ans2 = 0, ans3 = 0;
    for(auto it1 = zlicz.begin(); it1 != zlicz.end(); it1++)
        for(auto it2 = it1; it2 != zlicz.end(); it2++) {
            auto [val1, occu1] = *it1;
            auto [val2, occu2] = *it2;
            auto val3 = -(val1 + val2);
            if(zlicz.find(val3) == zlicz.end())
                continue;
            auto occu3 = zlicz[val3];
            if(val1 == val2) {
                if(val1 == val3)
                    ans1 += occu1 * (occu1 - 1) * (occu1 - 2) / 6;
                else
                    ans2 += (occu1 * (occu1 - 1) / 2) * occu3;
            }
            else {
                if(val1 == val3)
                    ans2 += (occu1 * (occu1 - 1) / 2) * occu2;
                else if(val2 == val3)
                    ans2 += (occu2 * (occu2 - 1) / 2) * occu1;
                else
                    ans3 += occu1 * occu2 * occu3;
            }

        }
    return ans1 + ans2 / 2 + ans3 / 3;
}

/*#include <vector>
#include <random>
void gen(int seed) {
    std::mt19937 rnd(seed);
    n = 3;
//    std::cout << n << std::endl;
    for(int i = 0; i < n; i++) {
        uc[i] = rnd() % 11 - 5;
//        std::cout << uc[i] << ' ';
    }
//    std::cout << std::endl;
}

long long brut() {
    std::vector<int> buc;
    calcPrefSum();
    for(int i = 0; i < n; i++)
        for(int j = i; j < n; j++)
            buc.push_back(sum(i, j));
    long long ans = 0;
    int s = buc.size();
    for(int ii = 0; ii < s; ii++)
        for(int jj = ii + 1; jj < s; jj++)
            for(int kk = jj + 1; kk < s; kk++)
                ans += ((buc[ii] + buc[jj] + buc[kk]) == 0);
    return ans;
}*/

int main() {
    input();
    calcPrefSum();
    calcZlicz();
    printf("%lld", answer());
    /*return 0;
    for(int s = 0;;s++) {
        gen(s);
        zlicz.clear();
        calcPrefSum();
        calcZlicz();
        if(answer() != brut()) {
            std::cout << s << std::endl;
            return -1;
        }
        std::cout << s << ' ' << "OK" << std::endl;
    }*/
    return 0;
}