Problem:


Score : 700 points

Problem Statement

There is an integer sequence of length 2^N: A_0, A_1, ..., A_{2^N-1}. (Note that the sequence is 0-indexed.)

For every integer K satisfying 1 \leq K \leq 2^N-1, solve the following problem:

Let i and j be integers. Find the maximum value of A_i + A_j where 0 \leq i < j \leq 2^N-1 and (i or j) \leq K.
Here, or denotes the bitwise OR.

Constraints

1 \leq N \leq 18

1 \leq A_i \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_0 A_1 ... A_{2^N-1}

Output

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

Sample Input 1

2
1 2 3 1

Sample Output 1

3
4
5

For K=1, the only possible pair of i and j is (i,j)=(0,1), so the answer is A_0+A_1=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), A_i+A_j=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), A_i+A_j=2+3=5. This is the maximum value, so the answer is 5.

Sample Input 2

3
10 71 84 33 6 47 23 25

Sample Output 2

81
94
155
155
155
155
155

Sample Input 3

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

Sample Output 3

101
120
147
156
156
178
194
194
194
194
194
194
194
194
194



Sample input:
2
1 2 3 1


Sample output:
3
4
5

Submission status: Wrong Answer

Solution code:
def max2(a, b, c, d):
    vals = sorted((a, b, c, d), reverse=True)
    return vals[0], vals[1]


n = int(input())
a = list(map(int, input().split()))

dp = [[0] * (1 << n) for i in range(n + 1)]
dq = [[0] * (1 << n) for i in range(n + 1)]
for i in range(1 << n):
    dp[0][i] = a[i]

for i in range(n):
    for bit_state in range(1 << n):
        if (1 << i) & bit_state:
            first, second = max2(dp[i][bit_state], dq[i][bit_state], dp[i][bit_state ^ (1 << i)], dq[i][bit_state ^ (1 << i)])
        else:
            first, second = dp[i][bit_state], dq[i][bit_state]
        dp[i + 1][bit_state], dq[i + 1][bit_state] = first, second
        
for i in range((1 << n) - 1):
    dp[-1][i + 1] = max(dp[-1][i + 1], dp[-1][i])
    dq[-1][i + 1] = max(dq[-1][i + 1], dq[-1][i])
# print(dp[-1])
# print(dq[-1])

for i in range(1, 1 << n):
    print(dp[-1][i] + dq[-1][i])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
zeta = a[: ]
zeta2 = [0] * (1 << N)
for i in range(N):
  for j in range(1 << N):
    if (1 << i) & j:
      if zeta[j] < zeta[(1 << i) ^ j]:
        zeta2[j] = max(zeta[j], zeta2[(1 << i) ^ j])
        zeta[j] = zeta[(1 << i) ^ j]
      elif zeta2[j] < zeta[(1 << i) ^ j]:
        zeta2[j] = zeta[(1 << i) ^ j]

for i in range((1 << N) - 1):
  zeta[i + 1] = max(zeta[i + 1], zeta[i])
  zeta2[i + 1] = max(zeta2[i + 1], zeta2[i])
#print(zeta, zeta2)
for i in range(1, 1 << N): print(zeta[i] + zeta2[i])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
zeta = a[: ]
zeta2 = [0] * (1 << N)
for i in range(N):
  for j in range(1 << N):
    if (1 << i) & j:
      if zeta[j] < zeta[(1 << i) ^ j]:
        zeta2[j] = zeta[j]
        zeta[j] = zeta[(1 << i) ^ j]
      elif zeta2[j] < zeta[(1 << i) ^ j]:
        zeta2[j] = zeta[(1 << i) ^ j]

for i in range((1 << N) - 1):
  zeta[i + 1] = max(zeta[i + 1], zeta[i])
  zeta2[i + 1] = max(zeta2[i + 1], zeta2[i])
#print(zeta, zeta2)
for i in range(1, 1 << N): print(zeta[i] + zeta2[i])

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
data=[[] for i in range(2**N)]
data[0]=[0,0]
if A[1]>A[0]:
    data[1]=[1,0]
else:
    data[1]=[0,1]
ans=[0]*2**N
ans[1]=sum(A[0:2])
for i in range(2,2**N):
    ans[i]=ans[i-1]
    h=[[A[i],i]]
    for j in range(N):
        if i&(1<<j)==0:
            continue
        else:
            kkk=i^(1<<j)
            num=data[kkk][0]
            uuu=[A[num],num]
            if not uuu in h:
                h.append(uuu)
            num=data[kkk][1]
            uuu=[A[num],num]
            if not uuu in h:
                h.append(uuu)
    h.sort(reverse=True)
    if h[0][0]+h[1][0]>ans[i]:
        ans[i]=h[0][0]+h[1][0]
        data[i]=[h[0][1],h[1][1]]
    else:
        data[i]=data[i-1][:]
