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

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = LI()
    s = sum(a)
    t = 1
    m = 2**(s//2+1)
    for c in a:
        t |= t << c
    t %= m

    return s - (t.bit_length() - 1)


print(main())

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = LI()
    s = sum(a)
    t = 1
    m = 2**(s//2+1)
    for c in a:
        t |= t << c
    t %= m

    return s - (len(bin(t)) - 3)


print(main())

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = LI()
    s = sum(a)
    t = 1
    m = 2**(s//2+1)
    for c in a:
        t |= t << c
        t %= m

    return s - (len(bin(t)) - 3)


print(main())

Submission status: Time Limit Exceeded

Solution code:
from statistics import mean, median,variance,stdev
import sys

sys.setrecursionlimit(10000)

n = int(input())
lis = list(map(int, input().split()))
ans_list = []

def dfs(i, su):
    # n個決め終わった時
    if i == n:
        if su != 0:
            ans_list.append(su)
        return
    dfs(i + 1, su)
    dfs(i + 1, su + lis[i])


dfs(0, 0)
print(median(list(sorted(ans_list))))

Submission status: Time Limit Exceeded

Solution code:
def getv(x,i):
	return (x>>i)&1
def setv(x,i,k):
	x=x&~(1<<i)
	x=x|(k<<i)
	return x
n=int(input())
tmp=input().split(' ')
a=[int(tmp[i]) for i in range(n)]
f=[0,0]
g=0
for i in range(n):
	t=f[g]
	t<<=a[i]
	t=setv(t,a[i],1)
	f[g^1]=f[g]|t
	g^=1

ans=(sum(a)+1)//2
while (not getv(f[g],ans)): ++ans
print(ans)

Submission status: Time Limit Exceeded

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

sumA = sum(A)
ct = {0:1}

for a in A:
  nct = {}
  for k in ct:
    nct[k] = nct.get(k, 0) + ct[k]
    nct[k+a] = nct.get(k+a, 0) + ct[k]
  ct = nct

ct[0] = 0
medidx = (2**N)//2
n = 0
keys = list(ct.keys())
keys.sort()
for key in keys:
  n += ct[key]
  if n >= medidx:
    print(key)
    exit()

Submission status: Time Limit Exceeded

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

sumA = sum(A)
ct = {0:1}

for a in A:
  nct = {}
  for k in ct:
    nct[k] = nct.get(k, 0) + ct[k]
    nct[k+a] = nct.get(k+a, 0) + ct[k]
  ct = nct

ct[0] = 0
medidx = (2**N)//2
n = 0
for i in range(sumA+1):
  n += ct.get(i, 0)
  if n >= medidx:
    print(i)
    exit()

Submission status: Time Limit Exceeded

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]

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

Submission status: Time Limit Exceeded

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

ct = [0]*(sum(A)+1)
ct[0] = 1
ctlen = len(ct)

for a in A:
  for i in range(ctlen-a-1,-1,-1):
    ct[i+a] += ct[i]

ct[0] = 0
medidx = (2**N)//2
n = 0
for i in range(ctlen):
  n += ct[i]
  if n >= medidx:
    print(i)
    exit()

Submission status: Time Limit Exceeded

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

import itertools

s = []
for i in range(n):
    s.extend([sum(j) for j in list(itertools.combinations(a, n-i))])
s = sorted(s)
print(s[len(s)//2])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# coding=utf-8

from itertools import chain, combinations
import sys


def powerset(iterable):
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s) + 1))


n = int(sys.stdin.readline().strip())
a = list(map(int, sys.stdin.readline().strip().split(" ")))
print(sorted([sum(ps) for ps in list(powerset(a))[1:]])[2**(n-1)-1])

Submission status: Time Limit Exceeded

Solution code:
import itertools

def solve():
    n = int(input())
    A = list(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: Time Limit Exceeded

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()
mid = 2**(in1-1) - 1
print(s[mid])

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
from collections import defaultdict
from itertools import accumulate

n = int(input())
arr = list(map(int, input().split()))
arr.sort()
sa = sum(arr)
lim = sa // 2
dp = defaultdict(int)
dp[0] = 1

for a in arr:
    # print(a, dp)
    ndp = dp.copy()
    for i, v in dp.items():
        if i + a <= lim:
            ndp[i + a] += v
    dp = ndp
    # print(a, dp)

dpk = list(dp.keys())
dpk.sort()
dpv = [dp[k] for k in dpk]
adp = list(accumulate(dpv))
k = 2 ** (n - 1)
j = bisect_left(adp, k)

# print(adp)
# print(k)

print(sa - dpk[j])

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
from itertools import accumulate

n = int(input())
arr = list(map(int, input().split()))
sa = sum(arr)
lim = sa // 2
dp = [0] * (lim + 1)
dp[0] = 1
mx = 0

for a in arr:
    # print(a, dp)
    for i in range(min(mx, lim - a), -1, -1):
        if dp[i]:
            dp[i + a] += dp[i]
    # print(a, dp)
    mx = max(mx + a, lim)

adp = list(accumulate(dp))
k = 2 ** (n - 1)

# print(adp)
# print(k)

print(sa - bisect_left(adp, k))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[int(i) for i in input().split(' ')]
nn=sum(a)+1
dp=[0]*(nn)
dp[a[0]]=1
dp[0]=1
for i in a[1:]:
    dp=[dp[x]+dp[x-i] if x-i>=0 else dp[x] for x in range(nn)]
ct=1<<(n-1)
for i in range(nn):
    ct-=dp[i]
    if(ct<0):
        print(i)
        break

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort()
# print(N,A)
dp = [0] * (4000001)
dp[0]=1
for i in range(N):
    for x in range(400000, A[i]-1, -1):
        dp[x] += dp[x-A[i]]
dp[0]=0
for i in range(4000001):
    dp[i] += dp[i-1]
z = 2**(N-1)
for i in range(1, 4000001) :
    if( dp[i] >= z ) :
        print(i)
        break

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
s = [0]
for i in range(n):
    for j in range(len(s)):
        s.append(s[j] + a[i])
s.sort()
print(s[int(len(s)/2)])

Submission status: Memory Limit Exceeded

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 for _ in range(n+1)]
dp[0] = 1
for i in range(1, n+1):
    dp[i] = dp[i-1] | (dp[i-1]<<a[i-1])
ans = float("inf")
for i in range(target, s+1):
    if (dp[n]>>i&1)==1:
        ans = min(ans, i)
        break
print(ans)

Submission status: Accepted

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)+1)//2,sum(A)+1):
    if dp&(1<<i)>0:
        print(i)
        break

