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

int main() 
{
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(NULL);    
  uint16_t n;
  std::cin >> n;
  std::vector<int16_t> a(n);
  for (uint16_t i = 0; i < n; i++)
    std::cin >> a[i];
  std::vector<std::vector<int32_t> > sum(n + 1); 
  // Dynamik: sum[s][i] - suma elementów a[i .. i+s-1]
  sum[1].resize(n);
  for (uint16_t i = 0; i < n; i++)
    sum[1][i] = a[i];
  for (uint16_t s = 2; s <= n; s++)
  {
    int i_max = n - s;
    sum[s].resize(i_max + 1);
    for (uint16_t i = 0; i <= i_max; i++)
      sum[s][i] = sum[s - 1][i] + a[i + (s - 1)];
  }
  uint32_t uc_size = n * (n + 1) / 2;
  std::vector<int32_t> uc(uc_size);
  uint32_t j = 0;
  for (uint16_t i = 0; i < n; i++)
    for (uint16_t s = 1; s <= n - i; s++, j++)
      uc[j] = sum[s][i];
  // Na razie brut, bo znalezione algorytmy 3SUM dają złe wyniki dla drugiego 
  // z przykładów (np. ten quadratic 3SUM z angielskiej wikipedii).
  // Być może eliminują powtarzające się wyniki.
  // A jak to są Ulubione Ciągi Bajtka, to może niech on sobie sam policzy?
  uint32_t result = 0;
  for (uint32_t i = 0; i < uc_size - 2; i++)
    for (uint32_t j = i + 1; j < uc_size - 1; j++)
      for (uint32_t k = j + 1; k < uc_size; k++)
        if (uc[i] + uc[j] + uc[k] == 0)
          result++;   
  std::cout << result << "\n";                  
  // system("pause");
}