for i in range(1,2**N):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
print("I cannot solve this.")

Submission status: Wrong Answer

Solution code:
import itertools
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353
def cummax(it, first=-float('inf')):
    """
    np.maximum.accumulate(arr) でもよさそう
    https://stackoverflow.com/questions/33569668/numpy-max-vs-amax-vs-maximum

    累積 max
    :param collections.Iterable it:
    :param float first:
    :return:
    """
    cm = first
    ret = []
    for v in it:
        cm = max(v, cm)
        ret.append(cm)
    return ret


N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))

# dp[k]: i | j | k == k となる i, j のうち A[i] + A[j] が最大となる i, j
#: :type: list of ((int, int), (int, int))
dp = [None] * (2 ** N)
for k in range(1, 2 ** N):
    dp[k] = (A[0], 0), (A[k], k)

digits = []
k = 1
while k < 2 ** N:
    digits.append(k)
    k <<= 1

for bit in range(2, N + 1):
    for ds in itertools.combinations(digits, bit):
        k = sum(ds)
        for rm in ds:
            pass
            # a, b = dp[k - rm]
            # c, d = dp[k]
            # ss = sorted({a, b, c, d})
            # dp[k] = ss[-1], ss[-2]

ans = [0] * (2 ** N)
for k in range(1, 2 ** N):
    (a1, _), (a2, _) = dp[k]
    ans[k] = a1 + a2

ans = cummax(ans[1:])
print(*ans, sep='\n')

Submission status: Wrong Answer

Solution code:
from heapq import nlargest
from itertools import accumulate

n = int(input())
aaa = list(map(int, input().split()))
n2 = 1 << n
mask = n2 - 1

a0 = aaa[0]
dp = [[a0, a] for a in aaa]

for j in range(n):
    b = 1 << j
    c = i = mask ^ b
    while i:
        dp[i | b] = nlargest(2, dp[i] + dp[i | b])
        i = (i - 1) & c

