Problem:


Score : 700 points

Problem Statement

You are given N integers A_1, A_2, ..., A_N.

Consider the sums of all non-empty subsequences of A. There are 2^N - 1 such sums, an odd number.

Let the list of these sums in non-decreasing order be S_1, S_2, ..., S_{2^N - 1}.

Find the median of this list, S_{2^{N-1}}.

Constraints

1 \leq N \leq 2000

1 \leq A_i \leq 2000

All input values are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the median of the sorted list of the sums of all non-empty subsequences of A.

Sample Input 1

3
1 2 1

Sample Output 1

2

In this case, S = (1, 1, 2, 2, 3, 3, 4). Its median is S_4 = 2.

Sample Input 2

1
58

Sample Output 2

58

In this case, S = (58).



Sample input:
3
1 2 1


Sample output:
2

Submission status: Wrong Answer

Solution code:
#伝家の宝刀†二分探索†
N=int(input())
L=list(map(int,input().split()))
sita=1
ue=4000000
if N==1:
  print(L[0])
  exit()
#DP説
#2000*4000000
s=sum(L)
DP=[[0 for i in range(s+1)] for i in range(N)]
#DP[i][j]=まえからi個までの中からいくつか選んで合計値がjになる数
DP[0][0]=1
DP[0][L[0]]=1
for i in range(1,N):
  a=L[i]
  for j in range(s+1):
    if j>=a:
      DP[i][j]=DP[i-1][j]+DP[i-1][j-a]
    else:
      DP[i][j]=DP[i-1][j]
s=DP[-1]
ans=0
a=2**(N-1)
for i in range(len(s)):
  ans+=s[i]
  if ans>=a:
    print(i)
    exit()

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
if N==1:
  print(A[0])
  exit()
if N==2:
  print(A[1])
  exit()
