問題一覧 > 通常問題

No.2799 Cut and Eat

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 25
作問者 : noya2noya2 / テスター : shobonvipshobonvip 👑 potato167potato167
2 ProblemId : 11021 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-06-28 21:03:28

問題文

正整数 $N,K$ が与えられます。

机の上に $N$ 個のケーキがあり、 $i$ 番目のケーキの大きさは $A_i$ です。

Alice と Bob はこれからこのケーキを切って食べるゲームを行います。

Alice からはじめて交互に次の一連の操作を行います。

  • 机の上にあるケーキが存在しないとき、ゲームを終了する。
  • そうでないとき、机の上にあるケーキを $1$ つ選んで机の上から取り除く。このケーキの大きさを $S$ とする。
  • $S\le K$ のとき、このケーキを食べる。
  • $S\gt K$ のとき、整数 $x\ (1\le x\le S-1)$ を $1$ つ選ぶ。大きさが $x,S-x$ の $2$ つのケーキを新たに机の上に置く。

各々が自分がゲームを通じて食べるケーキの大きさの総和ができるだけ大きくなるように行動するとき、 Alice がゲームを通じて食べるケーキの大きさの総和を求めてください。

制約

  • 入力はすべて整数
  • $1\le N\le 100$
  • $1\le K\le 10^9$
  • $1\le A_i\le 10^9\ (1\le i\le N)$

入力

$N$ $K$
$A_1$ $A_2$ $\dots$ $A_N$

出力

答えを出力してください。

サンプル

サンプル1
入力
1 3
5
出力
2

ゲームの進行の一例を示します。

  • この時点で、机の上には大きさが $5$ のケーキがある。
  • Alice は大きさ $5$ のケーキを選んで机の上から取り除き、大きさが $2,3$ のケーキを新たに机の上に置く。
  • この時点で、机の上には大きさが $2,3$ のケーキがある。
  • Bob は大きさ $3$ のケーキを選んで机の上から取り除き、このケーキを食べる。
  • この時点で、机の上には大きさが $2$ のケーキがある。
  • Alice は大きさ $2$ のケーキを選んで机の上から取り除き、このケーキを食べる。
  • 机の上にあるケーキが存在しないので、ゲームを終了する。

ゲームを通して Alice が食べたケーキの大きさの総和は $2$ です。

サンプル2
入力
4 10
1 2 3 4
出力
6

サンプル3
入力
6 28
62 8 628 6 28 628
出力
693

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