ans = list(accumulate(map(sum, dp[1:]), func=max))
print(*ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

n = int(input())
aaa = list(map(int, input().split())) + [-1]
n2 = 1 << n

dp = [[i, -1] for i in range(n2)]
for j in range(n):
    b = 1 << j
    for i in range(n2):
        if i & b:
            dpi, dpk = dp[i], dp[i & ~b]
            i0, i1 = dpi
            k0, k1 = dpk
            if i0 != k0 and aaa[i0] < aaa[k0]:
                dpi[1] = i0
                dpi[0] = k0
            elif i1 != k0 and aaa[i1] < aaa[k0]:
                dpi[1] = k0
            if i1 != k1 and aaa[i1] < aaa[k1]:
                dpi[1] = k1
aaa_get = aaa.__getitem__
ans = list(accumulate(map(lambda x: sum(map(aaa_get, x)), dp), func=max))
print(*ans[1:])

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

n = int(input())
aaa = list(map(int, input().split()))
n2 = 1 << n

dp = [[a, 0] for a in aaa]
for j in range(n):
    b = 1 << j
    for i in range(n2):
        if i & b:
            dpi = dp[i]
            dpk = dp[i & ~b]
            if dpi[0] < dpk[0]:
                dpi[1] = dpi[0]
                dpi[0] = dpk[0]
            elif dpi[1] < dpk[0]:
                dpi[1] = dpk[0]
            if dpi[1] < dpk[1]:
                dpi[1] = dpk[0]
ans = list(accumulate(map(sum, dp), func=max))
print(*ans[1:])

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

import numpy as np

n = int(input())
aaa = list(enumerate(map(int, input().split())))
aaa.sort(reverse=True, key=itemgetter(1))

n2 = 1 << n
arr = np.arange(n2, dtype=np.uint)
bit = np.zeros(n, dtype=np.uint)
mat = np.zeros((n, n2))
for i in range(n):
    b = 1 << i
    bit[i] = b
    mat[i] = (arr & b) > 0
count = np.zeros(n2, dtype=np.uint8)
ans = np.zeros(n2, dtype=np.uint)

lim = n2
for i, a in aaa:
    idx = mat[(bit & i).astype(bool), :lim].all(axis=0) & (count[:lim] < 2)
    ans[:lim][idx] += a
    count[:lim][idx] += 1
    filled = count[:lim] >= 2
    if filled.any():
        lim = filled.argmax()
ans = np.maximum.accumulate(ans[1:])
print(*ans)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

import numpy as np

n = int(input())
aaa = list(enumerate(map(int, input().split())))
aaa.sort(reverse=True, key=itemgetter(1))

n2 = 1 << n
arr = np.arange(n2, dtype=np.uint)
bit = np.zeros(n, dtype=np.uint)
mat = np.zeros((n, n2))
for i in range(n):
    b = 1 << i
    bit[i] = b
    mat[i] = (arr & b) > 0
count = np.zeros(n2, dtype=np.uint8)
ans = np.zeros(n2, dtype=np.uint)

i, a = aaa[0]
idx = mat[(bit & i).astype(bool)].all(axis=0) & (count < 2)
ans[idx] += a
count[idx] += 1

lim = n2
for i, a in aaa[1:]:
    filled = count[:lim] >= 2
    idx = mat[(bit & i).astype(bool), :lim].all(axis=0) & ~filled
    ans[:lim][idx] += a
    count[:lim][idx] += 1
    if filled.any():
        lim = filled.argmax()
ans = np.maximum.accumulate(ans[1:])
print(*ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
f = [[a] for a in A]
for i in range(N):
    j = 0
    while j < 1<<N:
        j |= 1<<i
        f[j] = sorted(f[j]+f[j^1<<i], reverse=True)[:2]
        j += 1
        print(j)
Ans = [sum(f[1])]
for a, b in f[2:]:
    Ans.append(max(Ans[-1], a+b))
print("\n".join(map(str, Ans)))

Submission status: Wrong Answer

Solution code:
# YouTube

def max12(x):
    if len(x) < 3:
        return x
    x.sort(reverse=True)
    return x[:2]

n = int(input())
nn = 2 ** n
aa = list(map(int, input().split()))
dp = [[a] for a in aa]
print(dp)
for i in range(n):
    for j in range(nn - 1, -1, -1):
        if j & 1 << i == 0:
            dp[j + (1 << i)] = max12(dp[j + (1 << i)] + dp[j])
#    print(dp)
mx = 0
for dk in dp[1:]:
    mx = max(mx, sum(dk))
    print(mx)

Submission status: Wrong Answer

Solution code:
from heapq import *

n = int(input())
nn = 2 ** n
aa = list(map(int, input().split()))
hp = []
ai = []
ans = [-1] * nn
for i, a in enumerate(aa):
    ai.append([a, i])
ai.sort(reverse=True)
used = set()
heappush(hp, [-ai[0][0] - ai[1][0], ai[0][1] | ai[1][1], 0, 1])
used.add((0, 1))
ni = 2
r = nn
while ni > 1:
    s, ni, i, j = heappop(hp)
    if ans[ni] == -1:
        for ii in range(ni, r):
            ans[ii] = -s
        r = ni
    if (i, j + 1) not in used and j < nn - 1:
        heappush(hp, [-ai[i][0] - ai[j][0], ai[i][1] | ai[j][1], i, j + 1])
        used.add((i, j + 1))
    if i + 1 < j and (i + 1, j) not in used:
        heappush(hp, [-ai[i + 1][0] - ai[j][0], ai[i + 1][1] | ai[j][1], i + 1, j])
        used.add((i + 1, j))
for x in ans[1:]:
    print(x)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from heapq import heappushpop

N = int(input())
A = [int(x) for x in input().split()]

# B_x = max {A_y | y\subset x}
# と思ったが、2元ずつ持つ必要がある。
# (値、何番から来たか)
B = []
for n,a in enumerate(A):
    arr = [(0,0),(a,n)]
    m = n
    while m:
        bit = m & (-m)
        (x,i),(y,j) = B[n-bit]
        heappushpop(arr,(x,i))
        heappushpop(arr,(y,j))
        m -= bit
    B.append(arr)

answer = [0]
for (x,i),(y,j) in B[1:]:
    z = answer[-1]
    if z < x + y:
        z = x + y
    answer.append(z)
print('\n'.join(map(str,answer[1:])))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))

dp = [(0, 0, a[0]), (0, 1, sum(a[:2]))]

