ARC226 B - Bin-ary Packing

考え方

最小重量ピッタリのサイズを持つ袋を用意したとして、その袋のサイズを分割して考える。
全ての荷物は重さが $2$ の累乗なので、袋のサイズを $2$ の累乗ごとに分割して考えてよい。

例えばサイズが $13$ の袋が $3$ つある場合は、サイズ $8,4,1$ の袋が $3$ つずつあると考えてよい。
ここに、重さ $2$ のものを $2$ つ入れる場合、$4$ の袋に入れればいいだけである。
全ての荷物は重さが $2$ の累乗なので、この処理方法ができなくなることはない。

よって、袋の最小サイズを求める問題は、以下のように読み替えられる。

• サイズが $2$ の累乗である袋を十分な枚数購入して、全ての荷物を収めたい
• サイズ $2^i$ の袋 $N$ 枚セットを、コスト $2^i$ 円で購入することができる
  • これは、真の袋サイズを $2^i$ 拡張したことに相当する
• サイズ $2^i$ の袋 $1$ 枚は、サイズ $2^{i-1}$ の袋 $2$ 枚と（再帰的に）みなして使用することができる
• 合計金額が最小にせよ

この言い換えさえできれば、荷物が重い方から順に、以下を実行すればよい。

• その荷物を入れられるだけの袋がなければ、追加購入する
• 荷物数と同じ数だけ袋を使用する
• 余った袋は、半分サイズの袋 $2$ 枚ということにする

各テストケースの計算量は $O(M)$。
全テストケースでは $O\left(\sum M\right)$。

入力例1での動作

入力例1の $1$ つ目のテストケースのみ考える。

入力を受け取る。

n: 2
m: 3
a: {3, 2, 1}

まず、重さ $2^2=4$ の荷物を考える。
荷物は $1$ 個だが、まだ重さ $4$ を入れられる空きはない。

そこで、サイズ $4$ の袋を $N=2$ 枚分追加する。
真の袋サイズは $4$ 増えるので、この時点で $4$ となる。
荷物を $1$ 個入れるとサイズ $4$ の空きが $1$ 枚分残り、これはサイズ $2$ の空き $2$ 枚分として使える。

次に、重さ $2^1=2$ の荷物を考える。
荷物は $2$ 個で、サイズ $2$ の空きも $2$ 枚分ある。
追加購入は必要なく、これらを使うと空きはなくなる。

最後に、重さ $2^0=1$ の荷物を考える。
荷物は $3$ 個だが、サイズ $1$ の空きはない。

サイズ $1$ の袋は $2$ 枚ずつ追加されるので、$2$ セット追加すればよい。
真の袋サイズはさらに $2$ 増えて $6$ となる。
サイズ $1$ の空き $4$ 枚分のうち $3$ 枚分を使えば、全ての荷物を入れられる。

したがって、答えは $6$ となる。

注意点

答えや、各サイズの袋として見た空き個数は int 型からはみ出る。
long long 型を用いること。

別解

特になし。