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: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
dp = [[0,0] for i in range(1<<n)]
def merge(ls1,ls2):
  p,q = ls1
  r,s = ls2
  ret = [max(p,r)]
  if p>r:
    ret.append(max(q,r))
  else:
    ret.append(max(p,s))
  return ret
for i in range(1<<n):
  dp[i][0] = a[i]
for i in range(n):
  for j in range(1<<n):
    if 1<<i & j:
      dp[j] = merge(dp[j],dp[1<<i^j])
ans = [0 for i in range(2**n)]
for i in range(1,1<<n):
  ans[i] = max(ans[i-1],sum(dp[i]))
for i in ans:
  if i:
    print(i)

Submission status: Accepted

Solution code:
def max2(p, q):
    e, b = p[0], p[1]
    c, d = q[0], q[1]
    s = list(set([e, b, c, d]))
    m1, m2 = 1<<n, 1<<n
    for i in s:
        if a[m1]<a[i]:
            m2 = m1
            m1 = i
        elif a[m2]<a[i]:
            m2 = i
    return (m1, m2)

n = int(input())
a = list(map(int, input().split()))
g = [(i, (1<<n)) for i in range(1<<n)]
a+=[0]
res = 0
for i in range(n):
    for j in range(1<<n):
        if (1<<i)&j: g[j] = max2(g[j], g[j^(1<<i)])
ans = []
for i in range(1, 1<<n):
    res = max(res, a[g[i][0]]+a[g[i][1]])
    ans.append(res)
print(*ans, sep = '\n')

Submission status: Accepted

Solution code:
N = int(input())
A = [(int(a), 0) for a in input().split()]
combine = lambda a, b: a if a[1] >= b[0] else b if b[1] >= a[0] else (a[0], b[0]) if a[0] > b[0] else (b[0], a[0])

for i in range(N):
    ii = 1 << i
    for j in range(1<<N)[::-1]:
        if j & ii:
            A[j] = combine(A[j], A[j^ii])

ANS = [0] * (1<<N)
for i in range(1, 1<<N):
    ANS[i] = max(ANS[i-1], sum(A[i]))

print("\n".join(map(str, ANS[1:])))

Submission status: Accepted

Solution code:
N = int(input())
A = [[(0, 0)] * (1<<N) for _ in range(N+1)]
A[0] = [(int(a), 0) for a in input().split()]
combine = lambda a, b: a if a[1] >= b[0] else b if b[1] >= a[0] else (a[0], b[0]) if a[0] > b[0] else (b[0], a[0])

for i in range(1, N+1):
    ii = 1 << i - 1
    for j in range(1<<N):
        if j & ii:
            A[i][j] = combine(A[i-1][j], A[i-1][j^ii])
        else:
            A[i][j] = A[i-1][j]

ANS = [0] * (1<<N)
for i in range(1, 1<<N):
    ANS[i] = max(ANS[i-1], sum(A[-1][i]))

print("\n".join(map(str, ANS[1:])))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = [[i] for i in a]

for j in range(n):
    for i in range(1<<n):
        if i & (1<<j):
            b[i] = sorted(b[i]+b[i^1<<j], reverse=True)[:2]
ans = []
tmp = 0
for i in range(1, 1<<n):
    tmp = max(tmp, sum(b[i]))
    ans.append(tmp)
print(*ans, sep="\n")

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))+[0]

data=[[] for i in range(2**N)]

for i in range(1,2**N):
    for j in range(N):
        if i&(1<<j)==0:
            continue
        else:
            data[i].append(i-(1<<j))

MAX=[0]*2**N
semiMAX=[0]*2**N

semiMAX[0]=2**N

if MAX[0]<A[1]:
    MAX[1]=1
    semiMAX[1]=0
else:
    MAX[1]=0
    semiMAX[1]=1

K=[A[0]+A[1]]
for k in range(2,2**N):
    a,b=k,2**N
    for u in data[k]:
        c,d=MAX[u],semiMAX[u]
        if A[c]<=A[b]:
            c=c
        elif A[d]>=A[a]:
            a,b=c,d
        elif A[c]>A[a]:
            a,b=c,a
        elif A[a]>=A[c]>A[b] and a!=c:
            b=c
        elif A[a]>=A[d]>A[b] and a!=d:
            b=d
    MAX[k]=a
    semiMAX[k]=b
    K.append(max(K[-1],A[a]+A[b]))

for u in K:
    print(u)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

