No.2492 Knapsack Problem?
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 227
作問者 : KumaTachiRen / テスター : hiro1729
タグ : / 解いたユーザー数 227
作問者 : KumaTachiRen / テスター : hiro1729
問題文最終更新日: 2023-10-02 17:19:55
問題文
Alice はナップサックを買いにナップサック屋さんに来ました. ナップサック屋さんでは 個のナップサックが売られており, 個目のナップサックは容量 ,重さ です.
Alice はできるだけ容量が大きく,なおかつ重すぎないナップサックが欲しいと思っています.
重さ 以下のナップサックのうち容量が最大であるものの容量を求めてください.
ただし重さ 以下のナップサックが存在しない場合は-1
を出力してください.
入力
- 入力はすべて整数
出力
重さ 以下のナップサックが存在するならばそれらの中での容量の最大値を,存在しないならば-1
を出力してください.
最後に改行してください.
サンプル
サンプル1
入力
3 7 6 9 3 3 5 6
出力
5
重さが 以下であるのは 個目のナップサックであり,それらの中での容積の最大値は 個目のナップサックの です.
サンプル2
入力
3 14 1 59 2 65 3 58
出力
-1
重さが 以下であるナップサックが存在しないので-1
を出力してください.
サンプル3
入力
10 414 851 708 305 850 438 421 245 191 409 476 764 490 159 386 350 505 531 42 292 822
出力
531
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。