No.1454 ツブ消ししとるなEasy
タグ : / 解いたユーザー数 141
作問者 :
sushitoruna
/ テスター :
oliverx3
MtSaka
問題文
寿司取るな君は $Tbutter$ という SNS を利用しています.
現在, 寿司取るな君のツブート数は $N$ です. また, 寿司取るな君の $i$ ツブート目のいいね数は $A_i$ です. ツブ廃になりたくない寿司取るな君は, ツブ消しをすることでツブート数を $M$ 以下にすることにしました.
ただツブ消しするだけではつまらないので, 寿司取るな君は残ったツブートのいいね数の和を最大化しようと思いました.
寿司取るな君は, いいね数が $Y$ 以下のツブートはつまらないので必ず消します. いいね数が $X$ 以上のツブートは面白いので消すことはできません. その他のツブートについては, 消すか消さないかを自由に決められます.
残ったツブートのいいね数の和の最大値を求めてください. ただし, どのようにツブ消しをしてもツブート数を $M$ 以下にできない場合は Handicapped と出力してください.
入力
$N\ M\ X\ Y$ $A_1\ A_2\ A_3\ ... A_N$
制約
$1 ≤ M ≤ N ≤ 10^5$
$0 ≤ Y < X ≤ 10^5$
$0 ≤ A_i ≤ 10^5$ ($1 ≤ i ≤ N$)
入力は全て整数
出力
寿司取るなくんがツブート数を $M$ 以下に
・できない場合はHandicappedを
・できる場合は残ったツブートのいいね数の合計の最大値を
それぞれ $1$ 行に出力してください.最後に改行してください.
サンプル
サンプル1
入力
9 6 7 2 1 3 2 5 4 7 6 8 9
出力
39
$6$ , $8$ , $9$ ツブート目のツブートは, $7$ いいね以上なので, 必ず残さなければなりません.
また, $1$ , $3$ ツブート目のツブートは, $2$ いいね以下なので, 必ず削除しなければなりません.
これを満たす, いいね数の合計が最大になる例は $1$ , $2$ , $3$ ツブート目を削除した例です.
サンプル2
入力
5 2 3 0 0 4 3 6 100
出力
Handicapped
$1$ ツブート目を除いては必ず残さなくてはならないので, $2$ ツブート以下にすることはできません.
サンプル3
入力
6 3 6 3 2 3 3 100 1 1
出力
100
必ず消さなくてはならないツブートが多い場合に注意して下さい.
サンプル4
入力
5 2 3 2 1 2 1 2 1
出力
0
全てのツブートを消す場合のいいね数の合計は $0$ です.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。