Max = [[(0, A[0])]]
ans = 0
for bit in range(1, (1<<N)):
    dic = {bit: A[bit]}
    for i in range(N):
        if bit&(1<<i) != 0:
            for ind, val in Max[bit-(1<<i)]:
                dic[ind] = val
    com = []
    for ind, val in dic.items():
        if len(com) < 2:
            com.append((ind, val))
        else:
            if com[0][1] < com[1][1]:
                if com[0][1] < val:
                    com[0] = (ind, val)
                elif com[1][1] < val:
                    com[1] = (ind, val)
            else:
                if com[1][1] < val:
                    com[1] = (ind, val)
                elif com[0][1] < val:
                    com[0] = (ind, val)               
    Max.append(com)
    tmp = com[0][1] + com[1][1]
    if tmp > ans:
        ans = tmp
    print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

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

dp = [(a, 0) for a in A]
for i in range(N):
    for j in range(1<<N):
        if not j & (1<<i):
            k = j|(1<<i)
            a, b = dp[k]
            c, d = dp[j]
            res = None
            if a > c:
                if b > c:
                    res = (a, b)
                else:
                    res = (a, c)
            else:
                if a > d:
                    res = (c, a)
                else:
                    res = (c, d)
            assert res == tuple(sorted([a, b, c, d], reverse = True)[:2]), ''
            dp[k] = res
dp[0] = sum(dp[0])
for i in range(1, 1<<N):
    dp[i] = max(dp[i-1], sum(dp[i]))
print('\n'.join(map(str, dp[1:])))

Submission status: Accepted

Solution code:
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')):
    """
    累積 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()))
SIZE = 2 ** N

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

# 高速ゼータ変換、配る版
# for k in range(1, SIZE):
#     mask = k
#     while mask < SIZE - 1:
#         # kに立ってないビットを1つだけ立てる
#         next_k = (mask + 1) | k
#         mask |= next_k
#
#         a1, a2 = dp[k]
#         b1, b2 = dp[next_k]
#         if a1 > b2:
#             # dp[next_k] = a1, a2
#             dp[next_k] = dp[k]
#         elif b1 > a2:
#             # dp[next_k] = b1, b2
#             pass
#         elif a2 > b2:
#             dp[next_k] = b2, a2
#         elif b2 > a2:
#             dp[next_k] = a2, b2

# 高速ゼータ変換
d = 1
while d < SIZE:
    for k in range(1, SIZE):
        if k & d == 0 or k - d == 0:
            continue
        # k に立っているビットを1つだけ消したもの
        prev_k = k - d

        a1, a2 = dp[k]
        b1, b2 = dp[prev_k]
        if a1 > b2:
            # dp[k] = a1, a2
            pass
        elif b1 > a2:
            # dp[k] = b1, b2
            dp[k] = dp[prev_k]
        elif a2 > b2:
            dp[k] = b2, a2
        elif b2 > a2:
            dp[k] = a2, b2
    d <<= 1

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

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

Submission status: Accepted

Solution code:
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')):
    """
    累積 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()))
SIZE = 2 ** N

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

# 高速ゼータ変換、配る版
# for k in range(1, SIZE):
#     mask = k
#     while mask < SIZE - 1:
#         # kに立ってないビットを1つだけ立てる
#         next_k = (mask + 1) | k
#         mask |= next_k
#
#         a1, a2 = dp[k]
#         b1, b2 = dp[next_k]
#         if a1 > b2:
#             # dp[next_k] = a1, a2
#             dp[next_k] = dp[k]
#         elif b1 > a2:
#             # dp[next_k] = b1, b2
#             pass
#         elif a2 > b2:
#             dp[next_k] = b2, a2
#         elif b2 > a2:
#             dp[next_k] = a2, b2

# 高速ゼータ変換
for k in range(1, SIZE):
    d = 1
    while d < SIZE:
        if k & d == 0 or k - d == 0:
            d <<= 1
            continue
        # k に立っているビットを1つだけ消したもの
        prev_k = k - d

        a1, a2 = dp[k]
        b1, b2 = dp[prev_k]
        if a1 > b2:
            # dp[k] = a1, a2
            pass
        elif b1 > a2:
            # dp[k] = b1, b2
            dp[k] = dp[prev_k]
        elif a2 > b2:
            dp[k] = b2, a2
        elif b2 > a2:
            dp[k] = a2, b2

        d <<= 1

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

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

Submission status: Accepted

Solution code:
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()))
SIZE = 2 ** N

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

