No.1416 ショッピングモール
タグ : / 解いたユーザー数 241
作問者 : harurun / テスター : NatsubiSogan
問題文
イギリス人のオリバー君は、ショッピングモールを建てる計画をしています。
このショッピングモールの $k\ (k \geq 0)$ 階には、最大で $2^k$ 軒の店が入ることのできるスペースがあります。
さて、これからこのショッピングモールに $n$ 軒の店が入る予定で、$i\ (1 \leq i \leq n)$ 番目の店には $A_i$ 人の店員がやってきます。
ここで、それぞれの店の コスト を以下のように定義します。
- $i$ 番目の店が $F_i\ (F_i \geq 0)$ 階にあるとしたとき、その コスト $C_i$ は $A_i \times F_i$
オリバー君は、すべての店の コスト の合計 $\displaystyle \sum_{i=1}^{n} C_i$ が最小となるように店を配置します。
この コスト の合計の最小値を求めてください。階の数え方が $1$ 階から始まっていないことに注意してください。
入力
$n$ $A_1\ A_2\ \ldots \ A_n$
1 行目には店の数 $n$ が与えられる。
2 行目には $A_1,\ A_2,\ \cdots ,\ A_n$ が空白区切りで与えられる。
制約
- 入力はすべて整数
- $1 \leq n \leq 5 \times 10^4$
- $1 \leq A_i \leq 10^3$
出力
コストの合計の最小値を出力してください。
最後に改行してください。
サンプル
サンプル1
入力
3 1 2 3
出力
3
$0$ 階に $3$ 人の店を配置し、 $1$ 階に $1$ 人の店と $2$ 人の店を配置すればよいです。
よって、求める値は $(3 \times 0) + (1 \times 1) + (2 \times 1) = 3$ となります。
サンプル2
入力
1 1
出力
0
サンプル3
入力
15 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000
出力
34000
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。