分数: 700 点
问题陈述
存在一个长度为整数的序列 2^N: A_0, A_1, ..., A_{2^N-1}。 (注意顺序是 0- 已索引。)
对于每个整数 K 满意 1 \leq K \leq 2^N-1,解决以下问题:
- 让 i 和 j 是整数。找到最大值 A_i + A_j 其中 0 \leq i < j \leq 2^N-1 和 (i or j) \leq K。 在这里, or 表示按位或。
约束
- 1 \leq N \leq 18
- 1 \leq A_i \leq 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N
A_0 A_1 ... A_{2^N-1}
输出
打印 2^N-1 行。 在 i第行,打印上面问题的答案 K=i.
示例输入 1
2 1 2 3 1
示例输出 1
3 4 5
对于 K=1,唯一可能的对 i 和 j is (i,j)=(0,1),所以答案是 A_0+A_1=1+2=3.
对于 K=2,可能的对 i 和 j 是 (i,j)=(0,1),(0,2)。 当 (i,j)=(0,2), A_i+A_j=1+3=4。这是最大值,所以答案是 4.
对于 K=3,可能的对 i 和 j 是 (i,j)=(0,1),(0,2),(0,3),(1,2),(1,3),(2,3) 。 当 (i,j)=(1,2), A_i+A_j=2+3=5。这是最大值,所以答案是 5.
示例输入 2
3 10 71 84 33 6 47 23 25
示例输出 2
81 94 155 155 155 155 155
示例输入 3
4 75 26 45 72 81 47 97 97 2 2 25 82 84 17 56 32
示例输出 3
101 120 147 156 156 178 194 194 194 194 194 194 194 194 194