No.1148 Dogu III
タグ : / 解いたユーザー数 79
作問者 :
SSRS
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もしくは右上の雲マークをクリックしてアカウントを作成してください。