問題一覧 > 通常問題

No.1454 ツブ消ししとるなEasy

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 151
作問者 : sushitoruna / テスター : oliverx3 MtSaka
1 ProblemId : 6082 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-03-31 12:35:30

問題文

寿司取るな君は Tbutter という SNS を利用しています.
現在, 寿司取るな君のツブート数は N です. また, 寿司取るな君の i ツブート目のいいね数は Ai です. ツブ廃になりたくない寿司取るな君は, ツブ消しをすることでツブート数を M 以下にすることにしました.
ただツブ消しするだけではつまらないので, 寿司取るな君は残ったツブートのいいね数の和を最大化しようと思いました.
寿司取るな君は, いいね数が Y 以下のツブートはつまらないので必ず消します. いいね数が X 以上のツブートは面白いので消すことはできません. その他のツブートについては, 消すか消さないかを自由に決められます.
残ったツブートのいいね数の和の最大値を求めてください. ただし, どのようにツブ消しをしてもツブート数を M 以下にできない場合は Handicapped と出力してください.

入力

N M X Y
A1 A2 A3 ...AN

制約
1MN105
0Y<X105
0Ai105 (1iN)
入力は全て整数

出力

寿司取るなくんがツブート数を 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もしくは右上の雲マークをクリックしてアカウントを作成してください。