Subtask 1

We can check all ~\binom N 4~ tuples of ~(i, j, k, l)~ where ~i < j < k < l~, check if ~A_i + A_j + A_k = A_l~, and increment our total.

Time Complexity: ~\mathcal{O}(N^4)~

Subtask 2

Suppose we had an array ~\text{cnt}~ such that ~\text{cnt}[x][y]~ was equal to the number of indices ~l~ such that ~x < l~ and ~A[l] = y~. We can then iterate through all ~\binom N 3~ tuples of ~(i, j, k)~, and add ~\text{cnt}[k][A_i + A_j + A_k]~ to our total. We can compute ~\text{cnt}[x][y]~ using suffix sums.

Time Complexity: ~\mathcal{O}(N^3 + N \cdot \max A_i)~

Subtask 3

Welcome to another wleung_bvg editorial. As usual, he still does not know how to do dynamic programming and is bad at grammar, so please continue to bear with him. Note that it is possible to solve this problem without dynamic programming.

Suppose we processed elements from left to right and maintained an array ~\text{dp}~ with ~\text{dp}[i][y][z]~ equal to the number of increasing subsequences ending at or before index ~i~ with a length of ~y~ and a sum of ~z~. Then for each element, we can add ~\text{dp}[i - 1][3][A_i]~ to our total and update the ~\text{dp}~ array appropriately. We can update the ~\text{dp}~ array with the following recurrence:

~\text{dp}[i][y][z] = \begin{cases} \text{dp}[i - 1][y][z] + \text{dp}[i - 1][y - 1][z - A_i] & y \ge 1, z \ge A_i \\ \text{dp}[i - 1][y][z] & \text{otherwise} \end{cases}~

The initial state of the ~\text{dp}~ array is all elements equal to ~0~ with ~\text{dp}[0][0][0] = 1~. Note that we only need to consider ~y \le 3~ and ~z \le 100~ for this problem. While using this recurrence directly uses ~\mathcal{O}(N \cdot \max A_i)~ memory, it is possible to reduce it to ~\mathcal{O}(\max A_i)~.

Time Complexity: ~\mathcal{O}(N \cdot \max A_i)~