AT_arc100_c.[ARC100E] Or Plus Max

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一个长度为 $2^N$ 的整数序列 $A_0,\ A_1,\ ...,\ A_{2^N-1}$ 。（注意下标从 $0$ 开始）

对于所有满足 $1\leq K\leq 2^N-1$ 的整数 $K$ ，请解决以下问题：

设 $i,j$ 为整数，满足 $0\leq i<j\leq 2^N-1$ ，且 $(i\ \text{or}\ j)\leq K$ ，求 $A_i+A_j$ 的最大值。这里 $or$ 表示按位或运算。

输入格式

输入以以下格式从标准输入中给出。

$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
```

输入#2

3
10 71 84 33 6 47 23 25

输出#2

输入#3

4
75 26 45 72 81 47 97 97 2 2 25 82 84 17 56 32

输出#3

说明/提示

限制条件

$1\leq N\leq 18$
$1\leq A_i\leq 10^9$
所有输入均为整数。

样例解释 1

当 $K=1$ 时，可能的 $(i,j)$ 只有 $(0,1)$ ，所以答案为 $A_0+A_1=1+2=3$ 。
当 $K=2$ 时，可能的 $(i,j)$ 有 $(0,1),(0,2)$ 。当 $(i,j)=(0,2)$ 时， $A_i+A_j=1+3=4$ ，这是最大值，所以答案为 $4$ 。
当 $K=3$ 时，可能的 $(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$ 。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页