I - Prefix Or
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
長さ N の非負整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。 A の要素を自由に並び替えることができるとき、以下の値としてありうる最小値を求めてください。
\displaystyle \sum_{k=1}^N(A_1\lor A_2\lor\cdots\lor A_k)
ただし \lor はビット単位 \operatorname{OR} 演算を表します。
ビット単位 \operatorname{OR} 演算とは
非負整数 A,B に対するビット単位 \operatorname{OR} 演算 A\lor B は、以下のように定義されます。
- A\lor B を二進表記した際の 2^k\,(k\geq0) の位の数は、A,B を二進表記した際の 2^k の位の数のうち少なくとも一方が 1 であれば 1、そうでなければ 0 である。
例えば、3\lor5=7 となります(二進表記すると 010\lor101=111)。
制約
- 1 \le N \le 2\times 10^5
- 1 \le A_i \le 2\times 10^5
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N
出力
答えを出力せよ。
入力例 1
3 4 1 2
出力例 1
11
A を (1,2,4) に並べ替えると、(A_1)+(A_1\lor A_2)+(A_1\lor A_2\lor A_3)=1+3+7=11 となります。これが最小です。
入力例 2
3 2 5 6
出力例 2
15
A を (2,6,5) に並べ替えると、(A_1)+(A_1\lor A_2)+(A_1\lor A_2\lor A_3)=2+6+7=15 となります。これが最小です。
入力例 3
4 13 13 13 13
出力例 3
52
入力例 4
6 11 15 10 9 4 12
出力例 4
74