for k in range(1, SIZE):
    mask = k
    while mask < SIZE - 1:
        # kに立ってないビットを1つだけ立てる
        next_k = (mask + 1) | k
        mask |= next_k

        a1, a2 = dp[k]
        b1, b2 = dp[next_k]
        if a1 > b2:
            # dp[next_k] = a1, a2
            dp[next_k] = dp[k]
        elif b1 > a2:
            # dp[next_k] = b1, b2
            pass
        elif a2 > b2:
            dp[next_k] = b2, a2
        elif b2 > a2:
            dp[next_k] = a2, b2

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

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

Submission status: Accepted

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

ans = [0] * M
max_list = [0] * M
for i in range(1, M):
    cand = [i]
    ans_cand = []
    ibin = bin(i)[2:].zfill(N)
    for j in range(N):
        if ibin[j] == '1':
            cand.append(max_list[i - 2 ** (N - j - 1)])
            ans_cand.append(ans[i - 2 ** (N - j - 1)])
    cand_set = sorted(list(set(cand)))
    max1 = 0
    max2 = 0
    for c in cand_set:
        Ac = A[c]
        if Ac >= max1:
            max2 = max1
            max1 = Ac
            max_idx = c
        elif Ac > max2:
            max2 = Ac
    ans_cand.append(max1 + max2)
    ans_cand.append(ans[i - 1])
    max_list[i] = max_idx
    ans[i] = max(ans_cand)
    print(ans[i])

Submission status: Accepted

Solution code:
from itertools import accumulate

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

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


def update(dpi, dpk):
    if dpk[0] < dpi[0]:
        dpk[1] = max(dpk[0], dpi[1])
        dpk[0] = dpi[0]
    elif dpk[1] < dpi[0]:
        dpk[1] = dpi[0]


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

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

Submission status: Accepted

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

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


def update(dp, i, k):
    dpi, dpk = dp[i], dp[k]
    if dpk[0] < dpi[0]:
        dpk[1] = max(dpk[0], dpi[1])
        dpk[0] = dpi[0]
    elif dpk[1] < dpi[0]:
        dpk[1] = dpi[0]


for j in range(n):
    b = 1 << j
    c = i = mask ^ b
    while i:
        update(dp, i, i | b)
        i = (i - 1) & c
    update(dp, 0, b)

ans = []
tmp = 0
for a in dp[1:]:
    tmp = max(tmp, a[0] + a[1])
    ans.append(tmp)
print(*ans)

Submission status: Accepted

Solution code:
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 not i & b:
            dpi, dpk = dp[i], dp[i | b]
            if dpk[0] < dpi[0]:
                dpk[1] = max(dpk[0], dpi[1])
                dpk[0] = dpi[0]
            elif dpk[1] < dpi[0]:
                dpk[1] = dpi[0]

ans = []
tmp = 0
for a in dp[1:]:
    tmp = max(tmp, a[0] + a[1])
    ans.append(tmp)