Submission status: Accepted

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
dp = 1
for i in range(1, n+1):
    dp = dp | (dp<<a[i-1])
ans = float("inf")
for i in range(target, s+1):
    if (dp>>i&1)==1:
        ans = min(ans, i)
        break
print(ans)

Submission status: Accepted

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

n = int(input())
A = tuple(map(int, input().split()))
M = sum(A)
l = -(-M//2)
dp = 1
mask = (1<<(2*M))-1
for a in A:
  dp |= (dp<<a)&mask
dp >>= l
ans = (dp&(-dp)).bit_length() - 1 + l
print(ans)

Submission status: Accepted

Solution code:
N, *A = map(int, open(0).read().split())

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

cur = (sum(A) + 1) // 2
while (dp >> cur) & 1 == 0:
    cur += 1

print(cur)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, *A = map(int, read().split())

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

S = bin(dp)[2:][::-1]

can_make = [i for i, x in enumerate(S) if x == '1']
n = len(can_make)
x = can_make[n // 2]
print(x)

Submission status: Accepted

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

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)
while True:
  t = b&(-b)
  T = t.bit_length()-1
  if (s+1)//2 <= T <= s:
    print(T)
    break
  b ^= t

Submission status: Accepted

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)
while True:
  t = b&(-b)
  #print(i,t,b)
  if (s+1)//2 <= t.bit_length()-1 <= s:
    print(t.bit_length()-1)
    break
  b ^= t

Submission status: Accepted

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

sum_a = sum(a)

dp = 1
for i in range(n):
    dp |= dp << a[i]

