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

Solution (Python):
def merge(x, y, z, w):
    P = [x, y, z, w]
    P.sort()
    return P[-1], P[-2]


def main():
    N = int(input())
    a = list(map(int, input().split()))
    dp = [0]*(2*(N+1)*((1 << N)))

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


if __name__ == "__main__":
    main()

Solution (Python):

"""

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

    na,nb = i,-1
    
    for j in range(N):

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

            ta,tb = dp[i ^ (2**j)]
            if A[na] < A[ta]:
                nb = na
                na = ta
            elif A[nb] < A[ta] and ta != na:
                nb = ta

            if A[nb] < A[tb]:
                nb = tb

    
    ans = max(A[na] + A[nb] , ans)
    aaa.append(ans)
    dp.append( ( na,nb ) )

print ("\n".join(map(str,aaa)))

Solution (Python):
N = int(input())
As = [(A << 20) + i for i, A in enumerate(map(int, input().split()))]


def chmax(i, elem):
    global dp
    if dp[0][i] < elem:
        dp[1][i] = dp[0][i]
        dp[0][i] = elem
        return True
    elif dp[1][i] < elem < dp[0][i]:  
        dp[1][i] = elem
        return True
    else:
        return False


dp = [[0] * len(As) for _ in range(2)]  
dp[0][0] = As[0]
ans = 0
for i in range(1, 2 ** N):
    for j in range(N):
        if i & (1 << j):
            if chmax(i, dp[0][i & ~(1 << j)]):
                chmax(i, dp[1][i & ~(1 << j)])
    chmax(i, As[i])
    ans = max(ans, (dp[0][i] + dp[1][i]) >> 20)
    print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
from itertools import accumulate

def merge(x, y):
  a, b = dp[x]
  c, d = dp[y]
  if a >= c:
    return (a, max(c, b))
  return (c, max(a, d))
  
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")

Solution (Python):
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")

Solution (Python):
import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
dp = [[A[S], 0] for S in range(1 << N)]
for k in range(N):
    for S in range(1 << N):
        if S >> k & 1:
            if dp[S][0] < dp[S ^ (1 << k)][0]:
                dp[S][1] = max(dp[S][0], dp[S ^ (1 << k)][1])
                dp[S][0] = dp[S ^ (1 << k)][0]
            else:
                dp[S][1] = max(dp[S][1], dp[S ^ (1 << k)][0])
ans = 0
for K in range(1, 1 << N):
    ans = max(ans, sum(dp[K]))
    print(ans)

Solution (Python):
import sys

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]

    def __add__(self, other):
        self.val=sorted(self.val+other.val,reverse=True)[:2]
        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,sum(dp[j].val))
    print(mx)

Solution (Python):
import sys

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):
        self.val=sorted(self.val+other.val,reverse=True)[:2]
        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,sum(dp[j].val))
    print(mx)

Solution (Python):
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)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
m = [[ai] for ai in a]
for d in range(n):
    for s in range(1 << n):
        if s >> d & 1 == 0:
            t = s | 1 << d
            m[t] = sorted(m[t] + m[s])[-2:]
for k in range(1, 1 << n):
    ans = sum(m[k])
    for d in range(n):
        if k >> d & 1 == 1:
            t = k ^ 1 << d  | (1 << d) - 1
            ans = max(ans, sum(m[t]))
    print(ans)

Solution (Python):
def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return



def examE():
    N = I()
    A = LI()
    n = len(A)
    dp = [[0,0]for _ in range(n)]
    for i,a in enumerate(A):
        dp[i][0] = a
    for j in range(N):
        for i,a in enumerate(A):
            if i&(1<<j)>0:
                dp[i] = sorted(dp[i&~(1<<j)]+dp[i],reverse=True)[:2]
    ans = 0
    for v in dp[1:]:
        ans = max(ans,sum(v))
        print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examE()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Solution (Python):
def solve():
    N = int(input())
    As = list(map(int, input().split())) + [0]

    pow2 = 2**N

    anss = []
    ans = 0
    max2s = [[0, -1]]
    for S in range(1, pow2):
        m1, m2 = S, -1
        for i in range(N):
            if (S>>i)&1:
                S0 = S^(1<<i)
                i1, i2 = max2s[S0]
                if m1 == i1:
                    m2 = m2 if As[m2] >= As[i2] else i2
                elif As[m1] >= As[i1]:
                    m2 = m2 if As[m2] >= As[i1] else i1
                else:
                    m2 = m1 if As[m1] >= As[i2] else i2
                    m1 = i1
        ans2 = As[m1]+As[m2]
        if ans2 > ans:
            ans = ans2
        anss.append(ans)
        max2s.append([m1, m2])

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


solve()

Solution (Python):
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    A=LI()
    N2=pow(2,N)
    
    """
    下位集合に対する高速ゼータ変換．
    (Kがi,jを包含している）
    ここでのgを適切なfの和として考えるのが基本だけど，
    今回は和ではなくて上位2つの要素を持つ
    """
    
    g=[[0,0]for _ in range(N2)]
    
    for i in range(N2):
        g[i][0]=A[i]
        
    for k in range(N):
        for s in range(N2):
            if ((s>>k)&1):
                
                L=[0,0,0,0]
                L[0]=g[s][0]
                L[1]=g[s][1]
                L[2]=g[(s^(1<<k))][0]
                L[3]=g[(s^(1<<k))][1]
                L.sort()
                g[s][0]=L[-1]
                g[s][1]=L[-2]
                
                
    ans=0
    for k in range(1,N2):
        ans=max(ans,sum(g[k]))
        print(ans)
        
    
                    
                
            
        
    
    

main()

Solution (Python):
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):
    for j in range(N):
        if i>>j&1==1:
            a,b=data[i-2**j]
            if a[0]>data[i][0][0]:
                data[i][1]=data[i][0]
                data[i][0]=a
            elif a[0]>data[i][1][0] and a[1]!=data[i][0][1]:
                data[i][1]=a
            if b[0]>data[i][0][0]:
                data[i][1]=data[i][0]
                data[i][0]=b
            elif b[0]>data[i][1][0] and b[1]!=data[i][0][1]:
                data[i][1]=b
    a=(A[i],i)
    if a[0]>data[i][0][0]:
        data[i][1]=data[i][0]
        data[i][0]=a
    elif a[0]>data[i][1][0] and a[1]!=data[i][0][1]:
        data[i][1]=a


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

Solution (Python):
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

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

Solution (Python):
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]

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

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353


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)

Solution (Python):
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 t5 > t1:
                t1, t2, t3, t4 = t5, t6, t1, t2
            elif t5 > t3:
                if t6 != t2:
                    t3, t4 = t5, t6
                    continue
            if t7 > t3:
                t3, t4 = t7, t8
        d[i] = [t1, t2, t3, t4]
        ans = max(ans, t1+t3)
        print(ans)


main()

Solution (Python):
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 t5 > t1:
                t1, t2, t3, t4 = t5, t6, t1, t2
            elif t5 > t3:
                if t6 != t2:
                    t3, t4 = t5, t6
            if t7 > t3:
                t3, t4 = t7, t8
        d[i] = [t1, t2, t3, t4]
        ans = max(ans, t1+t3)
        print(ans)


main()

Solution (Python):
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(n):
            (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 not in [t2, t4]:
                if t7 > t3:
                    t3, t4 = t7, t8
        d[i] = [(t1, t2), (t3, t4)]
        ans = max(ans, t1+t3)
        print(ans)


main()

Solution (Python):
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)

Solution (Python):
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')

Solution (Python):
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:])))

Solution (Python):
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:])))

Solution (Python):
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")

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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:])))

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

dp1 = [x for x in a]
dp2 = [0 for _ in range(1<<n)]

for j in range(n+1):
	for i in range(1<<n):
		if i & (1<<j):
			if dp1[i & ~(1<<j)] >= dp1[i]:
				if dp2[i & ~(1<<j)] >= dp1[i]:
					dp2[i] = dp2[i & ~(1<<j)]
				else:
					dp2[i] = dp1[i]
				dp1[i] = dp1[i & ~(1<<j)]
			else:
				if dp1[i & ~(1<<j)] >= dp2[i]:
					dp2[i] = dp1[i & ~(1<<j)]

ans = 0
for i in range(1, 1<<n):
	ans = max(ans, dp1[i]+dp2[i])
	print(ans)

Solution (Python):
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



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 = [None] * SIZE
for k in range(1, SIZE):
    dp[k] = list(sorted([(A[0], 0), (A[k], k)]))























d = 1
while d < SIZE:
    for k in range(1, SIZE):
        if k & d == 0 or k - d == 0:
            continue
        
        prev_k = k - d

        a1, a2 = dp[k]
        b1, b2 = dp[prev_k]
        if a1 > b2:
            
            pass
        elif b1 > a2:
            
            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')

Solution (Python):
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



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 = [None] * SIZE
for k in range(1, SIZE):
    dp[k] = list(sorted([(A[0], 0), (A[k], k)]))























for k in range(1, SIZE):
    d = 1
    while d < SIZE:
        if k & d == 0 or k - d == 0:
            d <<= 1
            continue
        
        prev_k = k - d

        a1, a2 = dp[k]
        b1, b2 = dp[prev_k]
        if a1 > b2:
            
            pass
        elif b1 > a2:
            
            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')

Solution (Python):
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



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 = [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:
        
        next_k = (mask + 1) | k
        mask |= next_k

        a1, a2 = dp[k]
        b1, b2 = dp[next_k]
        if a1 > b2:
            
            dp[next_k] = dp[k]
        elif b1 > a2:
            
            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')

Solution (Python):
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):
  for i in range(2**n):
    if not i & (1<<j):
      renew(a,i|(1<<j),i)
a = [x+y for x,y in a[1:]]
for i in range(1,2**n-1):
  if a[i] < a[i-1]:
    a[i] = a[i-1]
for x in a:
  print(x)

Solution (Python):
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])

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

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

n = int(input()) 

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


za = zeta_transform(a[:],n)


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

Solution (Python):
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)))

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