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):
import sys
input = sys.stdin.readline
from heapq import heappushpop

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




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]
        if (x,i) != arr[-1]:
            heappushpop(arr,(x,i))
        if (y,j) != arr[-1]:
            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:])))

Solution (Python):


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)

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

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

Solution (Python):
N=int(input())
A=[int(i) for i in input().split()]
B=[[A[i],-10**15] for i in range(2**N)]
for i in range(N):
    for b in range(2**N):
        if ((1&(b>>i))==1):
            merge=B[b]+B[b^(1<<i)]
            merge.sort(reverse=True)
            B[b]=merge[:2]
ans=-10**15
for i in range(1,2**N):
    ans=max([ans,sum(B[i])])
    print(ans)

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

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

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

Solution (Python):
from heapq import heappush, heappop, heappushpop
N = int(input())
*A, = map(int, input().split())

def update(v, que):
    p, q = que
    if v == p or v == q:
        return
    heappushpop(que, v)

memo = [None]*(2**N)
memo[0] = [(0, -1), (A[0], 0)]
ma = 0; ans = []
for i in range(1, 2**N):
    res = [(0, -1), (A[i], i)]
    for j in range(N):
        if (i >> j) & 1 == 0:
            continue
        p, q = memo[i ^ (1 << j)]
        update(p, res)
        update(q, res)
    p, q = memo[i] = res
    ma = max(ma, p[0] + q[0])
    ans.append(ma)
print(*ans, sep='\n')

Solution (Python):

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)

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

for i in range(N):
    for j in range(1<<N):
        if (j & (1<<i))==0:
            
            dp[j|(1<<i)]=chmax(dp[j],dp[j|(1<<i)])

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

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

for i in range(N):
    for j in range(1<<N):
        if j & (1<<i):
            
            dp[j]=chmax(dp[j],dp[j^(1<<i)])

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

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

func()

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

func()

Solution (Python):







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)
    

func()

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

func()

Solution (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):
        Ai = A[i]
        Pi = P[i]
        if (Ai, i) > Pi[0]:
            Pi[1] = Pi[0]
            Pi[0] = (Ai, i)
        elif (Ai, i) > Pi[1]:
            Pi[1] = (Ai, i)
        for j in range(N):
            if (i & (1 << j)) == 0:
                Pindex = P[i + (1 << j)]
                for k in range(2):
                    if Pi[k] > Pindex[0]:
                        Pindex[1] = Pindex[0]
                        Pindex[0] = Pi[k]
                    elif Pi[k] > Pindex[1] and Pi[k] != Pindex[0]:
                        Pindex[1] = Pi[k]
    ans = 0
    for i in range(1, 2 ** N):
        ans = max(ans, P[i][0][0] + P[i][1][0])
        print(ans)
    

func()