| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 | 555 MB | 23 | 8 | 5 | 45.455% |
You are given an array $a$ of length $n$ consisting of non-negative integers. Calculate the number of pairs $(k, T)$ such that there exists a subsequence of $a$ of length $k$ whose sum is equal to $T$.
Just kidding, this is too general. Suppose the sum of elements of $a$ is equal to $S,ドル then it is guaranteed that $a$ has at least $S/5$ elements equal to 1ドル$.
The first line contains two positive integers $n$ and $S$ (1ドル \le n, S \le 2 \cdot 10^5$) --- the number of elements in $a$ and their sum.
The second line contains the array $a_1, a_2, \ldots, a_n$ (0ドル \le a_i \le S$). It is guaranteed that $\sum_{i=1}^{n} a_i = S$ and at least $S/5$ elements of $a$ are equal to 1ドル$.
Print the number of pairs $(k, T)$ such that there exists a subsequence of $a$ of length $k$ whose sum is equal to $T$.
7 9 0 0 0 1 1 2 5
42
10 33 9 9 8 1 1 1 1 1 1 1
48
10 14 2 4 4 1 0 1 0 1 0 1
81
10 14 3 5 3 0 1 0 1 0 1 0
87