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: Time Limit Exceeded

Solution code:


def merge(p1, p2):
    inds = list(set(p1 + p2))
    inds.sort(key=lambda i: a[i],reverse=True)
    return inds[:2]


n = input()
a = map(int, raw_input().split())
a.append(0) #default value used for a[-1]

best = a[0]
dp = [[i, -1] for i in range(1 << n)]
for mask in range(1, len(dp)):
    for j in range(n):
        if mask & (1 << j):
            dp[mask] = merge(dp[mask], dp[mask ^ (1 << j)])
    best = max(best, sum(map(lambda x: a[x], dp[mask])))
    print(best)

Submission status: Time Limit Exceeded

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):
  s=set()
  s.add((A[i],i))
  for k in range(l+1):
    if i&(1<<k):
      a,b=C[i^(1<<k)]
      s.add(a)
      s.add(b)
  s=sorted(list(s))
  C.append([s[-2],s[-1]])
  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: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
ai = list(map(int,input().split()))
ansi = []
for i in ai:
    ansi.append([i,0])
for i in range(N):
    for j in range(1<<N):
        if (j & (1<<i)):
            ccc = ansi[j] + ansi[j^(1<<i)]
            cccc = ccc.copy()
            cccc.sort()
            ansi[j] = [cccc[3],cccc[2]]
now = ansi[0][0]+ansi[0][1]
for i in range(1,1<<N):
    if now < ansi[i][0]+ansi[i][1]:
        now = ansi[i][0]+ansi[i][1]
    print(now)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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)):
            ccc = ansi[j] + ansi[j^(1<<i)]
            cccc = ccc.copy()
            cccc.sort()
            ansi[j] = [cccc[3],cccc[2]]
answer = [i[0]+i[1] for i in ansi]
now = answer[1]
for i in range(1,1<<N):
    now = max(now,answer[i])
    print(now)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np

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: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import math

# 入力データ
in_cnt = int(input())
in_data = [int(i) for i in input().split()]

val_arr = [[in_data[i], 0] for i in range(1<<in_cnt)]

def check_max(i, j):
	global val_arr
	val0 = val_arr[j][0]
	val1 = val_arr[j][1]
	if val0 > val_arr[j|(1<<i)][0]:
		if val1 > val_arr[j|(1<<i)][0]:
			val_arr[j|(1<<i)][1] = val1
		else:
			val_arr[j|(1<<i)][1] = val_arr[j|(1<<i)][0]
		val_arr[j|(1<<i)][0] = val0
	elif val0 > val_arr[j|(1<<i)][1]:
		val_arr[j|(1<<i)][1] = val0

for i in range(in_cnt):
	for j in range(1<<in_cnt):
		if 0 == ( j&(1<<i) ):
			check_max(i, j)

max_sum = 0
for idx in range((1<<in_cnt)-1):
	if max_sum < sum(val_arr[idx+1]):
		max_sum = sum(val_arr[idx+1])
	print(max_sum)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import math

# 入力データ
in_cnt = int(input())
in_data = [int(i) for i in input().split()]

max_val = 0
max_arr = [0 for i in range(2 ** in_cnt)]

k = 1
max_k = 2 ** in_cnt - 1
while k <= max_k:
	for i in range(k):
		val = in_data[i] + in_data[k]
		idx = i | k
		if idx > max_k:
			continue
		if max_arr[idx-1] < val:
			max_arr[idx-1] = val
			
	if max_val < max_arr[k-1]:
		max_val = max_arr[k-1]
	
	# ans:k
	print(max_val)
	k += 1

Submission status: Time Limit Exceeded

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: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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))==0:
            #print(j,i,j|(1<<i))
            dp[j|(1<<i)]=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: Time Limit Exceeded

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
n=i1()
a=i2()
a.append(0)
b=[0,0]
c=[0,0]
k=[[0,0]for i in range(1<<n)]
for i in range(1<<n):
 v=[i,-1]
 for j in range(18):
   if 1<<j & i:
      v.append(k[i-(1<<j)][0])
      v.append(k[i-(1<<j)][1])
 v=list(set(v))
 v=sorted(v,key=lambda x:a[x])
 k[i][0]=v[-1]
 k[i][1]=v[-2]
d=0
for i in range(1,1<<n):
 d=max(d,a[k[i][0]]+a[k[i][1]])
 print(d)

Submission status: Time Limit Exceeded

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):
        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)
    #print(P)

func()

Submission status: Time Limit Exceeded

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] in P[index]:
                        continue
                    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]:
                        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: Time Limit Exceeded

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):
        P[i].append((A[i], i))
        P[i] = list(set(P[i]))
        P[i].sort()
        P[i] = P[i][-2:]
        for j in range(N):
            if (i & (1 << j)) == 0:
                P[i + (1 << j)] += P[i]
    ans = 0
    for i in range(1, 2 ** N):
        ans = max(ans, P[i][0][0] + P[i][1][0])
        print(ans)

func()

Submission status: Time Limit Exceeded

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(2 ** N)]

for i in range(1, 2 ** N):
    P[i].append((A[i], i))
    P[i] = list(set(P[i]))
    P[i].sort()
    P[i] = P[i][-2:]
    for j in range(N):
        if (i & (1 << j)) == 0:
            P[i + (1 << j)] += P[i]