print(dp[1][2])
power = 0
pow2 = [2**p for p in range(19)]
for i in range(2, 2**n):
    if i == pow2[power+1]:
        power += 1

    i_0 = i-pow2[power]
    i_00, i_01, ans_0 = dp[i_0]
    
    i_1 = i&(i-1)
    i_10, i_11, ans_1 = dp[i_1]
    
    _, _, ans_prev = dp[i-1]

    a_tops = set([(a[i_00], i_00), (a[i_01], i_01),
                  (a[i_10], i_10), (a[i_11], i_11),
                  (a[i], i)])
    a_top1, a_top2 = sorted(a_tops, reverse = True)[:2]
    ans = max(a_top1[0]+a_top2[0], ans_prev)
    print(ans)
    dp.append((a_top1[1], a_top2[1], ans))
    
# print(dp)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))

dp = [(0, 0, a[0]), (0, 1, sum(a[:2]))]

print(dp[1][2])
power = 0
pow2 = [2**p for p in range(19)]
for i in range(2, 2**n):
    if i == pow2[power+1]:
        power += 1

    i_0 = i-pow2[power]
    i_00, i_01, ans_0 = dp[i_0]
    
    i_1 = i&(i-1)
    i_10, i_11, ans_1 = dp[i_1]
    _, _, ans_prev = dp[i_1-1]

    a_tops = set([(a[i_00], i_00), (a[i_01], i_01),
                  (a[i_10], i_10), (a[i_11], i_11),
                  (a[i], i)])
    a_top1, a_top2 = sorted(a_tops, reverse = True)[:2]
    ans = max(a_top1[0]+a_top2[0], ans_prev)
    print(ans)
    dp.append((a_top1[1], a_top2[1], ans))
    
# print(dp)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))

ma = [[A[0], 0], [0, 0], [0, 0]]

jud = 2
for i in range(1, 2 ** N):
  k = [A[i], i]
  for j in range(3):
    if k[0] > ma[j][0]:
      t = ma[j]
      ma[j] = k
      k = t
  if i == jud:
    jud *= 2
    d = ma[0][1] + ma[1][1]
    if d == i * 2 - 1:
      print(ma[0][0] + ma[2][0])
    else:
      print(ma[0][0] + ma[1][0])
  else:
    print(ma[0][0] + ma[1][0])

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
INF = float("inf")
B = [[A[i], -INF] for i in range(1 << N)]
for i in range(N):
    for j in range(1 << N):
        if j & (1 << i):
            tmp = B[j] + B[j ^ (1 << i)]
            tmp = sorted(tmp, reverse=True)
            B[j] = tmp[:2]

ans = -INF
for i in range(1, 1 << N):
    ans = max(ans, sum(B[i]))
    print(sum(B[i]))

Submission status: Wrong Answer

Solution code:
N = int(input())
ai = list(map(int,input().split()))
ansi = [[i,0] for i in ai]
for i in range(N):
    for j in range(1<<N):
        if (j & (1<<i)):
            ansi[j][1] = max(ansi[j][1],ai[j^(1<<i)])
            if ansi[j][0] < ansi[j][1]:
                ansi[j][0],ansi[j][1] = ansi[j][1],ansi[j][0]
answer = [i[0]+i[1] for i in ansi]
now = answer[0]
for i in range(1,1<<N):
    now = max(now,answer[i])
    print(now)

Submission status: Wrong Answer

Solution code:
# -*- coding:utf-8 -*-
n = int(input())
a = [int(i) for i in input().split()]
dp = [[x, 0] for x in range(0, len(a))]


def ins(x, i):
    if dp[i][0] != x and a[dp[i][0]] < a[x]:
        dp[i][1] = dp[i][0]
        dp[i][0] = x
    elif dp[i][1] != x and a[dp[i][1]] < a[x]:
        dp[i][1] = x


def mix(i, j):
    ins(dp[i][0], j)
    ins(dp[i][1], j)


for i in range(0, len(a)):
    for j in range(0, n):
        if i & (1 << j) == 0:
            mix(i, i | (1 << j))

ans = 0
for i in range(1, len(a)):
    u = a[dp[i][0]]+a[dp[i][1]]
    ans = max(ans, u)
    print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding:utf-8 -*-
n = int(input())
a = [int(i) for i in input().split()]
dp = [[x, 0] for x in range(0, len(a))]


def ins(x, i):
    if dp[i][0] != x and a[dp[i][0]] < a[x]:
        dp[i][1] = dp[i][0]
        dp[i][0] = x
    elif dp[i][1] != x and dp[i][1] < x:
        dp[i][1] = x


def mix(i, j):
    ins(dp[i][0], j)
    ins(dp[i][1], j)


for i in range(0, len(a)):
    for j in range(0, n):
        if i & (1 << j) == 0:
            mix(i, i | (1 << j))

ans = 0
for i in range(1, len(a)):
    u = a[dp[i][0]]+a[dp[i][1]]
    ans = max(ans, u)
    print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(i) for i in input().split()]