for i in range((sum_a + 1) // 2, sum_a + 1):
    if dp & (1 << i):
        print(i)
        exit()

Submission status: Accepted

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)+1)//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: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
sm = sum(a)
dp = 1
for i in range(N): dp |= (dp << a[i])
#print(dp)
x = 1 << ((sm + 1) // 2)
for i in range((sm + 1) // 2 + 1):
  if dp & x:
    print((sm + 1) // 2 + i)
    break
  x <<= 1

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
d = (sum(a)+1)//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: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
S=sum(A)
if S%2==1:
    check=1
    for i in range(N):
        check=check|check<<A[i]
    for i in range(S//2+1,S+1):
        if check>>i &1==1:
            print(i)
            break
else:
    check=1
    for i in range(N):
        check=check|check<<A[i]

    for i in range(S//2,S+1):
        if check>>i &1==1:
            print(i)
            break

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
A = list(map(int, input().split()))
M = sum(A)

s = 1 << M
for a in A:
  s |= s >> a
ans = bin(s)[2+(M+1)//2:].find("1") + (M+1)//2
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
S = sum(A)
M = (S+1)//2

dp = 1
for a in A:
    dp |= (dp<<a)
ans = M
while 1:
    if dp&(1<<ans):
        print(ans)
        exit()
    ans += 1

Submission status: Accepted

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)+1)//2, sum(A)+1):
    if s & (1<<i):
        print(i)
        break

Submission status: Accepted

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

ss = bin(s)
for i in range((sum(A)+1)//2, sum(A)+1):
    if ss[-i-1] == "1":
        print(i)
        break

Submission status: Accepted

Solution code:

"""

連続でない部分列問題…
中央値問題でよくあるのは、その数字以上の数がいくつ出てくるかで二分探索

部分問題：N個ある数列Aから1つ以上取って総和がK以上になる取り方はいくつあるか
→普通にdpするとできるがO(N^2*A)で無理(つーかほぼ答え)

中央値と平均値の関係は？
→今回はすべてのAが1/2の確率で選ばれるので、Aの総和/2 が全てのSの平均値となる
→だからなに・・・


=======解説をみた=======

Aのすべての合計をTとすると、前半はT/2以下で、後半はT/2以上(補集合の関係から)
求めるのは後半の一番小さい数字→T/2以上で登場する最小値

boolのDPになった！
bitsetを使えばオーダーレベルの改善になる
https://w.atwiki.jp/vivid_turtle/pages/40.html
ここに書かれている例に帰着する
"""
import sys

N = int(input())

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

asum = sum(A)

now = 1

for i in range(N):

    now = (now<<A[i]) | now

for i in range((asum+1)//2 , asum+1):

    if (1<<i) & now > 0:
        print (i)
        sys.exit()

Submission status: Accepted

Solution code:
N = int(input())
*A, = map(int, input().split())
S = sum(A)
subset_sum = 1
for a in A:
    subset_sum |= subset_sum << a
ans = (S + 1) // 2
subset_sum >>= ans
while subset_sum & 1 == 0:
    subset_sum >>= 1
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
#解説参照
n = int(input())
a = list(map(int, input().split( )))

dp = 1
for i in range(n):
    dp |= dp<<a[i]
ans = (sum(a)+1)//2
tmp = 1<<ans
for i in range(ans):
    if dp&tmp:
        print(ans)
        exit()
    ans+=1
    tmp <<=1
print(ans)

Submission status: Accepted

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+1)//2,s+1):
        if((dp>>i)&1):
            print(i)
            return
resolve()

Submission status: Accepted

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

N = int(readline())
A = list(map(int, readline().split()))
S = sum(A)
dp = 1
for a in A:
    dp |= dp<<a
dp ^= dp&((1<<(-(-S//2))) - 1)
print((-dp&dp).bit_length() - 1)

Submission status: Accepted

Solution code:
def main():
  _,a=open(0)
  *a,=map(int,a.split())
  d=1
  for i in a:d|=d<<i
  s=0--sum(a)//2
  d>>=s
  print((d&-d).bit_length()+s-1)
main()

Submission status: Accepted

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

Submission status: Accepted

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] | exist[a:]

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

Submission status: Accepted

Solution code:
import numpy as np

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

exist = np.zeros(sum(A)+1, dtype=bool)
exist[sum(A)] = 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: 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


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
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 = 1000000007



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

b = bin(dp)

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

Submission status: Accepted

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

# 集合Sと補集合を対応 → 空、全体を除くと完全に対応
# 和がsum(A)/2)以上での最小値

import numpy as np

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

S = sum(A)

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

answer = np.nonzero(dp[(S+1)//2:])[0][0] + (S+1)//2
print(answer)

Submission status: Accepted

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)[::-1][(S+1)//2:].index("1")+(S+1)//2)

Submission status: Accepted

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

DP = 1
for a in A:
    DP |= DP << a

Shalf = ceil(sum(A)/2)
DP >>= Shalf
for i in range(N * max(A)):
    if DP & 1:
        print(Shalf + i)
        break
    DP >>= 1

Submission status: Accepted

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

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

for i in range((sum(A)+1)//2, sum(A)+1):
	if (dp>>i)%2 == 1:
		print(i)
		break

Submission status: Accepted

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=S//2
for i in range(hS+1)[::-1]:
  if dp&(1<<i):
    ans=i
    break
print(S-i)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())


N = int(input())
aa = inpl()

b = 1
for a in aa:
	b |= b << a

S = sum(aa)
half = (S+1)//2
b >>= half

print((b&-b).bit_length()+half-1)

Submission status: Accepted

Solution code:
from math import ceil

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

# dpの右から(j+1)ビット目: 和がjである部分列が存在するならば1
dp = 1
for A in As:
    dp |= dp << A

# 和がjである部分列が存在する、(ΣA/2)以上で最小のjが答え
ans = ceil(sum(As) / 2)
dp >>= ans
while not (dp & 1):
    dp >>= 1
    ans += 1

print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import numpy
n = int(input())
a = [int(i) for i in input().split()]
dp = 1
for i in range(0, len(a)):
	dp = (dp | (dp << a[i]))
 
asum = 0
for i in range(0, len(a)):
	asum += a[i]
 
for i in range(int((asum + 1) / 2), asum + 1):
	if (dp >> i) & 1:
		print(i)
		break

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
dp = 1
for i in range(0, len(a)):
	dp = (dp | (dp << a[i]))

asum = 0
for i in range(0, len(a)):
	asum += a[i]

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# はじめてのぱいそん！
# Aの和 + not(A)の和 = ΣAと対称性から、答えはceil(ΣA / 2)以上の最小の部分和になる
# dp[i][j] = A_1～A_iで部分和jを作れるか？とすると, O(max(A_i) * N^2)で間に合わないように見える.
# しかしdp[i][j]の遷移は「シフト, コピー」のみなので、ビット演算によって高速化できる。
# pythonでは間に合わないよなあ…と一見思うかもしれないが、ビット演算の内部はおそらくc++なので多分間に合う。
# for文を使うと、一気に低速になるので(体感c++の50倍時間がかかる）、配列の和・値の検索あたりでは、ライブラリを使いたいところ。

n = int(input())
a = [int(i) for i in input().split()]
dp = 1
for i in range(0, len(a)):
	dp = (dp | (dp << a[i]))

asum = 0
for i in range(0, len(a)):
	asum += a[i]

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

Submission status: Accepted

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

#1からスタートしてlistの数字だけ左にシフトして論理和を取る。
#例えば1->4を左にシフトして論理和をとると1->10000->（元の1との論理和で）10001。
#さらに例を続ける。この次に5があるとき、10001->1000100000->（同様に）1000110001。
#つまり、スタートの1を除くと、5,6,10桁目にbitが立つ状態になる。
#求めたい部分集合の合計値が作れるかどうかはn+1桁目にbitが立っているかどうかを調べればよい。
#上記例（[4,5]の操作）では5,6,10桁目にbitが立っている＝4,5,9が作れているということ。
bits=1
for b in A:
  bits|=bits<<b

#解説どおり、答えはsum(list)/2以上で作れる部分和の最小値。
#上記bitsの定義を前提にbitsをsum(list)/2桁分だけ右にシフト。
#ココで最下位bitが立っていれば、答えはsum(list)/2。
#あとは1つずつ右にシフトして（答えも+1して）調べていくだけ。
ans=sum(A)
ans=(ans+1)//2
bits >>= ans
while True:
  if bits&1:
    break
  else:
    bits>>=1
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = LI()
    s = sum(a)
    t = 1
    m = 2**(s//2+1) - 1
    for c in a:
        t |= t << c
    t &= m

    return s - (t.bit_length() - 1)


print(main())

Submission status: Accepted

Solution code:
n, arr, dp = int(input()), list(map(int, input().split())), 1
for a in arr:
    dp |= dp << a
ofs = (sum(arr) + 1) // 2
dp >>= ofs
print((dp & -dp).bit_length() + ofs - 1)

Submission status: Accepted

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

N = int(readline())
A = list(map(int, readline().split()))
S = sum(A)
bits = 1
for a in A:
    bits |= bits << a
ans = (S + 1) // 2
bits >>= ans
while True:
    if bits & 1:
        print(ans)
        exit()
    bits >>= 1
    ans += 1

Submission status: Accepted

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+1)//2, asum+1):
    if (dp>>i)&1:
        print(i)
        break

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import math
input()
dp = 1
for x in map(int, input().split()):
    dp |= dp << x
h = math.ceil((len(format(dp, 'b')) - 1) / 2)
print(h + bin(dp >> h)[::-1].index('1'))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import math
input()
A = list(map(int, input().split()))

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

h = math.ceil(sum(A) / 2)
print(h + bin(dp >> h)[::-1].index('1'))

Submission status: Accepted

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
i = 0
while 1:
    if bitset & 1:
        print(i + halfA)
        exit()
    bitset >>= 1
    i += 1

Submission status: Accepted

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
i = 0
while 1:
    if bitset & 1:
        print(i + halfA)
        exit()
    bitset >>= 1
    i += 1

Submission status: Accepted

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
i = 0
while i < halfA:
  if bitset & 1:
    print(i+halfA)
    exit()
  bitset >>= 1
  i += 1
print(i+halfA)

Submission status: Accepted

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

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

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

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n = int(input())
M = 10**4
dp = [0]*(2*M)
dp[M] = 1
A = tuple(map(int, input().split()))
for i, a in enumerate(A):
  for j in range(2*M):
    if j-a >= 0 and dp[j-a]:
      dp[j] = 1
l = sum(divmod(sum(A), 2))
now = M+l
while True:
  if dp[now]:
    print(now-M)
    break
  now += 1

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int,input().split()))
s = sum(a)
a.sort()
b = 0
for i in a:
  b |= b<<i
  b |= 1<<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: Runtime Error

Solution code:
import numpy as np

N = int(input())
A = [int(a) for a in 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]

f[0] = 0
f = np.cumsum(f)
print(np.where(f >= 2**(N-1))[0][0])

Submission status: Runtime Error

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

S = sum(A)

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

for i in range(1, N+1) :
  for j in range(1, S+1) : 
    canMake[i][j] = canMake[i-1][j]
  canMake[i][A[i]] = True
  for j in range(1, S+1-A[i]) : 
    canMake[i][j+A[i]] = canMake[i-1][j] or canMake[i][j+A[i]]
"""
for i in range(1, N+1) :
  print(i , canMake[i])
"""
for j in range(int(S/2) if S % 2 == 0 else int(S/2) + 1, S+1) :
  if canMake[N][j] :
    print(j)
    break

Submission status: Runtime Error

Solution code:
#解説参照
n = int(input())
a = list(map(int, input().split( )))

dp = 1
for i in range(n):
    dp |= dp<<a[i]
ans = (sum(a)+1)//2
tmp = 1<<sn
for i in range(ans):
    if dp&tmp:
        print(ans)
        exit()
    ans+=1
    tmp <<=1 
print(ans)

Submission status: Runtime Error

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)
n=len(ans)
if(n%2==0):
  print((ans[(n//2)-1] + ans[n//2])/2.0)
else:
  return(ans[n//2])

Submission status: Runtime Error

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)
if(n%2==0):
  print((ans[(n//2)-1] + ans[n//2])/2.0)
else:
  print(ans[n//2])