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

Submission status: Time Limit Exceeded

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]))
    s.sort(key = lambda x:a[x])
    return (s[-1], s[-2])

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

Solution code:
def max2(p, q):
    s = list(set(p+q))
    s.sort(key = lambda x:a[x], reverse = True)
    return s[:2]

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

Solution code:
def max2(p, q):
    s = list(set(p+q))
    s.sort(key = lambda x:a[x], reverse = True)
    return s[:2]

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)])
for i in range(1, 1<<n):
    res = max(res, a[g[i][0]]+a[g[i][1]])
    print(res)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
L=[0 for i in range(2**N)]
for i in range(2**N-1):
    for j in range(i+1,2**N):
        L[i|j]=max(L[i|j],A[i]+A[j])
        #print(L)
for i in range(1,len(L)):
    L[i]=max(L[i],L[i-1])
for i in range(1,2**N):
    print(L[i])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = [[i, 1<<n] for i in range(len(a))]
a.append(-float("inf"))

def update(a1, a2):
    a1.extend(a2)
    return sorted(set(a1), key=lambda x: -a[x])[:2]

for j in range(n):
    for i in range(1<<n):
        if i & (1<<j):
            b[i] = update(b[i], b[i & ~(1<<j)])
ans = []
tmp = 0
for i in range(1, 1<<n):
    tmp = max(tmp, a[b[i][0]]+a[b[i][1]])
    ans.append(tmp)
print(*ans, sep="\n")

Submission status: Time Limit Exceeded

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

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

m = 1<<n
ans = [0]*m

for i in range(1, m):
    max1 = max2 = 0
    j = i
    while j >= 0:
        j &= i
        if a[j] >= max1:
            max1, max2 = a[j], max1
        elif a[j] > max2:
            max2 = a[j]
        j -= 1
    ans[i] = max(ans[i-1], max1+max2)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter

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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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] = [(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
        dp[next_k] = list(sorted(set(dp[next_k] + dp[k])))[-2:]
    # for d in digits:
    #     if k & d == 0:
    #         dp[k | d] = list(sorted(set(dp[k | d] + dp[k])))[-2:]

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

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

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

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

for k in range(1, 2 ** N):
    for d in digits:
        if k & d == 0:
            dp[k | d] = list(sorted(set(dp[k | d] + dp[k])))[-2:]

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

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

Submission status: Time Limit Exceeded

Solution code:
import heapq
import os
import sys

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

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


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

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


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

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

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

for k in range(1, 2 ** N):
    dp[k] = set(heapq.nlargest(2, dp[k]))
    for d in digits:
        if k & d == 0:
            dp[k | d] |= dp[k]

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

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

Submission status: Time Limit Exceeded

Solution code:
import heapq
import os
import sys

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

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


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

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


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

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

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

nums = set(digits[:])
while nums:
    next_nums = set()
    for k in nums:
        dp[k] = set(heapq.nlargest(2, dp[k]))
        for d in digits:
            if k | d > k:
                dp[k | d] |= dp[k]
                next_nums.add(k | d)
    nums = next_nums

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

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

Submission status: Time Limit Exceeded

Solution code:
import heapq
import itertools
import os
import sys

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

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


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

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


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

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

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

for bit in range(2, N + 1):
    for ds in itertools.combinations(digits, bit):
        k = sum(ds)
        for rm in ds:
            dp[k] |= dp[k - rm]
        dp[k] = set(heapq.nlargest(2, dp[k]))

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

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

Submission status: Time Limit Exceeded

Solution code:
import itertools
import os
import sys

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

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


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

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


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

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

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import itertools
import os
import sys

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

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


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

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


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

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

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

for bit in range(2, N + 1):
    for ds in itertools.combinations(digits, bit):
        k = sum(ds)
        for rm in ds:
            dp[k] += dp[k - rm]
        ss = sorted(set(dp[k]))
        dp[k] = ss[-1], ss[-2]

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

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

Submission status: Time Limit Exceeded

Solution code:
import itertools
import os
import sys

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

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


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

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


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

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

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import itertools
import os
import sys

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

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


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

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


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

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

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import itertools
import os
import sys

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

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

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

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

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

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

ans = [0] * (2 ** N)
for k in range(1, 2 ** N):
    (a1, _), (a2, _) = dp[k]
    ans[k] = a1 + a2
ans = itertools.accumulate(ans[1:], max)
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from heapq import nlargest
from itertools import accumulate

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

a0 = aaa[0]
dp = [[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: Time Limit Exceeded

Solution code:
from heapq import nlargest
from itertools import accumulate

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

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

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

Submission status: Time Limit Exceeded

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

Solution code:
from operator import itemgetter

import numpy as np

n = int(input())
aaa = list(enumerate(map(int, input().split())))
n2 = 1 << n
arr = np.arange(n2, dtype=np.uint)
bit = np.zeros(n, dtype=np.uint)
mat = np.zeros((n, n2))
for i in range(n):
    b = 1 << i
    bit[i] = b
    mat[i] = (arr & b) > 0
count = np.zeros(n2, dtype=np.uint8)
ans = np.zeros(n2, dtype=np.uint)
aaa.sort(reverse=True, key=itemgetter(1))
for i, a in aaa:
    idx = mat[(bit & i).astype(bool)].all(axis=0) & (count < 2)
    ans[idx] += a
    count[idx] += 1
ans = np.maximum.accumulate(ans[1:])
print(*ans)

Submission status: Time Limit Exceeded

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:]:
    ans = max(ans, a+b)
    Ans.append(ans)
print("\n".join(map(str, Ans)))

Submission status: Time Limit Exceeded

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])]
for a, b in f[2:]:
    Ans.append(max(Ans[-1], a+b))