def chmax(a, b):
    if a[0] < b[1]:
        return b
    elif a[0] < b[0]:
        return b[0], a[0]
    elif a[1] < b[0]:
        return a[0], b[0]
    else:
        return a


dp = [(A[i], 0) for i in range(1 << N)]  # 1 << N = 2**N

# おそらく以下が高速ゼータ変換に当たる部分
for i in range(N):
    for j in range(1 << N):
        if j & (1 << i):
            print(j, i, j ^ (1 << i))
            dp[j] = chmax(dp[j], dp[j ^ (1 << i)])


print(dp)
ans = sum(dp[0])
for i in range(1, 1 << N):
    t = sum(dp[i])
    ans = max(ans, t)
    print(ans)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
N=int(input())
A=[int(i) for i in input().split()]

def chmax(a,b):
    if a[0]<b[1]:
        return b
    elif a[0]<b[0]:
        return(b[0],a[0])
    elif a[1]<b[0]:
        return (a[0],b[0])
    else:
        return a
dp=[(A[i],0) for i in range(1<<N)]
#print(dp)
for i in range(N):
    for j in range(1<<N):
        if j & (1<<i):
            #print(j,i,j|(1<<i))
            dp[j]=chmax(dp[j],dp[j^(1<<i)])
#print(dp)
ans =0
for i in range(1<<N):
    t = sum(dp[i])
    ans = max(ans,t)
    print(ans)

Submission status: Wrong Answer

Solution code:
# なんかWAって言われた、しんどい
N = int(input())
A = list(map(int, input().split()))


ans = 0
old_list = [0,0]
# Kが1増えた時に追加される和を計算して、maxを出せばよい
for k in range(1, 2**N):
    i_j_list = []
    i_j_list.append([0, k])
    for j in range(old_list[1], k+1):
        for i in range(0, j):
            if i | j <= k:
                i_j_list.append([i, j])
    A_new = [A[l[0]] + A[l[1]] for l in i_j_list]
    old_list = i_j_list[-1]
    ans = max(ans, max(A_new))
    print(ans)

Submission status: Wrong Answer

Solution code:
#
N = int(input())
A = list(map(int, input().split()))


ans = 0
old_list = [0,0]
# Kが1増えた時に追加される和を計算して、maxを出せばよい
for k in range(1, 2**N):
    i_j_list = []
    i_j_list.append([0, k])
    for j in range(old_list[1], k+1):
        for i in range(0, j):
            if i | j <= k:
                i_j_list.append([i, j])
    A_new = [A[l[0]] + A[l[1]] for l in i_j_list]
    old_list = i_j_list[-1]
    ans = max(ans, max(A_new))
    print(ans)
    print(i_j_list)

Submission status: Wrong Answer

Solution code:
#
N = int(input())
A = list(map(int, input().split()))


ans = 0
# Kが1増えた時に追加される和を計算して、maxを出せばよい
for k in range(1, 2**N):
    i_j_list = []
    i_j_list.append([0, k])
    j = k
    i = 0
    while (i+1) | j <= k and (i+1) < j:
        i += 1
        i_j_list.append([i, j])
    j = k - 1
    i = 0
    while (i+1) | j <= k and (i+1) < j:
        i += 1
        i_j_list.append([i, j])
    A_new = [A[l[0]] + A[l[1]] for l in i_j_list]
    ans = max(ans, max(A_new))
    print(ans)

Submission status: Wrong Answer

Solution code:
def suan(x, y):
    li = []
    for a in x:
        for b in y:
            if x[0] == x[1]:
                li.append(a+b)
                li.append(x[0]+x[1])
            elif a != b:
                li.append(a+b)
    return max(li)

while True:
    try:
        n = int(input())
        num = list(map(int, input().split()))
        maxn = [[num[0], 0]]
        max1 = num[0]
        max2 = 0
        for i in range(1, 2**n):
            if num[i] > max2:
                max2 = num[i]
            if max2 > max1:
                max1, max2 = max2, max1
            maxn.append([max1, max2])
        for i in range(1, 2**n):
            xxx = []
            if (i | (i-1)) <= i:
                xxx.append(suan(maxn[i], maxn[i-1]))
            if (i | (i-2)) <= i and i >= 2:
                xxx.append(suan(maxn[i], maxn[i-2]))
            if ((i-1) | (i-2)) <= i and i >= 2:
                xxx.append(suan(maxn[i-1], maxn[i-2]))
            print(max(xxx))
    except:
        break

Submission status: Wrong Answer