ans = 0
for i in range(1, 2 ** N):
    ans = max(ans, P[i][0][0] + P[i][1][0])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
A_ij = [A[0] for a in A]
for j in range(1, 2 ** N):
  for i in range(j):
    A_ij[i|j] = max(A_ij[i|j], A[i] + A[j])
ans = 0
for a in A_ij[1:]:
  ans = max(ans, a)
  print(ans)

Submission status: Time Limit Exceeded

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

B = [0 for x in range(1 << 18)]

for i in [1<<x for x in range(N)]:
    for j in range(1 << N):
        if j & i:
            r = max(A[j],A[j^i])
            B[j] = max(max(r^A[j]^A[j^i],B[j]),B[j^i])
            A[j] = r

m = 0
for i in range(1,1<<N):
    m = max(m,A[i] + B[i])
    print(m)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(x) for x in input().split(' ')]
M = 1 << N

max2 = [[0, 0]]
ans = 0
anss = []
for i in range(1, M):
    t = [0, i] if A[0] > A[i] else [i, 0]
    j = i
    while j:
        mask = j & -j
        for x in max2[i & ~mask]:
            if x in t: continue
            if A[x] >= A[t[0]]:
                t[0], t[1] = x, t[0]
            elif A[x] >= A[t[1]]:
                t[1] = x
        j &= ~mask
    max2.append(t)
    ans = max(ans, A[t[0]] + A[t[1]])
    anss.append(ans)
print('\n'.join([str(ans) for ans in anss]))

Submission status: Time Limit Exceeded

Solution code:

def main():
    N = int(input())
    A = [int(x) for x in input().split(' ')]
    M = 1 << N

    max2 = [[0, 0]]
    ans = 0
    for i in range(1, M):
        t = [0, i] if A[0] > A[i] else [i, 0]
        j = i
        while j:
            mask = j & -j
            for x in max2[i & ~mask]:
                if x in t: continue
                if A[x] >= A[t[0]]:
                    t[0], t[1] = x, t[0]
                elif A[x] >= A[t[1]]:
                    t[1] = x
            j &= ~mask
        max2.append(t)
        ans = max(ans, A[t[0]] + A[t[1]])
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

N = read()
A = reads()

M = 1 << N

def key(i):
  return -A[i] if i >= 0 else 0

amax = [None] * M
amax[0] = [0, -1]
for b in range(1, M):
  s = set()
  s.add(b)
  for i in range(N):
    if b & (1 << i) > 0:
      s.update(amax[b & ~(1 << i)])
  amax[b] = sorted(s, key=key)[:2]

sm = [0] * M
for b in range(M):
  sm[b] = A[amax[b][0]] + A[amax[b][1]]

for b in range(1, M):
  ret = sm[b]
  for i in range(1, N):
    if b & (1 << i) > 0:
      b2 = (b & ~(1 << i)) | ((1 << i) - 1)
      ret = max(ret, sm[b2])
  print(ret)

Submission status: Time Limit Exceeded

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

N = read()
A = reads()

M = 1 << N

def key(i):
  return -A[i] if i >= 0 else 0

amax = [None] * M
amax[0] = [0, -1]
for b in range(1, M):
  s = set()
  s.add(b)
  for i in range(N):
    if b & (1 << i) > 0:
      s.update(amax[b & ~(1 << i)])
  amax[b] = sorted(s, key=key)[:2]

sm = [0] * M
for b in range(M):
  sm[b] = A[amax[b][0]] + A[amax[b][1]]

# print(amax, file=stderr)

for b in range(1, M):
  ret = sm[b]
  for i in range(1, N):
    if b & (1 << i) > 0:
      b2 = (b & ~(1 << i)) | ((1 << i) - 1)
      ret = max(ret, sm[b2])
  print(ret)

Submission status: Time Limit Exceeded

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

for k in range(1, len(a)):
    maxij = 0
    for i in range(k):
        for j in range(i + 1, k + 1):
            if i | j <= k:
                v = a[i] + a[j]
                if v > maxij:
                    maxij = v
    print(maxij)

Submission status: Accepted

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

Submission status: Accepted

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

    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

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

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

Submission status: Accepted

Solution code:
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]:  # skip dp[0][i] == elem
        dp[1][i] = elem
        return True
    else:
        return False


dp = [[0] * len(As) for _ in range(2)]  # first largest and second largest
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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

# 参考
# https://qiita.com/Euglenese/items/260f9ddf513f772d7e42
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
"""

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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):#このkはKと違う，kbit目に着目する
        for s in range(N2):#これが今回でいうK，
            if ((s>>k)&1):#sのkbit目が立っていれば
                #加法として，上位2つを選択する
                L=[0,0,0,0]
                L[0]=g[s][0]
                L[1]=g[s][1]
                L[2]=g[(s^(1<<k))][0]#sのkbit目をマスクしたgを持ってくる
                L[3]=g[(s^(1<<k))][1]
                L.sort()
                g[s][0]=L[-1]
                g[s][1]=L[-2]
                #print(bin(s),k,g[s],L)
                
    ans=0
    for k in range(1,N2):
        ans=max(ans,sum(g[k]))
        print(ans)
        
    
                    
                
            
        
    
    

main()

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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]

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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