P10366 [PA 2024] Bardzo Ulubiony Ciąg

PA 2024 5C1

**This problem is translated from Round 5 of [PA 2024](https://sio2.mimuw.edu.pl/c/pa-2024-1/dashboard/), [Bardzo Ulubiony Ciąg](https://sio2.mimuw.edu.pl/c/pa-2024-1/p/buc/). Thanks to Macaronlin for providing the translation.** Given an integer array $a$ of length $n$, all subarray sums of $a$ form an array $b$ of length $\frac{n(n+1)}{2}$. The subarray sums are ordered by increasing starting index of the subarray; if two subarrays have the same starting index, they are ordered by increasing ending index. For the newly formed array $b$, compute the number of triples $(i,j,k)$ such that $b_i+b_j+b_k=0\ (i

The first line contains an integer $n\ (1\le n\le 500)$, the length of array $a$. The second line contains $n$ integers $a_1,a_2,\ldots,a_n\ (|a_i|\le 20\,000)$, representing array $a$.

Output one integer: the number of triples $(i,j,k)$ in array $b$ satisfying $b_i+b_j+b_k=0\ (i

**Sample Explanation 1** Array $b$ is $[7,3,1,-4,-6,-2]$. Only the three distinct elements $3,1,-4$ satisfy the condition, so the answer is $1$. **Sample Explanation 2** Array $b$ consists of $55$ zeros. Any choice of three indices $i