Solution code:
def suan(x, y):
    li = []
    for a in x:
        for b in y:
            if x[0] == x[1]:
                li.append(a+b)
            elif a != b:
                li.append(a+b)
    return max(li)

while True:
    try:
        n = int(input())
        num = list(map(int, input().split()))
        maxn = [[num[0], 0]]
        max1 = num[0]
        max2 = 0
        for i in range(1, 2**n):
            if num[i] > max2:
                max2 = num[i]
            if max2 > max1:
                max1, max2 = max2, max1
            maxn.append([max1, max2])
        for i in range(1, 2**n):
            xxx = []
            if (i | (i-1)) <= i:
                xxx.append(suan(maxn[i], maxn[i-1]))
            if (i | (i-2)) <= i and i >= 2:
                xxx.append(suan(maxn[i], maxn[i-2]))
            if ((i-1) | (i-2)) <= i and i >= 2:
                xxx.append(suan(maxn[i-1], maxn[i-2]))
            print(max(xxx))
    except:
        break

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

N = int(input())

A = list(map(int, input().split()))
P = [((A[0], 0), (0, 0))]

for i in range(1, 2 ** N):
    SP1 = P[i - 1][0]
    SP2 = P[i - 1][1]
    S1 = (A[i], i)
    S2 = (0, 0)
    for j in range(N):
        if (i & (1 << j)) != 0:
            index = i - (1 << j)
            for k in range(2):
                p = P[index][k]
                if S1 < p:
                    S2 = S1
                    S1 = p
                elif S2 < p and S1 != p:
                    S2 = p
    if(SP1[0] + SP2[0] > S1[0] + S2[0]):
        S1 = SP1
        S2 = SP2
    print(S1[0] + S2[0])
    P.append((S1, S2))
#print(P)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

N = int(input())

A = list(map(int, input().split()))

for i in range(2 ** N):
    print(0)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[int(i) for i in input().split()]
for k in range(1,2**n):
    if k!=2:
        b=a[:k+1]
        b.sort()
        #print(b)
        print(b[k-1]+b[k])
    else:
        b=a[:k+1]
        print(max(b[0]+b[1],b[0]+b[2]))

Submission status: Wrong Answer

Solution code:
N = input('')
N=int(N)
tmp=2**N-1
tmpK = list(map(int,input().split()))
#K=input('')

#tmpK=K.split(' ')
#tmpK = [int(s) for s in tmpK]
#print(tmpK[0:1])
#tmpK=int(tmpK)
print(tmpK)
for i in range(1,tmp+1):
    #print("i=",i)
    if i==2:
        max1=tmpK[0]+tmpK[1]
        max2=tmpK[0]+tmpK[2]
        if max1<max2:
            print(max2)
        else:
            print(max1)
        
    else:
        test=tmpK[0:i+1]
        #print(test)
        ld = sorted(test, reverse=True)
        #print("ld=",ld)
        print(ld[0]+ld[1])

Submission status: Wrong Answer

Solution code:
# npimport numpy as
N = input('')
N=int(N)
tmp=2**N-1
K=input('')
tmpK=K.split(' ')
tmpK = [int(s) for s in tmpK]
#print(tmpK[0:1])
#tmpK=int(tmpK)
#print(tmpK)
for i in range(1,tmp+1):
    #print("i=",i)
    if i==2:
        max1=int(tmpK[0])+int(tmpK[1])
        max2=int(tmpK[0])+int(tmpK[2])
        if max1<max2:
            print(max2)
        else:
            print(max1)
        
    else:
        test=tmpK[0:i+1]
        #print(test)
        ld = sorted(test, reverse=True)
        #print("ld=",ld)
        print(int(ld[0])+int(ld[1]))

Submission status: Time Limit Exceeded

Solution code:

def merge(L1, L2):
    P = []
    for x in L1:
        P.append(x)
    for y in L2:
        P.append(y)
    P.sort(reverse=True)
    return [P[0], P[1]]


