問題一覧 > 通常問題

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

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

問題文

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

入力

\(N\) \(V\)
\(C_1\) \(C_2\) ... \(C_N\)

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

出力

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

サンプル

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

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

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

果物 \(1\) を \(5\) リットル、果物 \(2\) を \(4\) リットル、果物 \(3\) を \(1\) リットル混ぜるのが最適です。

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

果物 \(1\) を \(4\) リットル、果物 \(2\) を \(3\) リットル、果物 \(3\) を \(3\) リットル混ぜるのが最適です。

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

例えば、\(3\) つ全ての果物の \(1\) リットルパックを買い、果物 \(1\) を \(0.5\) リットル、果物 \(2\) を \(0.3\) リットル、果物 \(3\) を \(0.2\) リットル混ぜるなどとすることができます。

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

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

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