print(*ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

n = int(input()) 
#n,x = [int(i) for i in readline().split()]
a = [int(i) for i in readline().split()]

def zeta_transform(a,n): #高速ゼータ変換
    b = [[i,0] for i in a]
    for i in range(n):
        I = 1<<i
        for j in range(1<<n):
            if not j&I:
                if b[j][0] > b[j^I][0]:
                    b[j^I][0],b[j^I][1] = b[j][0], b[j^I][0]
                    if b[j][1] > b[j^I][1]:
                        b[j^I][1] = b[j][1]
                elif b[j][0] > b[j^I][1]:
                    b[j^I][1] = b[j][0]
    return b

#print(a)
za = zeta_transform(a[:],n)
#print(zeta_transform(a[:],n),"zeta-a")

for i, zi in enumerate(za):
    if not i: ans = 0
    else:
        i1,i2 = za[i]
        ans = max(ans,i1+i2)
        print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
f = [[a, -1] for a in A]
lim = 1<<N
for i in range(N):
    bit = 1<<i
    j = 0
    while j < lim:
        j |= bit
        a, b = f[j]
        c, d = f[j^bit]
        if a < c:
            f[j][0] = c
            f[j][1] = d if d>a else a
        elif b < c:
            f[j][1] = c
        j += 1
ans = sum(f[1])
Ans = [ans]
for a, b in f[2:]:
    s = a+b
    if s > ans:
        ans = s
    Ans.append(ans)
print("\n".join(map(str, Ans)))

Submission status: Accepted

Solution code:


def merge(a, b):
    if a[0] > b[0]:
        if a[1] > b[0]:
            return a
        return a[0], b[0]
    if b[1] > a[0]:
        return b
    return b[0], a[0]


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

dp = [(a[i], 0) for i in range(1 << n)]
for j in range(n):
    for mask in range(1, len(dp)):
        if mask & (1 << j):
            dp[mask] = merge(dp[mask], dp[mask ^ (1 << j)])

best = a[0]
for i in range(1, len(dp)):
    best = max(best, sum(dp[i]))
    print(best)

Submission status: Accepted

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
C=[]
l=0
C.append(([(0,-1),(A[0],0)]))
for i in range(1,2**N):
  biggest,second=(A[i],i),(0,-1)
  for k in range(l+1):
    if i&(1<<k):
      for a in C[i^(1<<k)]:
        if a[0]>biggest[0]:
          second=biggest
          biggest=a
        elif a[0]>second[0] and biggest!=a:
          second=a
  C.append([second,biggest])
  if i==2**(l+1)-1:
    l+=1
ans=[0]
for i in range(1,2**N):
  a,b=C[i]
  ans.append(max(ans[-1],a[0]+b[0]))
  print(ans[-1])

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    n2 = 2**n
    a = LI()
    t = [[0,0] for _ in range(n2)]
    ii = [2**i for i in range(18)]
    M = n2
    for i in range(n2):
        ti = t[i]
        ti[0] = a[i] * M + i
        for j in range(18):
            if not i & ii[j]:
                continue
            for c in t[i^ii[j]]:
                if ti[0] < c:
                    ti[1] = ti[0]
                    ti[0] = c
                elif ti[1] < c and ti[0] != c:
                    ti[1] = c

    r = [0]
    for i in range(1,n2):
        tr = sum(map(lambda x: x//M, t[i]))
        if tr > r[-1]:
            r.append(tr)
        else:
            r.append(r[-1])
    return '\n'.join(map(str, r[1:]))



print(main())

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
 
#dp[S] = A[S], -inf で初期化　Sの部分集合TのうちA[T]が(最大のもの, 次に大きいもの)　を入れていく
 
dp = [[A[S], -float('inf') ] for S in range(1 << N)]
for i in range(N):
    for T in range( 1 << N):
        if (T >> i) & 1 == 1: # Tがiを含むとき
            merge = dp[T] + dp[T ^ (1 << i)]
            merge.sort(reverse = True)
            dp[T] =merge[:2]
ans = -float('inf')
for S in range(1, 1 << N , 1):
    ans = max(ans, sum(dp[S]))
    print(ans)

Submission status: Accepted

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 x in dp[i]:
        return
    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: Accepted

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 =sum(dp[0])
for i in range(1,1<<N):
    t = sum(dp[i])
    ans = max(ans,t)
    print(ans)

Submission status: Accepted

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

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

def func():
    N = int(input())

    A = list(map(int, input().split()))
    P = [[(A[0], 0), (0, 0)] for i in range(2 ** (N + 1))]
    A = [0] * (2 ** N) + A

    for i in range(2 ** N + 1, 2 ** (N + 1)):
        if (A[i], i - 2**N) > P[i][0]:
            P[i][1] = P[i][0]
            P[i][0] = (A[i], i - 2**N)
        elif (A[i], i) > P[i][1]:
            P[i][1] = (A[i], i - 2**N)
        for j in range(N):
            piyo = i - 2 ** N
            if (piyo & (1 << j)) == 0:
                index = piyo + (1 << j) + 2 ** N
                for k in range(2):
                    if P[i][k] > P[index][0]:
                        P[index][1] = P[index][0]
                        P[index][0] = P[i][k]
                    elif P[i][k] > P[index][1] and P[i][k] != P[index][0]:
                        P[index][1] = P[i][k]
    ans = 0
    for i in range(2 ** N + 1, 2 ** (N + 1)):
        ans = max(ans, P[i][0][0] + P[i][1][0])
        print(ans)
    #print(P)

func()

Submission status: Accepted

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

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

def func():
    N = int(input())

    A = list(map(int, input().split()))
    P = [[(A[0], 0), (0, 0)] for i in range(2 ** (N + 1))]

    for i in range(1, 2 ** N):
        if (A[i], i) > P[i][0]:
            P[i][1] = P[i][0]
            P[i][0] = (A[i], i)
        elif (A[i], i) > P[i][1]:
            P[i][1] = (A[i], i)
        for j in range(N):
            if (i & (1 << j)) == 0:
                index = i + (1 << j)
                for k in range(2):
                    if P[i][k] > P[index][0]:
                        P[index][1] = P[index][0]
                        P[index][0] = P[i][k]
                    elif P[i][k] > P[index][1] and P[i][k] != P[index][0]:
                        P[index][1] = P[i][k]
    ans = 0
    for i in range(1, 2 ** N):
        ans = max(ans, P[i][0][0] + P[i][1][0])
        print(ans)
    #print(P)

func()

Submission status: Accepted

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

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

def func():
    N = int(input())

    A = list(map(int, input().split()))
    P = [[(A[0], 0), (0, 0)] for i in range(2 ** N)]

    for i in range(1, 2 ** N):
        if (A[i], i) > P[i][0]:
            P[i][1] = P[i][0]
            P[i][0] = (A[i], i)
        elif (A[i], i) > P[i][1]:
            P[i][1] = (A[i], i)
        for j in range(N):
            if (i & (1 << j)) == 0:
                index = i + (1 << j)
                for k in range(2):
                    if P[i][k] > P[index][0]:
                        P[index][1] = P[index][0]
                        P[index][0] = P[i][k]
                    elif P[i][k] > P[index][1] and P[i][k] != P[index][0]:
                        P[index][1] = P[i][k]
    ans = 0
    for i in range(1, 2 ** N):
        ans = max(ans, P[i][0][0] + P[i][1][0])
        print(ans)
    #print(P)

func()

Submission status: Accepted

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

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

def func():
    N = int(input())

    A = list(map(int, input().split()))
    P = [[(A[0], 0), (0, 0)] for i in range(2 ** N)]

    for i in range(1, 2 ** N):
        if (A[i], i) > P[i][0]:
            P[i][1] = P[i][0]
            P[i][0] = (A[i], i)
        elif (A[i], i) > P[i][1]:
            P[i][1] = (A[i], i)
        for j in range(N):
            if (i & (1 << j)) == 0:
                index = i + (1 << j)
                for k in range(2):
                    if P[i][k] > P[index][0]:
                        P[index][1] = P[index][0]
                        P[index][0] = P[i][k]
                    elif P[i][k] > P[index][1] and P[i][k] != P[index][0]:
                        P[index][1] = P[i][k]
    ans = 0
    for i in range(1, 2 ** N):
        ans = max(ans, P[i][0][0] + P[i][1][0])
        print(ans)
    #print(P)

func()

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int,input().split()))
dp = [[0,0] for i in range(1<<n)]
def merge(ls1,ls2):
  p,q,r,s = *ls1,*ls2
  ret = [max(p,r)]
  if p>r:
    ret.append(max(q,r))
  else:
    ret.append(max(p,s))
  return ret
for i in range(1<<n):
  dp[i][0] = a[i]
for i in range(n):
  for j in range(1<<n):
    if 1<<i & j:
      dp[j] = merge(dp[j],dp[1<<i^j])
ans = [0 for i in range(2**n)]
for i in range(1,1<<n):
  ans[i] = max(ans[i-1],sum(dp[i]))
for i in ans:
  if i:
    print(i)

Submission status: Runtime Error

Solution code:
def renew(lis,id1,id2):
  tar = lis[id1]; bow = lis[id2]
  if tar[0] < bow[0]:
    tar = [bow[0],max(bow[1],tar[0])]
  else:
    tar[1] = max(bow[0],tar[1])
  lis[id1] = tar
  return

n = int(input())
a = [[x,0] for x in list(map(int, input().split()))]
for j in range(n):
  t = 1<<j
  for i in range(1<<n):
    if not i&t:
      renew(a,i|t,i)
a = [x+y for x,y in a]
for i in range(1,1<<n):
  if a[i] < a[i-1]:
    a[i] = a[i-1]
for x in a[1:]:
  print(x)

Submission status: Runtime Error

Solution code:
from heapq import nlargest

n = int(input())
aaa = list(map(int, input().split()))
n2 = 1 << n
dp = [[0, a] for a in aaa]

for j in range(n):
    b = 1 << j
    for i in range(n2):
        if not i & b:
            dp[i | b] = nlargest(2, dp[i] + dp[i | b])

ans = []
tmp = 0
for a in dp[1:]:
    tmp = max(tmp, a)
    ans.append(tmp)
print(*ans)

Submission status: Runtime Error

Solution code:
from heapq import nlargest
from itertools import accumulate

n = int(input())
aaa = list(map(int, input().split()))
n2 = 1 << n
dp = [[0, a] for a in aaa]

for j in range(n):
    b = 1 << j
    for i in range(n2):
        if not i & b:
            dp[i | b] = nlargest(2, dp[i] + dp[i | b])
    dp[b] = nlargest(2, dp[0] + dp[b])

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

Submission status: Runtime Error

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
dp = [[0, 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
    dp[b] = nlargest(2, dp[0] + dp[b])

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

Submission status: Runtime Error

Solution code:
from heapq import nlargest
from itertools import accumulate

n = int(input())
aaa = list(map(int, input().split())) + [0]
aaa_get = aaa.__getitem__
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) == 0:
            dp[i | b] = nlargest(2, {*dp[i], *dp[i | b]}, key=aaa_get)
ans = list(accumulate(map(lambda x: sum(map(aaa_get, x)), dp[1:]), func=max))
print(*ans)

Submission status: Runtime Error

Solution code:
a = int(input())
ar = list(map(int,input().split(" ")))
print(ar[0] + ar[1])
if ar[0] + ar[1] >= ar[0] + ar[2]:
    print(ar[0]+ar[1])
else:
    print(ar[0]+ar[2])
br = sorted([ar[0],ar[1],ar[2]])
k = br[2]
g = br[1]
for i in range(3,len(ar)):
    if ar[i] > k:
        k,g = ar[i],k
    elif ar[i] > g:
        g = ar[i]
    print(k + g)

Submission status: Runtime Error

Solution code:
#ifndef LOCAL
#pragma GCC optimize ("O3")
#endif

#include <bits/stdc++.h>

using namespace std;

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return {i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (c it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(x...) " [" #x ": " << (x) << "] "

using ld = long double;
using ll = long long;

constexpr int mod = 1000 * 1000 * 1000 + 7;
constexpr int odw2 = (mod + 1) / 2;

void OdejmijOd(int& a, int b) { a -= b; if (a < 0) a += mod; }
int Odejmij(int a, int b) { OdejmijOd(a, b); return a; }
void DodajDo(int& a, int b) { a += b; if (a >= mod) a -= mod; }
int Dodaj(int a, int b) { DodajDo(a, b); return a; }
int Mnoz(int a, int b) { return (ll) a * b % mod; }
void MnozDo(int& a, int b) { a = Mnoz(a, b); }
int Pot(int a, int b) { int res = 1; while (b) { if (b % 2 == 1) MnozDo(res, a); a = Mnoz(a, a); b /= 2; } return res; }
int Odw(int a) { return Pot(a, mod - 2); }
void PodzielDo(int& a, int b) { MnozDo(a, Odw(b)); }
int Podziel(int a, int b) { return Mnoz(a, Odw(b)); }
int Moduluj(ll x) { x %= mod; if (x < 0) x += mod; return x; }

template <typename T> T Maxi(T& a, T b) { return a = max(a, b); }
template <typename T> T Mini(T& a, T b) { return a = min(a, b); }

struct Wyn {
  int x, y;
  int vx, vy;

  Wyn() : x(0), y(0), vx(-1), vy(-1) {}

  void Dodaj(int val, int v) {
    if (v == vx or v == vy) return;
    if (val > x) {
      y = x;
      vy = vx;
      x = val;
      vx = v;
    } else if (val > y) {
      y = val;
      vy = v;
    }
  }

  void Polacz(const Wyn& w) {
    Dodaj(w.x, w.vx);
    Dodaj(w.y, w.vy);
  }

  int Oblicz() const {
    return x + y;
  }
};

int n;
int A[1 << 18];
Wyn dp[1 << 18];

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  for (int i = 0; i < (1 << n); i++) {
    cin >> A[i];

    Wyn& w = dp[i];
    w.Dodaj(A[i], i);

    for (int j = 0; j < n; j++) {
      if ((i >> j) & 1) {
        w.Polacz(dp[i ^ (1 << j)]);
      }
    }
    debug() << imie(i) imie(w.x) imie(w.vx) imie(w.y) imie(w.vy);
  }

  for (int i = 1; i < (1 << n); i++) {
    int odp = dp[i].Oblicz();;
    for (int j = 0; j < n; j++) {
      if ((i >> j) & 1) {
        Maxi(odp, dp[(i ^ (1 << j)) | ((1 << j) - 1)].Oblicz());
      }
    }
    cout << odp << '\n';
  }
  return 0;
}

Submission status: Runtime Error

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])