def main():
    N = int(input())
    a = list(map(int, input().split()))
    dp = [[[0, -10**20] for j in range(N+1)]for i in range(1 << N)]
    for i in range(1 << N):
        dp[i][0][0] = a[i]

    for j in range(1, N+1):
        for i in range(1 << N):
            if (i & (1 << (j-1))):
                dp[i][j] = merge(dp[i & ~(1 << (j-1))][j - 1], dp[i][j-1])
            else:
                dp[i][j] = dp[i][j-1]
    result = [0]*(1 << N)
    for k in range(1, 1 << N):
        result[k] = max(result[k-1], sum(dp[k][N]))
        print(result[k])
    return


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
"""

https://atcoder.jp/contests/arc100/tasks/arc100_c

情報を再利用するのがメイン
K=Xの時は,K=X-1の時の答えに加え、 i or j == K の場合を考えればいい
or がKとなる場合、0の桁は両方0で、1の桁は片方が1ならよい
1では3通りの分け方があるので、3^N…

大きいほうから考えてみる？
最後は、当然最大のやつ2個→その2つのindex のORまではそれが保持

dp[X] = X と orしてもXのままのindexの集合における最大 & 2番目
→とすれば、1の桁全てに関して0にしてみた奴とXを見れば推移できる

O(2^N * logMAX(A)) で解けそうだ

"""

from sys import stdin

N = int(stdin.readline())
A = list(map(int,stdin.readline().split()))
A.append(float("-inf"))

dp = []
ans = 0
aaa = []

for i in range(2**N):

    if i == 0:
        dp.append( ( 0,-1 ) )
        continue

    dic = {}
    lis = [(A[i],i)]
    
    for j in range(N):

        if (2**j) & i > 0:

            ta,tb = dp[i ^ (2**j)]
            if ta not in dic:
                dic[ta] = 1
                lis.append( (A[ta],ta) )
            if tb not in dic:
                dic[tb] = 1
                lis.append( (A[tb],tb) )

    lis.sort()
    lis.reverse()

    aa,ab = lis[0][1] , lis[1][1]
    ans = max(A[aa] + A[ab] , ans)
    aaa.append(ans)
    dp.append( ( aa,ab ) )
print ("\n".join(map(str,aaa)))

Submission status: Time Limit Exceeded

Solution code:

"""

https://atcoder.jp/contests/arc100/tasks/arc100_c

情報を再利用するのがメイン
K=Xの時は,K=X-1の時の答えに加え、 i or j == K の場合を考えればいい
or がKとなる場合、0の桁は両方0で、1の桁は片方が1ならよい
1では3通りの分け方があるので、3^N…

大きいほうから考えてみる？
最後は、当然最大のやつ2個→その2つのindex のORまではそれが保持

dp[X] = X と orしてもXのままのindexの集合における最大 & 2番目
→とすれば、1の桁全てに関して0にしてみた奴とXを見れば推移できる

O(2^N * logMAX(A)) で解けそうだ

"""

from sys import stdin

N = int(stdin.readline())
A = list(map(int,stdin.readline().split()))
A.append(float("-inf"))

dp = []
ans = 0

for i in range(2**N):

    if i == 0:
        dp.append( ( 0,-1 ) )
        continue

    dic = {}
    lis = [(A[i],i)]
    
    for j in range(N):

        if (2**j) & i > 0:

            ta,tb = dp[i ^ (2**j)]
            if ta not in dic:
                dic[ta] = 1
                lis.append( (A[ta],ta) )
            if tb not in dic:
                dic[tb] = 1
                lis.append( (A[tb],tb) )

    lis.sort()
    lis.reverse()

    aa,ab = lis[0][1] , lis[1][1]
    ans = max(A[aa] + A[ab] , ans)
    print (ans)
    dp.append( ( aa,ab ) )

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from itertools import accumulate

def main():
  
  def merge(i, j):
    if dp1[i] >= A[j]:
      dp2[i] = max(dp2[i], A[j])
    else:
      dp2[i] = dp1[i]
      dp1[i] = A[j]
  n = int(input())
  A = tuple(map(int, input().split()))
  dp1 = [0]*(1<<n)
  dp2 = [0]*(1<<n)
  for i in range(1<<n):
    j = i
    while j>0:
      merge(i, j)
      j = (j-1)&i
    merge(i, 0)
  L = list(accumulate([a+b for a, b in zip(dp1, dp2)], max))
  print(*L[1:], sep="\n")

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from itertools import accumulate

def merge(i, j):
  if dp1[i] >= A[j]:
    dp2[i] = max(dp2[i], A[j])
  else:
    dp2[i] = dp1[i]
    dp1[i] = A[j]
n = int(input())
A = tuple(map(int, input().split()))
dp1 = [0]*(1<<n)
dp2 = [0]*(1<<n)
for i in range(1<<n):
  j = i
  while j>0:
    merge(i, j)
    j = (j-1)&i
  merge(i, 0)
