AtCoder Regular Contest E

Time limit : 2sec / Memory limit : 1024MB

Score : 700 points

Problem Statement

There is an integer sequence of length 2N: A0,A1,…,A2N−1. (Note that the sequence is 0-indexed.)

For every integer K satisfying 1≤K≤2N−1, solve the following problem:

Let i and j be integers. Find the maximum value of Ai+Aj where 0≤i<j≤2N−1 and (i or j)≤K. Here, or denotes the bitwise OR.

Constraints

1≤N≤18
1≤Ai≤109
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N

A0 A1 … A2N−1

Output

Print 2N−1 lines. In the i-th line, print the answer of the problem above for K=i.

Sample Input 1

Copy

2

1 2 3 1

Sample Output 1

Copy

For K=1, the only possible pair of i and j is (i,j)=(0,1), so the answer is A0+A1=1+2=3.

For K=2, the possible pairs of i and j are (i,j)=(0,1),(0,2). When (i,j)=(0,2), Ai+Aj=1+3=4. This is the maximum value, so the answer is 4.

For K=3, the possible pairs of i and j are (i,j)=(0,1),(0,2),(0,3),(1,2),(1,3),(2,3) . When (i,j)=(1,2), Ai+Aj=2+3=5. This is the maximum value, so the answer is 5.

Sample Input 2

Copy

3

10 71 84 33 6 47 23 25

Sample Output 2

Copy

Sample Input 3

Copy

4

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

Sample Output 3

Copy

101

120

147

156

156

178

194

194

194

194

194

194

194

194

194
要求max(Ai+Aj) (0≤i<j≤2N−1 && i|j≤k)，显然i <= k && j <= k,只要求max(Ai+Aj) (0≤i<j≤2N−1 && i|k=k && j|k=k),然后，就可以得出想要的结果，i|k=k说明i是在k的基础上二进制位中的0保持不变，改变1，把1变为0，则i < k,
这样求前缀，然后排着往后更新最大值即可。
代码：

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <algorithm>

#define Max 1 << 19

using namespace std;

int n,e,s[Max];

int r[Max][];///记录最大值下标

bool cmp(int a,int b){

    return s[a] < s[b];

}

int main(){

    scanf("%d",&n);

    e =  << n;///总数个数

    for (int i = ;i < e;i ++)

        scanf("%d",&s[i]);

    s[e] = -;

    r[][] = ;///初始化

    r[][] = e;

    for (int i = ;i < e;i ++){

        r[i][] = i;///初始化

        r[i][] = e;

        int x[];

        for (int j = ;j < n;j ++)

            if (i & ( << j)){///此位为1

                int d = i ^ ( << j);///把这位变成0 对于d的情况前面已经确定过 这里直接用

                x[] = r[i][];

                x[] = r[i][];

                x[] = r[d][];

                x[] = r[d][];

                sort(x,x + ,cmp);///按照对应位置值从小到大排列下标

                r[i][] = x[];///存最大值下标

                r[i][] = x[] == x[] ? x[] : x[];///存非重复下标

            }

    }

    int ans = ;

    for (int i = ;i < e;i ++){

        ans = max(ans,s[r[i][]] + s[r[i][]]);///前缀更新i的最大值

        printf("%d\n",ans);

    }

    return ;

}

巴特西

AtCoder Regular Contest E - Or Plus Max

Problem Statement

Constraints

Input

Output

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

最新文章

热门文章