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

using namespace std;

long long result[125'000];
void extendWithSubarraySums(const int nums[], int n) {
    int k = 0;
    // Dodajemy sumy wszystkich możliwych ciągów spójnych
    for (size_t start = 0; n > start; start++) {
        long long sum = 0;
        for (size_t end = start; end < n; end++) {
            sum += nums[end];
            result[k++] = sum;
        }
    }
}

long long ilosc = 0;
// Algorytm 3SUM
void zliczciagi(int n) {
    if(n == 1)
        return;
    sort(result, result + n);
    int Lm = 1;
    int mainIndex = 0;

    while(mainIndex < n - 1 && result[mainIndex] == result[mainIndex+1]){ //bierze ostatni index podciagu jednolitego
        mainIndex++;
        Lm++;
    }
    if(mainIndex == n - 1) {   //cala tablica w jednej cyfrze
        if(result[mainIndex] == 0) ilosc = n*(n-1)*(n-2)/6; //wzor na wybranie 3 indeksow z n
        return;
    }

    int Ll;
    int left;
    int Lr;
    int right;

    while (mainIndex < n - 2 && result[mainIndex]<=0) { //zawsze musi byc miejsce na pare, oraz min 1 liczba ujemna
        left = mainIndex + 1;
        Ll = 1;
        while(left < right-1 && result[left] == result[left+1]){    //right -1 aby nie nachodzily na siebie indexy
            left++;
            Ll++;
        }
        right = n - 1;
        Lr = 1;
        while (left +1 < right && result[right] == result[right - 1]) { //left +1 aby nie nachodzily na siebie indexy
            right--;
            Lr++;
        }
        while (left < right) {

            int sum = result[mainIndex] + result[left] + result[right];

            if (sum < 0){
                left++;
                Ll = 1;
                while(left < right-1 && result[left] == result[left+1]){
                    left++;
                    Ll++;
                }
            }
            else if (sum > 0){
                right--;
                Lr = 1;
                while (left +1 < right && result[right] == result[right - 1]) {
                    right--;
                    Lr++;
                }
            }
            else {  //znaleziono
                while (left < right-1 && result[left] == result[left + 1]) {
                    left++;
                    Ll++;
                }
                while (left +1 < right && result[right] == result[right - 1]) {
                    right--;
                    Lr++;
                }
                ilosc += Ll * Lr * Lm;  //dodajemy do ilosci wszystkie mozliwe trojpary indexow
                left++; // Aby uniknąć nieskończonej pętli, przesuwamy left i right
                Ll = 1;
                right--;
                Lr = 1;
            }
        }
        //kolejny indeks
        mainIndex++;
        Lm = 1;
        while(mainIndex < n - 1 && result[mainIndex] == result[mainIndex+1]){
            mainIndex++;
            Lm++;
        }
    }
}
int T[500];
int main() {
   int n;
   cin>>n;

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

   long long resMax = (n*(n+1))/2;

    extendWithSubarraySums(T,n); //maksymalny spojny podciag
    sort(result, result + resMax);

    zliczciagi(resMax);
    cout<<ilosc;
    return 0;
}