print("\n".join(map(str, Ans)))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
f = [[a, -1] for a in A]
for i in range(N):
    bit = 1<<i
    j = 0
    while j < 1<<N:
        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])]
for a, b in f[2:]:
    Ans.append(max(Ans[-1], a+b))
print("\n".join(map(str, Ans)))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from heapq import nlargest
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] = nlargest(2, f[j]+f[j^(1<<i)])
Ans = [sum(f[1])]
for v in f[2:]:
    Ans.append(max(Ans[-1], sum(v)))
print("\n".join(map(str, Ans)))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from heapq import nlargest
N = int(input())
A = list(map(int, input().split()))
f = [[a] for a in A]
for i in range(N):
    bit = 1<<i
    for j in range(1<<N):
        if j & bit:
            f[j] = nlargest(2, f[j]+f[j^bit])
Ans = [sum(f[1])]
for a, b in f[2:]:
    Ans.append(max(Ans[-1], a+b))
print("\n".join(map(str, Ans)))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from heapq import nlargest
N = int(input())
A = list(map(int, input().split()))
f = [[a] for a in A]
for i in range(N):
    bit = 1<<i
    for j in range(1<<N):
        if j & bit:
            f[j] = nlargest(2, f[j]+f[j^bit])
Ans = [sum(f[1])]
for v in f[2:]:
    Ans.append(max(Ans[-1], sum(v)))
print("\n".join(map(str, Ans)))

Submission status: Time Limit Exceeded

Solution code:
# YouTube

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

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

n = int(input())
f(n)

Submission status: Time Limit Exceeded

Solution code:
# YouTube

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

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

Submission status: Time Limit Exceeded

Solution code:
from heapq import *

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

Submission status: Time Limit Exceeded

Solution code:
from heapq import *

n = int(input())
nn = 2 ** n
aa = list(map(int, input().split()))
hp = []
ans = [-1] * nn
for i in range(nn-1):
    for j in range(i+1,nn):
        heappush(hp, [-(aa[i]+aa[j]), i|j])
r=nn
i=2
while i>1:
    s, i = heappop(hp)
    if ans[i]==-1:
        for ii in range(i,r):
            ans[ii]=-s
        r=i
for x in ans[1:]:
    print(x)

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

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

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

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

answer = itertools.accumulate([x+y for (x,i),(y,j) in B[1:]], max)
print('\n'.join(map(str,answer)))

Submission status: Time Limit Exceeded

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

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

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

answer = itertools.accumulate([x+y for (x,i),(y,j) in B[1:]], max)
print('\n'.join(map(str,answer)))

Submission status: Time Limit Exceeded

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

N2 = (1<<N)
dp= [ [0,-1,0,-1] for i in range(N2) ]

for i in range(N2):
  #print ("*",i)
  m = 1
  f1 = li[i]
  i1 = i
  f2 = 0
  i2 = -1
  for j in range(N):
    k = i^m
    if ( i|k==i ):
      #print (k)
      pf1,pi1,pf2,pi2= dp[k]
      tm = [ (pf1,pi1),(pf2,pi2),(f1,i1),(f2,i2), ] 
      tm.sort( key=lambda x:-x[0] )
      if ( tm[0][1] != tm[1][1] ):
        f1,i1=tm[0]
        f2,i2=tm[1]
      elif ( tm[0][1] != tm[2][1] ):
        f1,i1=tm[0]
        f2,i2=tm[2]
      elif ( tm[0][1] != tm[3][1] ):
        f1,i1=tm[0]
        f2,i2=tm[3]
      #print ( f1,i1,f2,i2 )
    m<<=1
  dp[i] = [f1,i1,f2,i2]
  #print ( dp[i] )
ma = 0
for i in range(1,N2):
  a,_,b,_ = dp[i]
  ma = max(ma,a+b)
  print ( ma )