問題一覧 > 通常問題

No.31 悪のミックスジュース

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 91
作問者 : LayCurseLayCurse
17 ProblemId : 3 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:47:45

問題文

ミックスジュースが切れました。
ミックスジュースの原材料の表示は、順番に、果物 1,果物 2,果物 N となっています。
既存のそれぞれの果物の100%ジュースを混ぜてミックスジュースを V リットルだけ作りたいです。
果物 k の100%ジュースは 1 リットルパックのみが売られていて、1 パックあたり Ck 円です。
V リットルのミックスジュースを、原材料の表示を変更することなく作るための、最小コストを求めるプログラムを書いてください。
つまり、ミックスジュースにおいて果物 k が占める割合 pkp1p2pN となる必要があり、更に、使われない果物があってもいけません。
1 リットルパックを買い、その一部のみを使用することも可能です。

入力

N V
C1 C2 ... CN

1 行目では、果物の種類数を表す整数 N (1N100) と作りたいミックスジュースの量を表す整数 V (1V109) が与えられます。
2 行目では、果物 k の100%ジュースの 1 リットルパックの値段を表す整数 Ck (1Ck109) が順番にスペース区切りで与えられます。

出力

最小のコスト(単位は円)を表す整数を 1 行で出力せよ。最後に改行すること。

サンプル

サンプル1
入力
3 10
1 100 100
出力
208

果物 18 リットル、果物 2,3 をそれぞれ 1 リットル混ぜるのが最適です。

サンプル2
入力
3 10
100 1 100
出力
604

果物 15 リットル、果物 24 リットル、果物 31 リットル混ぜるのが最適です。

サンプル3
入力
3 10
100 100 1
出力
703

果物 14 リットル、果物 23 リットル、果物 33 リットル混ぜるのが最適です。

サンプル4
入力
3 1
100 100 100
出力
300

例えば、3 つ全ての果物の 1 リットルパックを買い、果物 10.5 リットル、果物 20.3 リットル、果物 30.2 リットル混ぜるなどとすることができます。

サンプル5
入力
9 36
459473288 389234620 200824516 103210888 47314058 533584454 391380554 875989889 257188584
出力
10107195609

答えは 232 を超える可能性があることに注意してください。
果物 1,2 をそれぞれ 7 リットル、果物 3,4,5 をそれぞれ 6 リットル、果物 6,7,8,9 をそれぞれ 1 リットル混ぜるのが最適です。

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