L = list(accumulate([a+b for a, b in zip(dp1, dp2)], max))
print(*L[1:], sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from itertools import accumulate

def merge(x, y):
  D = sorted([dp[x][0], dp[x][1], dp[y][0], dp[y][1]], reverse=True)
  return (D[0], D[1])
  
n = int(input())
A = tuple(map(int, input().split()))
dp = [(a, 0) for a in A]
for j in range(n):
  for i in range(1<<n):
    if i & (1<<j):
      dp[i] = merge(i, i & ~(1<<j))
L = tuple(accumulate((sum(d) for d in dp), max))
print(*L[1:], sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class Top2:
    def __init__(self,x=-1,y=-1):
        if x<y:x,y=y,x
        self.val=[x,y]
        self.s=x+y

    def __add__(self, other):
        i=j=0
        self.val=sorted(self.val+other.val,reverse=True)[:2]
        self.s=sum(self.val)
        return self

n=II()
aa=LI()
dp=[Top2(a) for a in aa]

for i in range(n):
    for j in range((1<<n)-1,-1,-1):
        if j>>i&1:continue
        dp[j|1<<i]+=dp[j]

mx=-1
for j in range(1,1<<n):
    mx=max(mx,int(dp[j].s))
    print(mx)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    N = int(input())
    As = list(map(int, input().split()))

    pow2 = 2**N

    anss = []
    ans = 0
    setMax2s = [set([0])]
    for S in range(1, pow2):
        setMax2 = set([S])
        for i in range(N):
            if (S>>i)&1:
                S0 = S^(1<<i)
                setMax2 |= setMax2s[S0]
        Bs = sorted(setMax2, key=lambda x: As[x], reverse=True)
        i, j = Bs[:2]
        ans2 = As[i]+As[j]
        if ans2 > ans:
            ans = ans2
        anss.append(ans)
        setMax2 = set([i, j])
        setMax2s.append(setMax2)

    print('\n'.join(map(str, anss)))


solve()

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))

data=[((A[0],0),(-1,-1)) for i in range(2**N)]
for i in range(1,2**N):
    test=set([])
    for j in range(0,N):
        if i>>j&1==1:
            a,b=data[i-2**j]
            test.add(a)
            test.add(b)
    test.add((A[i],i))
    test=list(test)
    test.sort()
    data[i]=(test[-1],test[-2])

ans=[data[i][0][0]+data[i][1][0] for i in range(2**N)]
for i in range(2,2**N):
    ans[i]=max(ans[i],ans[i-1])

for i in range(1,2**N):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    d = [None]*(2**n)
    d[0] = [a[0], 0, -1, -1]
    ans = 0
    for i, t1 in enumerate(a[1:]):
        i += 1
        t2, t3, t4 = i, -1, -1
        for j in range(len(bin(i))-2):
            k = i & ~(1 << j)
            if k == i:
                continue
            t5, t6, t7, t8 = d[k]
            if t6 not in [t2, t4]:
                if t5 > t1:
                    t1, t2, t3, t4 = t5, t6, t1, t2
                elif t5 > t3:
                    t3, t4 = t5, t6
            if t8 != t4:
                if t7 > t3:
                    t3, t4 = t7, t8
        d[i] = [t1, t2, t3, t4]
        ans = max(ans, t1+t3)
        print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    d = [None]*(2**n)
    d[0] = [(a[0], 0), (-1, -1)]
    ans = 0
    for i, t1 in enumerate(a[1:]):
        i += 1
        t2, t3, t4 = i, -1, -1
        for j in range(len(bin(i))-2):
            k = i & ~(1 << j)
            if k == i:
                continue
            (t5, t6), (t7, t8) = d[k]
            if t6 not in [t2, t4]:
                if t5 > t1:
                    t1, t2, t3, t4 = t5, t6, t1, t2
                elif t5 > t3:
                    t3, t4 = t5, t6
            if t8 != t4:
                if t7 > t3:
                    t3, t4 = t7, t8
        d[i] = [(t1, t2), (t3, t4)]
        ans = max(ans, t1+t3)
        print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    d = [[(j, i), (-1, -1)] for i, j in enumerate(a)]
    ans = 0
    for i in range(1, 2**n):
        (t1, t2), (t3, t4) = d[i]
        for j in range(len(bin(i))-2):
            (t5, t6), (t7, t8) = d[i & ~(1 << j)]
            if t6 not in [t2, t4]:
                if t5 > t1:
                    t1, t2, t3, t4 = t5, t6, t1, t2
                elif t5 > t3:
                    t3, t4 = t5, t6
            if t8 != t4:
                if t7 > t3:
                    t3, t4 = t7, t8
        d[i] = [(t1, t2), (t3, t4)]
        ans = max(ans, t1+t3)
        print(ans)


main()