L=sorted(A)
print(sum(L[N//4:(3*N)//4]))

Submission status: Wrong Answer

Solution code:
N=int(input())
L=list(map(int,input().split()))
L=sorted(L)
print(L[N//2])

Submission status: Wrong Answer

Solution code:
n=int(input())
A=[int(i) for i in input().split()]
dp=1

for i in range(n):
    now=A[i]
    dp=dp|(dp<<now)

for i in range(sum(A)//2,sum(A)+1):
    if dp&(1<<i)>0:
        print(i)
        break

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
a.sort()
s = sum(a)
target = s//2 if s%2==0 else s//2+1
l = 2001
dp = [[0]*(l) for _ in range(n+1)]
dp[0][0] = 1
v = 0
ans = float("inf")
for i in range(1, n+1):
    v += a[i-1]
    for j in range(0, l):
        dp[i][j] = dp[i-1][j]
        if j-a[i-1]>=0:
            dp[i][j] = max(dp[i][j], dp[i-1][j-a[i-1]])
        if dp[i][j]>0 and v-j>=target:
            ans = min(ans, v-j)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
a.sort()
s = sum(a)
target = s//2 if s%2==0 else s//2+1
l = 2001
dp = [[0]*(l) for _ in range(n+1)]
dp[0][0] = 1
v = 0
ans = float("inf")
for i in range(1, n+1):
    v += a[i-1]
    for j in range(0, min(v+1, l)):
        dp[i][j] = dp[i-1][j]
        if j-a[i-1]>=0:
            dp[i][j] = max(dp[i][j], dp[i-1][j-a[i-1]])
        if dp[i][j]>0 and v-j>=target:
            ans = min(ans, v-j)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
s = sum(a)
target = s//2 if s%2==0 else s//2+1
l = 2001
dp = [[0]*(l) for _ in range(n+1)]
dp[0][0] = 1
v = 0
ans = float("inf")
for i in range(1, n+1):
    v += a[i-1]
    for j in range(0, min(v+1, l)):
        dp[i][j] = dp[i-1][j]
        if j-a[i-1]>=0:
            dp[i][j] = max(dp[i][j], dp[i-1][j-a[i-1]])
        if dp[i][j]>0 and v-j>=target:
            ans = min(ans, v-j)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
s = sum(a)
target = s//2 if s%2==0 else s//2+1
l = min(s, 2001)
dp = [[0]*(l) for _ in range(n+1)]
dp[0][0] = 1
v = 0
ans = float("inf")
for i in range(1, n+1):
    v += a[i-1]
    for j in range(0, min(v+1, l)):
        dp[i][j] = dp[i-1][j]
        if j-a[i-1]>=0:
            dp[i][j] = max(dp[i][j], dp[i-1][j-a[i-1]])
        if dp[i][j]>0 and v-j>=target:
            ans = min(ans, v-j)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
s = sum(a)
a.sort()
b = 1
for i in a:
  b |= b<<i
  
b &= 2**(s+1)-2**((s-1)//2)
t = b&(-b)
print(t.bit_length()-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
s = sum(a)
a.sort()
b = 1
for i in a:
  b |= b<<i
  
def all_bit_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8) 
    x = x + (x >> 16) 
    x = x + (x >> 32) 
    return x & 0x0000007f

l = all_bit_count(b)
for i in range(l):
  t = b&(-b)
  if (s+1)//2 <= t.bit_length()-1 <= s:
    print(t.bit_length()-1)
    break
  b ^= t

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
s = sum(a)
a.sort()
b = 1
for i in a:
  b |= b<<i
  
def all_bit_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8) 
    x = x + (x >> 16) 
    x = x + (x >> 32) 
    return x & 0x0000007f
  

l = all_bit_count(b)
for i in range((l+1)//2):
  t = b&(-b)
  b ^= t
  
print(t.bit_length()-1)

Submission status: Wrong Answer

Solution code:
def examA():
    N = I()
    ans = 0
    print(ans)
    return

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

def examC():
    N = I()
    A = LI()
    dp = 1
    for i in range(N):
        dp |= dp<<A[i]
    S = sum(A)//2
    ans = -1
    for i in range(S,2*S+1):
        if dp&(1<<i)>0:
            ans = i
            break
    print(ans)
    return

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

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

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

from decimal import 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 = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examC()

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

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.insert(0, 0)
#print(A)

S = sum(A)

# 1～i番目までのAk要素を組み合わせて和を取り、jを作ることが可能か
#canMakePre =  [False] * (S+1)
canMake =  [False] * (S+1)
canMake[0] = True

for i in range(1, N+1) :
  """
  for j in range(1, S+1) : 
    canMake[j] = canMakePre[j]
  canMake[A[i]] = True
  """
  for j in range(S, A[i]-1, -1) : 
    canMake[j] = canMake[j] or canMake[j-A[i]]
  """
  for j in range(1, S+1) : 
    canMakePre[j] = canMake[j]
    """
#  print(i , canMake)

for j in range(S//2, S+1) :
  if canMake[j] :
    print(j)
    break

Submission status: Wrong Answer

Solution code:
import numpy as np

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

if N == 1:
    print(A[0])
    exit()
f = np.zeros(U + 10, np.int64)
f[0] = 1
for a in A:
    g = f.copy()
    f[a:] += g[:-a]


cnt = 0
for i in range(1,U):
    cnt += f[i]
    if cnt >= 2 ** (N-1):
        print(i)
        exit()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
d = sum(a)//2
c = 1
for x in a:
  c |= c << x
c >>= d
for i in range(d+5):
  if c & (1 << i):
    print(d+i)
    break

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**7)

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

def condition(val):
    memo={}
    def dfs(num,count):
        if count>val:
            return 0

        if (num,count) in memo:
            return memo[(num,count)]

        if num==N:
            memo[(num,count)]=int(val>count)
            return memo[(num,count)]

        ans=dfs(num+1,count+A[num])+dfs(num+1,count)
        memo[(num,count)]=ans
        return memo[(num,count)]

    return 2**(N-1)>dfs(0,0)

start=0
end=2000**2
while end-start>1:
    test=(start+end)//2
    if condition(test):
        start=test
    else:
        end=test

if condition(end):
    print(end)
else:
    print(start)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from itertools import accumulate
import bisect
n = int(input())
A = list(map(int, input().split()))
  
def li(n):
    L = []
    while n:
        L.append(n & ((1 << k) - 1))
        n >>= k
    return L
  
k = 12
s = 1 << sum(A)*k
for a in A:
  s += s >> a * k
L = li(s)
L[0] = 0
A = list(accumulate(L))
ans = bisect.bisect_left(A, 1<<(n-1))
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np


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

total_a = sum(a_list)

dp = np.array([0] * (sum(a_list) + 1), dtype=np.int32)
dp[0] = 1

accumulation = 0
for a in a_list:
    for i in range(accumulation, -1, -1):
        dp[i + a] += dp[i]
    accumulation += a

center = (1 << (n - 1))
accumulation = 0
for i in range(1, total_a + 1):
    accumulation += dp[i]
    if accumulation >= center:
        print(i)
        break

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(a) for a in input().split()]
s = 1
for a in A:
    s |= s << a

for i in range(sum(A)//2, sum(A)+1):
    if s & (1<<i):
        print(i)
        break

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(a) for a in input().split()]
s = 1
for a in A:
    s |= s * ((1 << a) + 1)

for i in range(sum(A)//2, sum(A)+1):
    if s & (1<<i):
        print(i)
        break

Submission status: Wrong Answer

Solution code:
n=input()
ans=max(list(map(int,input().split())))
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools 
if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split(" ")))
    A.sort()
    ans = []

    for i in range(1, N+1):
        ans.extend(list(map(sum, itertools.combinations(A, i))))
    print(ans[int(len(ans)/2)])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    A=list(map(int,input().split()))
    s=sum(A)

    dp=1
    for a in A:
        dp|=(dp<<a)

    for i in range(s//2,s+1):
        if((dp>>i)&1):
            print(i)
            return
resolve()

Submission status: Wrong Answer

Solution code:
_,a=open(0)
*a,=map(int,a.split())
d=1
for i in a:d|=d<<i
s=sum(a)//2
print(bin(d)[~s::-1].find('1')+s)

Submission status: Wrong Answer

Solution code:

n=int(input())
arr=[int(x) for x in input().split()]
sum = sum(arr) 
ans=[]
      
    # dp[i][j] would be true if arr[0..i-1]  
    # has a subset with Sum equal to j.  
dp = [[False for i in range(sum + 1)] for i in range(n + 1)]

                   
    # There is always a subset with 0 Sum  
for i in range(n + 1):
  dp[i][0] = True
  
    # Fill dp[][] in bottom up manner  
  for i in range(1, n + 1): 
    dp[i][arr[i - 1]] = True
    for j in range(1, sum + 1): 
      if (dp[i - 1][j] == True): 
        dp[i][j] = True
        dp[i][j + arr[i - 1]] = True
              
    # Print last row elements  
for j in range(sum + 1):
  if (dp[n][j] == True):
    ans.append(j)
print(ans[n//2])

Submission status: Wrong Answer

Solution code:
import numpy as np

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

exist = np.zeros(sum(A)+1, dtype=bool)
exist[0] = True
for a in A:
    exist[a:] |= exist[:-a]

for i in range((sum(A)+1) // 2, sum(A) + 1):
    if exist[i]:
        print(i)
        break

Submission status: Wrong Answer

Solution code:
import numpy as np

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

exist = np.zeros(sum(A)+1, dtype=bool)
exist[0] = 1
for a in A:
    exist[a:] |= exist[:-a]

for i in range((sum(A)+1) // 2, sum(A) + 1):
    if exist[i]:
        print(i)
        exit()

Submission status: Wrong Answer

Solution code:
import numpy as np

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

exist = np.zeros(sum(A)+1, dtype=bool)
exist[0] = True
for a in A:
    exist[a:] |= exist[:-a]

for i in range((sum(A)+1) // 2, sum(A) + 1):
    if exist[i]:
        print(i)
        exit()

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
S=sum(A)
SET=1
for a in A:
  SET|=SET<<a
print(bin(SET)[2+S//2:].index("1")+S//2)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
A = list(map(int, input().split()))

H = Counter()
H[0] = 1

for a in A:
    for k, v in H.copy().items():
        H[k+a] += v
del H[0]
ctr = 2 ** (N-1)
for v, k in sorted(((v, k) for k, v in H.items())):
    ctr -= v
    if ctr <= 0:
        break
print(k)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(a) for a in input().split()]

DP = [[False for i in range(max(A) * N + 1)] for n in range(N)]
DP[0][0], DP[0][A[0]] = True, True
maxN = A[0]
for i in range(1, N):
    a = A[i]
    for j in range(maxN+1):
        if DP[i-1][j]:
            DP[i][j] = True
            DP[i][j + a] = True
    maxN += a

for i in range(sum(A)//2, max(A) * N + 1):
    if DP[N-1][i]:
        print(i)
        break

Submission status: Wrong Answer

Solution code:
from math import ceil
N=int(input())
A=[int(i) for i in input().split()]
dp=1
for i in range(N):
  dp|=dp<<A[i]
S=sum(A)
hS=ceil(S/2)
for i in range(hS+1)[::-1]:
  if dp&(1<<i):
    ans=i
    break
print(S-i)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = [[] for i in range(n)]
b[0] = a[0]
if n == 1:
  print(a[0])
  exit()
b[1] = a[1]
for i in range(2,n):
  to = []
  to.append(b[i-1])
  to.append(b[i-2])
  to.append(a[i])
  to = sorted(to)
  if to[2] > to[0]+ to[1]:
    b[i] = to[2]
  else:
    b[i] = to[0] + to[1]
print(b[n-1])

Submission status: Wrong Answer

Solution code:
import itertools

in1 = int(input())
in2 = [int(x) for x in input().split()]

sum2 = sum(in2)
s = list()
for i in range(1, in1//2+1):
    lists = list(itertools.combinations(in2, i))
    s += [sum(x) for x in lists]
    s += [sum2 - sum(x) for x in lists]
if in1%2 == 1:
    lists = list(itertools.combinations(in2, in1//2+1))
    s += [sum(x) for x in lists]

s.sort()
mid = 2**(in1-1) - 1
print(s[mid])

Submission status: Wrong Answer

Solution code:
# seishin.py
N = int(input())
*A, = map(int, input().split())
S = sum(A)

b = 1
for a in A:
    b |= 1 << a
b >>= S // 2
print((b & -b).bit_length() - 1 + S // 2)

Submission status: Wrong Answer

Solution code:
n = int(input())
arr = list(map(int, input().split()))
sa = sum(arr)
dp = 1 << (arr[0] - 1)

for a in arr[1:]:
    dp |= dp << a

ofs = (sa - 1) // 2
hdp = dp >> ofs
print((hdp & -hdp).bit_length() + ofs)

Submission status: Wrong Answer

Solution code:
n = int(input())
arr = list(map(int, input().split()))
dp = 1 << (arr[0] - 1)

for a in arr[1:]:
    dp |= dp << a

ts = 1 << ((dp.bit_length() + 1) // 2 - 1)
while not dp & ts:
    ts <<= 1

print(ts.bit_length())

Submission status: Wrong Answer

Solution code:
n = int(input())
arr = list(map(int, input().split()))
dp = 1

for a in arr:
    dp |= dp << a

ts = 1 << ((dp.bit_length() + 1) // 2 - 1)
while not dp & ts:
    ts <<= 1

print(ts.bit_length())

Submission status: Wrong Answer

Solution code:
n = int(input())
arr = list(map(int, input().split()))
dp = 1

for a in arr:
    dp |= dp << a

ts = 1 << (dp.bit_length() - 1)
while not dp & ts:
    ts <<= 1

print(ts.bit_length())

Submission status: Wrong Answer

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

#
if N%2==0:
    print(max(sum(A[1:N//2 + 1]), A[0]+sum(A[N//2 + 1:])))
else:
    print(max(sum(A[:N//2 + 1]), sum(A[N//2 + 1:])))

Submission status: Wrong Answer

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

#
if N%2==0:
    print(sum(A[1:N//2 + 1]))
else:
    print(sum(A[:N//2 + 1]))

Submission status: Wrong Answer

Solution code:
import sys, math
import numpy as np

DEBUG = False

def ni():
    return int(input())
def nia():
    return list(map(int,input().split()))
def merge(invs):
    merged = [invs[0]]
    for i in range(1, len(invs)):
        if invs[i][0] - merged[-1][1] <= 1:
            merged[-1][1] = invs[i][1]
        else:
            merged.append(invs[i])
    return np.array(merged, dtype=np.int32)

n = ni()
a = nia()

b = np.array([[0,0]])

for x in sorted(a):
    b = np.vstack([b, b + x])
    idx = np.argsort(b[:,0])
    b = b[idx]
    b = merge(b)

if len(b) % 2 == 0:
    print(b[len(b) // 2][0])
else:
    c = b[len(b) // 2]
    n = c[1] - c[0] + 1
    if n % 2 == 0:
        print(c[0] + n // 2)
    else:
        print(c[0] + n // 2)

Submission status: Wrong Answer

Solution code:
n=int(input())
tmp=input().split(' ')
a=[int(tmp[i]) for i in range(n)]
s=sum(a)
mx=max(a)
d={}
for i in range(n):
	d1={}
	d1[a[i]]=1
	for x in d:
		d1[x]=1
		if (x+a[i])*2<s+mx*2:
			d1[x+a[i]]=1
	d=d1
ans=mx*n
for x in d:
	if (x*x>=s):
		ans=min(ans,x)
print(ans)

Submission status: Wrong Answer

Solution code:
# coding=utf-8

N = int(input())
dp = 1
asum = 0
for a in input().split(" "):
    x = int(a)
    asum += x
    dp = dp|(dp<<x)

for i in range(asum//2, asum+1):
    if (dp>>i)&1:
        print(i)
        break

Submission status: Wrong Answer

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

sumA = sum(A)
halfA = math.ceil(sumA / 2)
bitset = 1
for a in A:
  bitset |= bitset << a

bitset >>= halfA
for i in range(halfA):
  if bitset & 1:
    print(i+halfA)
    exit()
  bitset >>= 1

Submission status: Wrong Answer

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

dp = 1
for x in a:
  dp |= dp << x

s = sum(a)
dp >>= s // 2
dp <<= s // 2
dp = bin(dp)

print(len(dp) - len(dp.rstrip('0')))

Submission status: Wrong Answer

Solution code:
from itertools import combinations

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

if N % 2 == 1:
    num = int(N / 2) + 1
    print(sum(A[:num]))
else:
    comb = list(combinations(A, int(N / 2)))
    SUM = [sum(c) for c in comb]
    SUM.sort()
    print(SUM[int(len(SUM) / 2)])

Submission status: Wrong Answer

Solution code:
from statistics import median
N = int(input())
s = list(input().split())
numbers = []
if N == 1:
    print(s[0])
else:
    for i in range(N):
        numbers.append(int(s[i]))
    numbers.sort()
    answers = []
    for i in range(N):
        answers.append(numbers[i])
    a = 0
    for i in range(N):
        a += numbers[i]
    answers.append(a)
    a = 0
    for i in range(N):
        for j in range(N):
            a += numbers[i]
            answers.append(a)
        a = 0
    answers.sort()
    print(int(median(answers)))

Submission status: Wrong Answer

Solution code:
from pprint import pprint as pp
import collections
import math
import statistics

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

result = []
for width in range(1, N+1):
  result.append(sum(A[:width]))
  for i in range(N - width+1):
    result.append(sum(A[i:i+width]))
print(statistics.median(result))

Submission status: Wrong Answer

Solution code:
from statistics import median
N = int(input())
s = list(input().split())
numbers = []
if N == 1:
    print(s[0])
else:
    for i in range(N):
        numbers.append(int(s[i]))
    numbers.append(0)
    numbers.sort()
    answers = []
    a = 0
    for i in range(N+1):
        a += numbers[i]
    a = 0
    for i in range(N):
        for j in range(N):
            a += numbers[i]
            answers.append(a)
        a = 0
    answers.sort()
    P = answers.count(0)
    print(answers)
    for i in range(P):
        answers.remove(0)
    print(int(median(answers)))

Submission status: Wrong Answer

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

sum_a = sum(A)
cnt = [0 for _ in range(sum_a + 1)]
cnt[0] = 1

for a in A:
    for j in range(a, len(cnt))[::-1]:
        cnt[j] += cnt[j - a]

print(A)
print(cnt)

target = 2 ** (N - 1)
s = 0
for i, c in enumerate(cnt[1:]):
    s += c
    if target <= s:
        print(i + 1)
        break

Submission status: Wrong Answer

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

sum_a = sum(A)
cnt = [0 for _ in range(sum_a + 1)]
cnt[0] = 1

for a in A:
    for j in range(a, len(cnt))[::-1]:
        cnt[j] += cnt[j - a]

print(A)
print(cnt)

target = 2 ** (N - 1)
s = 0
for i, c in enumerate(cnt):
    s += c
    if target <= s:
        print(i)
        break

Submission status: Wrong Answer

Solution code:
from itertools import combinations

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

if N % 2 == 1:
    num = int(N / 2) + 1
    print(sum(A[:num]))
else:
    comb = combinations(A, int(N / 2))
    SUM = [sum(c) for c in comb]
    SUM.sort()
    print(SUM[int(N / 2)])

Submission status: Wrong Answer

Solution code:
import itertools
import sys

def comb(n, k):
    m = 1
    if n < 2 * k:
        k = n - k
    for i in range(1, k + 1):
        m = m * (n - i + 1) / i
    return m

def main():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    #部分列の和を1番目から数えたk番目の要素がtarget
    target = 2**(n - 1)
    counter = 0
    for i in range(1, n + 1):
        len_of_lis = comb(n, i)

        if len_of_lis + counter >= target:
            list_of_check = list(itertools.combinations(a, i))
            print(sum(list_of_check[int(target - 1 - counter)]))
            sys.exit()
        else:
            counter += len_of_lis

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N=input()
a=map(int,raw_input().split())
sum_a=sum(a)
if N==1:
	print sum_a
else:
	print sum_a/2 if sum_a%2==0 else sum_a/2+1

Submission status: Wrong Answer

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

if N % 2 == 1:
    num = int(N / 2) + 1
    print(sum(A[:num]))
else:
    print(sum(A[:int(N / 4)]) + sum(A[int(N * 3 / 4):]))

Submission status: Wrong Answer

Solution code:
import itertools
import sys
n = int(input())
a = list(map(int, input().split()))
a.sort()
#部分列の和を1番目から数えたk番目の要素がtarget
target = 2**(n - 1)
counter = 0
for i in range(1, n + 1):
    list_of_check = list(itertools.combinations(a, i))
    if len(list_of_check) + counter >= target:
        print(sum(list_of_check[target - 1 - counter]))
        sys.exit()
    else:
        counter += len(list_of_check)

Submission status: Wrong Answer

Solution code:
from numpy.polynomial import polynomial as P
n = int(input())
A = list(map(int,input().split()))
def DC(l,r):
    if r - l == 1:
        return [1 if i == 0 or i == A[l] else 0 for i in range(A[l]+1)]
    m = (l + r) // 2
    return P.polymul(DC(l,m), DC(m,r))

A.sort()
for i in range(1,n,2):
    if i + n//2 >= n:
        break
    A[i], A[i+n//2] = A[i+n//2], A[i]
S = DC(0,len(A))
m = 2**(n-1)
t = 0
k = 1
while k < len(S):
    y = t + S[k]
    if y < m:
        t = y
        k+=1
    else:
        break
print(k)

Submission status: Wrong Answer

Solution code:
import itertools

N = int(input())
A_LIST = sorted(list(map(int, input().split(' '))))

if N == 1:
    print(A_LIST[0])

else:
    s_list = []
    for i in range(N):
        s_list.extend([sum(comb) for comb in itertools.combinations(A_LIST, (i + 1))])

    print(sorted(s_list)[2**(N - 1)] - 1)

Submission status: Wrong Answer

Solution code:
import itertools

def solve():
    n = int(input())
    A = list(set(map(int, input().split(" "))))
    sum_list = []
    for i in range(1, n + 1):
        for ele in list(itertools.combinations(A, i)):
            sum_list.append(sum(ele))

    sum_list.sort()
    length = len(sum_list)
    print(sum_list[length // 2])

solve()

Submission status: Wrong Answer

Solution code:
from numpy.polynomial import polynomial as P
n = int(input())
A = list(map(int,input().split()))
def DC(l,r):
    if r - l == 1:
        return [1 if i == 0 or i == A[l] else 0 for i in range(A[l]+1)]
    m = (l + r) // 2
    return P.polymul(DC(l,m), DC(m,r))
S = DC(0,len(A))
m = 2**(n-1)
t = 0
k = 1
while k < len(S):
    y = t + S[k]
    if y < m:
        t = y
        k+=1
    else:
        break
print(k)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

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

target = 2**(N - 1)
num = 0
for i in range(N):
    comb = list(combinations(A, i + 1))
    length = len(list(comb))
    if target < num + length:
        break
    num += length

diff = target - num - 1
print(sum(comb[diff]))

Submission status: Wrong Answer

Solution code:
import itertools
import sys
n = int(input())
a = list(map(int, input().split()))
a.sort()
#部分列の和を0番目から数えたk番目の要素がtarget
target = (2**n - 1) // 2
counter = 0
for i in range(1, n + 1):
    if len(list(itertools.combinations(a, i))) - 1 + counter >= target:
        print(sum(list(itertools.combinations(a, i))[target - counter]))
        sys.exit()
    else:
        counter += len(list(itertools.combinations(a, i)))

Submission status: Wrong Answer

Solution code:
import itertools

in1 = int(input())
in2 = [int(x) for x in input().split()]

s = list()
for i in range(1, in1+1):
    lists = list(itertools.combinations(in2, i))
    s += [sum(x) for x in lists]

s.sort()
smid = 2**in1 - 3
print(s[smid])

Submission status: Wrong Answer

Solution code:
input()
print(max(map(int, input().split())))

Submission status: Wrong Answer

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

A = sorted(A, reverse = True)
print(A[0])

Submission status: Time Limit Exceeded

Solution code:
#伝家の宝刀†二分探索†
N=int(input())
L=list(map(int,input().split()))
sita=1
ue=4000000
if N==1:
  print(L[0])
  exit()
#DP説
#2000*4000000
s=sum(L)
DP=[[0 for i in range(s+1)] for i in range(N)]
#DP[i][j]=まえからi個までの中からいくつか選んで合計値がjになる数
DP[0][0]=1
DP[0][L[0]]=1
for i in range(1,N):
  a=L[i]
  for j in range(s+1):
    if j>=a:
      DP[i][j]=DP[i-1][j]+DP[i-1][j-a]
    else:
      DP[i][j]=DP[i-1][j]
s=DP[-1]
ans=0
a=2**(N-1)+1
for i in range(len(s)):
  ans+=s[i]
  if ans>=a:
    print(i)
    exit()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
s = sum(a)
a.sort()
b = 1
for i in a:
  b |= b<<i
  
while True:
  t = b&(-b)
  if (s+1)//2 <= t.bit_length()-1 <= s:
    print(t.bit_length()-1)
    break
  b ^= t

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.insert(0, 0)
#print(A)

S = sum(A)

# 1～i番目までのAk要素を組み合わせて和を取り、jを作ることが可能か
canMakePre =  [False] * (S+1)
canMake =  [False] * (S+1)

for i in range(1, N+1) :
  for j in range(1, S+1) : 
    canMake[j] = canMakePre[j]
  canMake[A[i]] = True
  for j in range(A[i]+1, S+1) : 
    canMake[j] = canMake[j] or canMakePre[j-A[i]]
  for j in range(1, S+1) : 
    canMakePre[j] = canMake[j]
#  print(i , canMake)

for j in range(int(S/2) if S % 2 == 0 else int(S/2) + 1, S+1) :
  if canMake[j] :
    print(j)
    break

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))

dp = defaultdict(int)
dp[0] = 1

for a in A:
    newDP = defaultdict(int)
    for k, v in dp.items():
        newDP[k] += v
        newDP[k + a] += v
    dp = newDP

m = pow(2, N - 1)
cnt = 0

for k in sorted(dp.keys())[1:]:
    cnt += dp[k]
    if cnt >= m:
        break

print(k)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**7)

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

def condition(val):
    memo={}
    def dfs(num,count):
        if count>=val:
            return 0

        if (num,count) in memo:
            return memo[(num,count)]

        if num==N:
            memo[(num,count)]=int(val>count)
            return memo[(num,count)]

        ans=dfs(num+1,count+A[num])+dfs(num+1,count)
        memo[(num,count)]=ans
        return memo[(num,count)]

    return 2**(N-1)>dfs(0,0)-1

start=0
end=2000**2
while end-start>1:
    test=(start+end)//2
    if condition(test):
        start=test
    else:
        end=test

if condition(end):
    print(end)
else:
    print(start)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[int(x) for x in input().split()]
b=[[]]
for i in a:
  b+=[[i]+j for j in b]

c=b[1:]
d=[]
for i in c:
  d.append(sum(i))
d=sorted(d)
k=len(d)
if(k%2==0):
  print((d[(k//2)-1] + d[k//2])/2.0)
else:
  print(d[k//2])

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[int(x) for x in input().split()]
b=[[]]
for i in a:
  b+=[[i]+j for j in b]
c=sorted(b)
c=c[1:]
d=[]
for i in c:
  d.append(sum(i))
d=sorted(d)
k=len(d)
if(k%2==0):
  print((d[(k//2)-1] + d[k//2])/2.0)
else:
  print(d[k//2])

Submission status: Time Limit Exceeded

Solution code:
import math
N=int(input())
A=list(map(int,input().split()))
#print(A)

S=math.ceil(sum(A)/2)

#print(S)

D=dict()
D[0]=0
#print(D)
for i in A:
    #print(A)
    d=dict()
    for j in D:
        #print(i,j)
        if j<=S:
            d[i+j]=1
            d[j]=1
        else:
            d[j]=1
    D=d
    #print(D)
#print(D)
ans=10**9
for i in D:
    if i>=S and i<ans:
        ans=i
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil
N = int(input())
A = [int(a) for a in input().split()]

DP = [[False for i in range(max(A) * N + 1)] for n in range(N)]
DP[0][0], DP[0][A[0]] = True, True
maxN = A[0]
for i in range(1, N):
    a = A[i]
    for j in range(maxN+1):
        if DP[i-1][j]:
            DP[i][j] = True
            DP[i][j + a] = True
    maxN += a

for i in range(ceil(sum(A)/2), max(A) * N + 1):
    if DP[N-1][i]:
        print(i)
        break

Submission status: Time Limit Exceeded

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

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

sys.setrecursionlimit(10000000)

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

m_p2 = {}
def p2(num):
    if num in m_p2:
        return m_p2[num]
    if num == 0:
        m_p2[num] = 1
        return 1
    m_p2[num] = p2(num - 1) * 2
    return m_p2[num]

ans = 1
for num in A:
    ans |= ans * p2(num)

S = sum(A)
mid = S / 2 + S % 2

for i in range(mid, S + 1):
    if ans & p2(i):
        print i
        break