問題一覧 > 通常問題

No.1148 Dogu III

レベル : / AI推定難易度 : 800 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 79
作問者 : okazakisteve / テスター : SSRS
お気に入りにしたユーザー ProblemId : 4928 / 自分の提出
問題文最終更新日: 2020-08-05 17:58:39
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original

Problem Statement

$n$ dogu (clay figurines) are lined up in a row. Each dogu has a value called its "curse value". You now want to throw away some of the dogu. However, you will be cursed if the dogu you throw away include two or more dogu with the same curse value. You do not want to be cursed, so you must choose the dogu carefully. Note that the chosen dogu must be consecutive in the row.
You also want to throw away as many dogu as possible, but the total curse value of the dogu you throw away must not exceed $w$.
Find the maximum number of dogu you can throw away.

Input

$n\ w$
$a_1$
$a_2$
$\vdots$
$a_n$

$1 \leq n \leq 10^5$, $0 \leq w,a_i \leq 10^9$
All inputs are integers.

Output

Output the maximum number of dogu you can throw away.
Print a newline at the end.

Sample

Sample 1
Input
6 11
1
2
1
3
4
1
Output
4

You should throw away the four dogu 2,1,3,4.

Sample 2
Input
2 1
100
100
Output
0

You are destined to be cursed.

Sample 3
Input
20 155
20
18
15
10
20
16
18
11
14
12
12
19
13
17
15
13
12
13
15
20
Output
8

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。