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
/*
 * =====================================================================================
 *
 *       Filename:  buc.cpp
 *
 *    Description:  https://sio2.mimuw.edu.pl/c/pa-2024-1/p/buc/
 *
 *        Version:  0.1.0
 *        Created:  15.03.2024
 *
 *         Author:  Michał Zagórski (zagura), <zagura6@gmail.com>
 *
 * =====================================================================================
 */

#include <cstdio>
#include <vector>
#include <list>
#include <unordered_map>

using std::vector;
using std::list;
using std::unordered_map;

int main() {
    int len = 0;
    scanf("%d", &len);
    vector<int> nums {};
    nums.reserve(len);
    for (int i = 0; i < len; i++) {
        int c;
        scanf("%d", &c);
        nums.push_back(c);
    }
    vector<long long int> sums;
    unordered_map<long long int, list<size_t>> ids {};
    long long int current_sum = 0;
    for (int i = 0; i < len; i++) {
        current_sum = 0;
        for (int j = i; j < len; j++) {
            current_sum += nums[j];
            sums.push_back(current_sum);
            ids[current_sum].push_back(sums.size() - 1);
        }
    }
    //for (const auto& el: sums) {
    //    printf("%lld ", el);
    //}
    //printf("\n");
    unsigned long long int totals = 0;
    for (int i = 0; i < sums.size() - 2; i++) {
        long long int sum = 0;
        for (int j = i + 1; j < sums.size() - 1; j++) {
            sum = sums[i] + sums[j];
            auto it = ids.find((-1) * sum);
            if (it != ids.end()) {
                list<size_t>& l = it->second;
                auto current = l.begin();
                for (size_t k = 0; k < l.size(); k++) {
                    if (*current > j) {
                        totals += (l.size() - k);
                        break;
                    }
                    ++current;
                }
            }
        }
    }
    printf("%llu\n", totals);
    return 0;
}