No.1858 Gorgeous Knapsack
タグ : / 解いたユーザー数 58
作問者 :
Shirotsume
/ テスター :
👑 
potato167
問題文
$N$ 個の宝石があります。それぞれの宝石には $1, 2, 3, \dots, N$ の番号が付けられており、宝石 $i$ $(1 \leq i \leq N)$ の美しさは $V_i$、 重さは $W_i$ です。
あなたは、これらの宝石から $0$ 個以上選び、ナップサックに入れることにしました。ナップサックの容量は $M$ で、ナップサックに入れる宝石の重さの合計は $M$ 以下でなければいけません。
ここで、ナップサックの 豪華さ $G$ を以下のように定義します。
- $G =$ (ナップサックに入っている宝石の美しさの最小値) $\times$ (ナップサックに入っている宝石の美しさの総和)
ただし、ナップサックに入っている宝石が $0$ 個のときの豪華さは $0$ とします。
うまくナップサックに入れる宝石を決めたとき、豪華さ $G$ の最大値はいくらになりますか？
制約
- 入力は全て整数
- $1 \leq N \leq 5000$
- $1 \leq M \leq 5000$
- $1 \leq V_i \leq 10^6$ ($1 \leq i \leq N$)
- $1 \leq W_i \leq 5000$ ($1 \leq i \leq N$)
入力
入力は以下の形式で標準入力から与えられる。$N$ $M$ $V_1$ $W_1$ $V_2$ $W_2$ $\vdots$ $V_N$ $W_N$
出力
ナップサックに宝石を入れたときの豪華さとして考えられる最大値を出力せよ。最後に改行すること。
サンプル
サンプル1
入力
4 30 10 8 1 6 5 11 10 3
出力
200
宝石 $1, 4$ をナップサックに入れると、ナップサックに入っている宝石の重量の総和は $11$ で、美しさの総和は $20$ 、最小値は $10$ となり、豪華さは $10 \times 20 = 200$ となります。
豪華さをこれ以上大きくすることはできません。
サンプル2
入力
5 25 11 11 13 3 2 7 1 3 9 7
出力
297
宝石 $1, 2, 5$ をナップサックに入れると、重さの総和は $21$、美しさの総和は $33$、美しさの最小値は $9$ となり、豪華さは $9 \times 33 = 297$ となります。
サンプル3
入力
5 1 100 1000 100 1000 100 1000 100 1000 100 1000
出力
0
どの宝石もナップサックの容量よりも重く、入れることができません。よって、豪華さの最大値は $0$ となります。
サンプル4
入力
25 2297 869446 1904 287909 1874 935730 2781 119975 1981 705677 929 644024 851 997269 2313 302869 939 383338 500 744220 2133 442205 1952 546991 401 792852 732 784709 539 250917 1101 922704 2274 399156 1435 844960 1077 603700 1992 276715 242 53425 691 791544 2432 949488 2471 181585 2153 329429 2118
出力
1611228542126
豪華さは32bit整数に収まらない場合があります。注意してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。