5

시간 제한5초메모리 제한555 MB

요약

음이 아닌 정수 배열의 합이 S이고 1이 S/5 이상 들어 있을 때, 길이가 k이고 합이 T인 부분수열이 존재하는 (k, T) 쌍의 개수를 구합니다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 수학
정답자: 아직 제출이 없습니다

문제

길이가 $n$ 인 음이 아닌 정수로 이루어진 배열 $a$ 가 주어진다. 길이가 $k$ 이고 합이 $T$ 인 $a$ 의 부분수열이 존재하는 순서쌍 $(k, T)$ 의 개수를 구하라. 농담이다. 이 문제는 너무 일반적이다. 배열 원소의 합을 $S$ 라고 하면, $a$ 에는 값이 $1$ 인 원소가 적어도 $S/5$ 개 있다고 보장된다.

입력

첫째 줄에 양의 정수 $n$ 과 $S$ 가 주어진다 ( $1 \le n, S \le 2 \cdot 10^5$ ). 각각 $a$ 의 원소 개수와 원소의 합이다. 둘째 줄에 배열 $a_1, a_2, \ldots, a_n$ 이 주어진다 ( $0 \le a_i \le S$ ). 모든 $a_i$ 의 합은 $S$ 이고, $a$ 의 원소 중 적어도 $S/5$ 개는 $1$ 이다.

출력

조건을 만족하는 순서쌍 $(k, T)$ 의 개수를 출력한다.

예제4

예제 1
입력
```
7 9
0 0 0 1 1 2 5
```
예상 출력
```
42
```
예제 2
입력
```
10 33
9 9 8 1 1 1 1 1 1 1
```
예상 출력
```
48
```
예제 3
입력
```
10 14
2 4 4 1 0 1 0 1 0 1
```
예상 출력
```
81
```
예제 4
입력
```
10 14
3 5 3 0 1 0 1 0 1 0
```
예상 출력
```
87
```