問題一覧 > 通常問題

No.1416 ショッピングモール

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 179
作問者 : harurunharurun / テスター : NatsubiSoganNatsubiSogan
2 ProblemId : 5664 / 出題時の順位表
問題文最終更新日: 2021-02-18 11:02:59

問題文

イギリス人のオリバー君は、ショッピングモールを建てる計画をしています。

このショッピングモールの $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もしくは右上の雲マークをクリックしてアカウントを作成してください。