Problem:


Score : 600 points

Problem Statement

AtCoDeer the deer has N cards with positive integers written on them. The number on the i-th card (1≤i≤N) is a_i.
Because he loves big numbers, he calls a subset of the cards good when the sum of the numbers written on the cards in the subset, is K or greater.

Then, for each card i, he judges whether it is unnecessary or not, as follows:

If, for any good subset of the cards containing card i, the set that can be obtained by eliminating card i from the subset is also good, card i is unnecessary.

Otherwise, card i is NOT unnecessary.

Find the number of the unnecessary cards. Here, he judges each card independently, and he does not throw away cards that turn out to be unnecessary.

Constraints

All input values are integers.

1≤N≤5000

1≤K≤5000

1≤a_i≤10^9 (1≤i≤N)

Partial Score

300 points will be awarded for passing the test set satisfying N,K≤400.

Input

The input is given from Standard Input in the following format:

N K
a_1 a_2 ... a_N

Output

Print the number of the unnecessary cards.

Sample Input 1

3 6
1 4 3

Sample Output 1

1

There are two good sets: {2,3} and {1,2,3}.

Card 1 is only contained in {1,2,3}, and this set without card 1, {2,3}, is also good. Thus, card 1 is unnecessary.

For card 2, a good set {2,3} without card 2, {3}, is not good. Thus, card 2 is NOT unnecessary.

Neither is card 3 for a similar reason, hence the answer is 1.

Sample Input 2

5 400
3 1 4 1 5

Sample Output 2

5

In this case, there is no good set. Therefore, all the cards are unnecessary.

Sample Input 3

6 20
10 4 3 10 25 2

Sample Output 3

3



Sample input:
3 6
1 4 3


Sample output:
1

Submission status: Accepted

Solution code:
n,k=map(int,raw_input().split())
a=map(int,raw_input().split())
a.sort()
used=[False]*n
idx=n-1
cnt=0
while True:
    if idx-cnt<0:
        break
    tmp=sum(a[idx-cnt:idx+1])
    if tmp<k:
        cnt+=1
        continue
    for i in xrange(idx-cnt,idx+1):
        used[i]=True
    tmp-=a[idx-cnt]
    for i in xrange(idx-cnt-1,-1,-1):
        if tmp+a[i]>=k:
            used[i]=True
        else:
            break
    idx-=1
    cnt=0
ans=0
for i in xrange(n):
    if not used[i]:
        ans+=1
print ans

Submission status: Accepted

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

small = 0
while small < n and a[small] < k:
    small += 1
n = small


cnt = 0
able = [False for i in range(k)]
able[0] = True
min_need = n
max_able = 0
i = n-1
while i >= 0:
    if max_able + a[i] >= k:
        min_need = i
        for j in range(min_need):
            if max_able + a[j] >= k:
                min_need = i
                break
    for j in range(min(max_able, k-a[i]-1), -1, -1):
        if able[j]:
            able[j+a[i]] = True
            max_able = max(j+a[i], max_able)
    i -= 1
print(min_need)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

sys.setrecursionlimit(4100000)

def biser(lst,func):
    n=len(lst)
    nh=n//2
    if n==1:
        if func(lst[0]):
            return lst[0]
        else:
            return -1
    if func(lst[nh]):
        return biser(lst[nh:],func)
    else:
        return biser(lst[:nh],func)

def findminsum(lst,K,N):
    inf=10**6
    dp=[[inf]*N for s in range(K+1)]
    for s in range(K+1):
        for j in range(N):
            if j==0 and s<=lst[j]:
                dp[s][j]=lst[0]
            elif s>lst[j] and j>0:
                dp[s][j]=min(dp[s-lst[j]][j-1]+lst[j], dp[s][j-1])
            elif s<=lst[j] and j>0:
                dp[s][j]=min(lst[j],dp[s][j-1])
    # print(lst)
    # print(dp[0][:])
    # print(dp[1][:])
    # print(dp[K][:])
    return dp[K][N-1]


    dp=[[inf]*N for s in range(K+1)]
    for s in range(K+1):
        for j in range(N):
            if j==0 and s<=lst[j]:
                dp[s][j]=lst[0]
            elif s>lst[j] and j>0:
                dp[s][j]=min(dp[s-lst[j]][j-1]+lst[j], dp[s][j-1])
            elif s<=lst[j] and j>0:
                dp[s][j]=min(lst[j],dp[s][j-1])
    # print(lst)
    # print(dp[0][:])
    # print(dp[1][:])
    # print(dp[K][:])
    return dp[K][N-1]

    
def main():
    N,K=map(int,sys.stdin.readline().strip().split())
    cards=list(map(int,sys.stdin.readline().strip().split()))
    # cards=list(filter(lambda x:x<K,cards))
    # N=len(cards)
    cards.sort()
    c1i=list(range(N))
    def unneccesity(h):
        if cards[h]>=K:
            return False
        else:
            c=cards[h]
            cards[h]=0
            ret=findminsum(cards,K-c,N)>=K
            cards[h]=c
            return ret
    #nn=0
    nn=biser(ci,unneccesity)
    # for i in range(N):
    #     if cards[i]<K:
    #         c=cards[i]
    #         cards[i]=0
    #         if findminsum(cards,K-c,N)>=K:
    #             nn+=1
    #         cards[i]=c
    #     else:
    #         break
    print(nn+1)


def main2():
    N,K=map(int,sys.stdin.readline().strip().split())
    cards=list(map(int,sys.stdin.readline().strip().split()))
    mask=lambda c: (1<<(K))-(1<<c)
    
    def isunnec(i):
        c=cards[i]
        if c>K:
            return False
        cards[i]=0
        ret=0
        for x in cards:
            if x!=0:
                ret=(((ret+1)<<x)|ret )&mask(0)
        cards[i]=c
        # print(i,bin(ret&mask(K-c)))
        if ret&mask(K-c)>0:
            return False
        else:
            return True
    nn=biser(list(range(N)),isunnec)
    print(nn+1)
    # for x in range(N):
    #     isunnec(x)
if __name__=='__main__':
    #main()
    main2()

Submission status: Runtime Error

Solution code:
n, k = map(int,input().split())
a = list(map(int,input().split()))
def trans(v):
  l = [0]*(k+1)
  for i in range(k+1):
    l[i] = (v&1)
    v >>= 1
  return l

a.sort()
lef = [1]*n
rig = [1]*n
mask = (1 << (k+1)) - 1
for i in range(n-1):
  lef[i+1] = lef[i] | (lef[i] << a[i]) & mask
  rig[-i-2] = rig[-i-1] | (rig[-i-1] << a[-i-1]) & mask
ok = -1
ng = n
while ng - ok > 1:
  mid = (ng + ok) // 2
  lc = lef[mid]
  rc = rig[mid]
  cov = ((1 << k) - 1) ^ ((1 << (k - a[mid])) - 1)
  for i in range(k+1):
    if lc & 1 and rc & cov:
      ng = mid
      break
    lc >>= 1
    cov >>= 1
  else:
    ok = mid
print(ok + 1)

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
b=list(map(int,input().split()))
b.sort()
a=[]
for i in range(N):
    if b[i]<K:
        a.append(b[i])
N=len(a)
ans=0
#print(bin((1<<K)>>1))
C=[1]
n=1
for i in range(N):
    n=n|n<<a[i]
    n%=(1<<K)
    C.append(n)
#print(C)
    #print(bin(n))
if N<=10:
    for i in range(N):
        n=C[i]
        for j in range(i+1,N):
            n=n|n<<a[j]
            n%=(1<<K)
        if n < (1<<K)>>a[i]:
            ans+=1
        else:
            break
    print(ans)
else:
    a+=[10**9]
    H=N
    L=0
    
    while abs(H-L)>4:
        Mid=(H+L)//2
        #print(H,Mid,L)
        n=1
        for i in range(N):
            if i==Mid:
                continue
            else:
                n=n|n<<a[j]
                n%=(1<<K)
        if n < (1<<K)>>a[i]:    
            H=Mid
        else:
            L=Mid
            
    for j in range(max(0,L-5),N):
        n=1
        for i in range(N):
            if i==j:
                continue
            else:
                n=n|n<<a[j]
                n%=(1<<K)
        if n < (1<<K)>>a[i]: 
            print(j)
            exit()

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
b=list(map(int,input().split()))
b.sort()
a=[]
for i in range(N):
    if b[i]<K:
        a.append(b[i])
N=len(a)
ans=0
#print(bin((1<<K)>>1))
C=[1]
n=1
for i in range(N):
    n=n|n<<a[i]
    n%=(1<<K)
    C.append(n)
#print(C)
    #print(bin(n))
P=N//2
n=C[P]
for x in range(P+1,N):
    n=n|n<<a[x]
    n%=(1<<K)
if n < (1<<K)>>a[P]:
    F=0
else:
    F=1
if F==0:
    for i in range(N):
        n=C[i]
        for j in range(i+1,N):
            n=n|n<<a[j]
            n%=(1<<K)
        if n < (1<<K)>>a[i]:
            ans+=1
        else:
            break
    print(ans)
else:
    ans=N//2
    P=N//2
    for i in range(P+1,N):
        n=C[i]
        for j in range(i+1,N):
            n=n|n<<a[j]
            n%=(1<<K)
        if n < (1<<K)>>a[i]:
            ans+=1
        else:
            break
    print(ans)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
A = [a for a in A if a <K]
N = len(A)
#dpm = [+1) for _ in range(N+1)]
dpm = [0]*(N+1)
dpm[0] = 1<<(K-1)
for i, a in enumerate(A):
    dpm[i+1] = dpm[i] | (dpm[i] >> a)

r = 0
dp2 = 1
for i, a in enumerate(A[::-1]):
    for j in range(a):
        if dp2 & tmp:
            break
        dpm[N-i-1] >>= 1
    else:
        r += 1
    dp2 |= dp2<<a
    dp2 &= (1<<K)-1
print(r)

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools

"""
・「必要」とは～～が存在
・x を含まない、[K-x,K) 内の総和が存在
・集合を指定すると、ある値段より上側
・全体としても単調性がある
"""

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

A.sort()
A = [x if x <= K else K + 1 for x in A]

mask = (1 << K) - 1

def test(x):
    # x番目は必要
    if A[x] > K:
        return True
    dp = 1
    for a in itertools.chain(A[:x], A[x+1:]):
        dp |= (dp << a)
        dp &= mask
    dp >>= (K - x)
    return (dp > 0)

left = -1 # 必要
right = N # 不要
while left + 1 < right:
    x = (left + right) // 2
    if test(x):
        right = x
    else:
        left = x

answer = left + 1
print(answer)

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools

"""
・「必要」とは～～が存在
・x を含まない、[K-x,K) 内の総和が存在
・集合を指定すると、ある値段より上側
・全体としても単調性がある
"""

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

A.sort()
A = [x if x <= K else K + 1 for x in A]

mask = (1 << K) - 1

def test(x):
    # x 番目を抜いて
    dp = 1
    for a in itertools.chain(A[:x], A[x+1:]):
        dp |= (dp << a)
        dp &= mask
    dp >>= (K - x)
    return (dp > 0)

left = -1 # 必要
right = N # 不要
while left + 1 < right:
    x = (left + right) // 2
    if test(x):
        right = x
    else:
        left = x

answer = right
print(answer)

Submission status: Runtime Error

Solution code:
_,k = map(int,input().split())
a = list(filter(lambda x:x<k,list(map(int,input().split()))))
n = len(a)
a.sort(reverse=True)
dpf = [[False]*k for _ in range(n)] 
dpb = [[False]*k for _ in range(n)] 
dpf[0][0] = True
dpb[-1][0] = True
for i in range(n-1):
  wf = a[i]
  wb = a[-(i+1)]
  for j in range(k):
    if dpf[i][j]:
      dpf[i+1][j] = True
      if j+wf < k:
        dpf[i+1][j+wf] = True
    if dpb[-(i+1)][j]:
      dpb[-(i+2)][j] = True
      if j+wb < k:
        dpb[-(i+2)][j+wb] = True
        
def check(v):
  w = a[v]
  im = [0]*(k+1)
  lf = dpf[v]
  lb = dpb[v]
  for i in range(k):
    if lb[i]:
      if k-i <= 0:
        continue
      im[max(k-w-i,0)] += 1
      im[k-i] -= 1
  if lf[0] and im[0]>0:
    return False
  for i in range(1,k):
    im[i] += im[i-1]
    if lf[i] and im[i]>0:
      return False
  return True
 
ng = -1
ok = n
while ok-ng > 1:
  mid = (ok+ng)//2
  if check(mid):
    ok = mid
  else:
    ng = mid
print(n-ok)

Submission status: Runtime Error

Solution code:
_,k = map(int,input().split())
a = list(filter(lambda x:x<k,list(map(int,input().split()))))
n = len(a)
a.sort(reverse=True)
dpf = [[False]*k for _ in range(n)] 
dpb = [[False]*k for _ in range(n)] 
dpf[0][0] = True
dpb[0][0] = True
for i in range(n-1):
  wf = a[i]
  wb = a[-(i+1)]
  for j in range(k):
    if dpf[i][j]:
      dpf[i+1][j] = True
      if j+wf < k:
        dpf[i+1][j+wf] = True
    if dpb[i][j]:
      dpb[i+1][j] = True
      if j+wb < k:
        dpb[i+1][j+wb] = True
        
def check(v):
  w = a[v]
  im = [0]*(k+1)
  lf = dpf[v]
  lb = dpb[n-v-1]
  for i in range(k):
    if lb[i]:
      if k-i <= 0:
        continue
      im[max(k-w-i,0)] += 1
      im[k-i] -= 1
  if lf[0] and im[0]>0:
    return False
  for i in range(1,k):
    im[i] += im[i-1]
    if lf[i] and im[i]>0:
      return False
  return True
 
ng = -1
ok = n
while ok-ng > 1:
  mid = (ok+ng)//2
  if check(mid):
    ok = mid
  else:
    ng = mid
print(n-ok)

Submission status: Runtime Error

Solution code:
def main():
  n,k = map(int,input().split())
  a = list(filter(lambda x:x<k,list(map(int,input().split()))))
  n = len(a)
  a.sort(reverse=True)
  ng = -1
  ok = n
  while ok-ng > 1:
  mid = (ok+ng)//2
  dp = [False]*(k+1)
  dp[0] = True
  f = 0
  for j in range(n):
    if j == mid:
      continue
    w = a[j]
    for i in range(k,w-1,-1):
      if dp[i-w]:
        dp[i] = True
        if k-a[mid] <= i < k:
          ng = mid
          f = 1
          break
    if f:
      break
  else:
    ok = mid
      
  print(n-ok)

if __name__ == "__main__":
  main()

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse=True)
hi = -1
lo = n
while lo-hi>1:
  mid = (lo+hi)//2
  if a[mid] >= k:
    hi = mid
  else:
    lo = mid
ng = hi
ok = n
while ok-ng > 1:
  mid = (ok+ng)//2
  dp = [False]*(k+1)
  dp[0] = True
  f = 1
  for j in range(n):
    if j == mid:
      f = 0
      continue
    w = a[j]
    new = dp.copy()
    for i in range(k-w+1):
      new[i+w] |= dp[i]
    dp = new
  if any(dp[k-a[mid]:k]):
    ng = mid
  else:
    ok = mid
print(n-ok)

Submission status: Runtime Error

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


def subset_sum(a):
    n = len(a)
    dp = [[0]*(k + 1) for i in range(n + 1)]
    dp[0][0] = 1
    for i in range(n):
        for j in range(k+1):
            if j - a[i] < 0:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = dp[i][j] + dp[i][j - a[i]]
    return dp[n]
  
ok = -1
ng = n
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    li = a[0:mid] + a[mid+1:]
    dp = subset_sum(li)
    if max(dp[k-a[mid]:k]) == 0:
        ok = mid
    else:
        ng = mid
        
print(ng)

Submission status: Runtime Error

Solution code:
import sys

n, k = map(int, input().split())
a = sorted(list(map(int, input().split())))
#print(a)
fr = 0
ba = n+1

def check(mi):
    x = a[mi-1]
    if x >= k:
        return True
    #print(mi)
    dp = [False] * (k+1)
    dp[0] = True
    for i in range(n):
        if i == mi-1:
            continue
        y = a[i]
        for j in range(k, -1, -1):
            if j >= y:
                dp[j] = dp[j] | dp[j-y]

    if sum(dp[k-x:k]):
        return True
    else:
        return False

if not check(1):
    print(0)
    sys.exit()

if check(n+1):
    print(n)
    sys.exit()

while ba-fr > 1:
    mi = (ba+fr+1) // 2
    if check(mi):
        ba = mi
    else:
        fr = mi

print(fr)

Submission status: Runtime Error

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]

[N,K]=i2()
a=i2()
a.sort()
def f(b,c):
       
        dp=[[0 for i in range(K)]for j in range(len(b))]
        dp[0][b[0]]=1
        d=0
        for i in range(1,len(b)):
          for j in range(K):
            dp[i][j]+=dp[i-1][j]
            if j-b[i]>=0:dp[i][j]+=dp[i-1][j-b[i]]
            if dp[i][j]==1 and d<j:d=j
        return  K-c <= d         
           
    
def ff():
    low = 0                        
    high = len(a) - 1
    while  high-low>1:            
        mid = (low + high) // 2
        if 0<mid<N-1:
           b=a[:mid]+a[mid+1:]
        elif mid==N-1:
           b=a[:mid]
        else:
           b=a[mid+1:]
        if f(b,a[mid]):          
            high = mid
        else:                      
            low = mid 
    return high

if f(a[1:],a[0]):
   print(0)
elif not f(a[:N-1],a[N-1]):
   print(N)
else:
   print(ff())

Submission status: Runtime Error

Solution code:
from bisect import bisect
N,K=map(int,input().split())
a=[int(i) for i in input().split()]
a.sort()
def dp(n):
  d=[False]*(K+1)
  d[0]=True
  for i in range(N):
    if i!=n:
      for w in range(K)[::-1]:
        if w+a[i]<=K and d[w]:
          d[w+a[i]]=True
  for i in range(K-a[n],K):
    if d[i]:
      return True
  return False

l,r=0,N-1
while r-l>1:
  m=(l+r)//2
  if dp(m):
    r=m
  else:
    l=m
if r==N-1 and not dp(N-1):
  print(N)
elif not dp(r):
  print(r+1)
elif not dp(l):
  print(l+1)
else:
  print(l)

Submission status: Runtime Error

Solution code:
# https://beta.atcoder.jp/contests/arc070/submissions/2980516
from bisect import bisect_left

N, K = map(int, input().split())
A = sorted(map(int, input().split()))
A = A[:bisect_left(A, K)]
dp = [False] * K
dp[0] = True
curr_max = 0
ans = len(A)
for i, a in reversed(enumerate(A)):
    # a[i - 1]を使ってa[i]が必要ならa[i - 1]も必要
    # a[i]より大きな値を使って判定すればいい
    if curr_max + a >= K:
        ans = i

    f = True
    for j in range(min(curr_max, K - a - 1), -1, -1):
        if dp[j]:
            dp[j + a] = True
            if f:
                curr_max = max(curr_max, j + a)
                f = False
print(ans)

Submission status: Runtime Error

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

def check(i):
	if i == 0:
		b = a[1:]
	elif i == N - 1:
		b = a[:N - 1]
	else:
		b = a[:i] + a[i+1:]
	#print(b)
	ok = False
	dp = [[False] * K for _ in range(N - 1)]
	dp[0][b[0]] = True
	if K - a[i] <= b[0] < K:
		ok = True
	for j in range(1, N - 1):
		for k in range(1, K):
			if dp[j - 1][k] == True:
				dp[j][k] = True
			elif k > b[j]:
				if dp[j - 1][k - b[j]] == True:
					dp[j][k] = True

			if dp[j][k] == True and K - a[i] <= k < K:
				ok = True

	if ok:
		#del b, dp
		return True
	else:
		#del b, dp
		return False


def bi_search(lower, upper):
	#print(lower, upper)
	mid = (lower + upper) // 2
	#print(mid)
	if check(mid) == False and check(mid + 1) == True:
		#print("hoge")
		return mid + 1
	elif mid == 0 and check(mid) == True:
		return 0
	elif mid == N - 2 and check(mid + 1) == False:
		return N
	elif check(mid) == True:
		return bi_search(lower, mid)
	else:
		return bi_search(mid, upper)


print(bi_search(0, N - 1))

Submission status: Runtime Error

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7


def solve(f):
    n, k = f.read_int_list()
    a = f.read_int_list()
    a.sort(reverse=True)

    # if n > 400: return 0

    def check(ai):
        aa = a[:]
        aa.remove(ai)
        # dp = [False] * k
        dp = [False] * (2*k)
        dp[0] = dp[k] = True

        for i in xrange(n-1):
            ofs0 = (i % 2) * k
            ofs1 = ((i+1)%2) * k
            for j in xrange(k):
                if dp[ofs0+j] and aa[i] + j < k:
                    dp[ofs1+aa[i]+j] = True

        if (n-1)%2 == 0:
            return any(dp[k-ai:k])
        else:
            return any(dp[2*k-ai:])

    au = list(set(a))
    au.sort(reverse=True)

    mi = -1
    ma = len(au)

    while ma - mi > 1:
        mid = (ma+mi)/2
        if check(au[mid]):
            mi = mid
        else:
            ma = mid

    a.sort()
    return bisect.bisect_right(a, au[ma])

    # need = 0
    # for i in xrange(n):
    #     if check(i): need += 1
    #
    # return n-need


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Submission status: Runtime Error

Solution code:
import bisect


def preliminary(k, aaa):
    dp = [False] * k
    dp[0] = True
    curr_max = 0
    fwd = {}
    pa = aaa[0]
    pdp, ppdp = dp[:], None
    for a in aaa:
        if pa != a:
            fwd[pa] = ppdp
        for i in range(min(curr_max, k - a - 1), -1, -1):
            if dp[i]:
                dp[i + a] = True
        curr_max += a
        pa = a
        ppdp = pdp
        pdp = dp[:]
    fwd[pa] = ppdp

    dp = [False] * k
    dp[0] = True
    curr_max = 0
    bwd = {}
    pa = 0
    pdp = []
    for a in reversed(aaa):
        if pa != a:
            bwd[a] = [i for i, v in enumerate(pdp) if v][1:]
        for i in range(min(curr_max, k - a - 1), -1, -1):
            if dp[i]:
                dp[i + a] = True
        curr_max += a
        pa = a
        pdp = dp[:]

    return fwd, bwd


def get_judge(k, aaa):
    fwd, bwd = preliminary(k, aaa)
    cache = [None] * k

    def judge(m):
        am = aaa[m]
        if cache[am] is None:
            dp = fwd[am]
            ndp = dp[:]
            for i in bwd[am]:
                for j in range(k - i - 1, -1, -1):
                    if dp[j]:
                        ndp[i + j] = True
            cache[am] = any(ndp[-am:])
        return cache[am]

    return judge


def solve(k, aaa):
    if sum(aaa) < k:
        return n

    aaa.sort()
    aaa = aaa[:bisect.bisect_left(aaa, k)]

    judge = get_judge(k, aaa)

    l = 0
    r = len(aaa) - 1
    m = (l + r) // 2
    while l <= r:
        if judge(m):
            r = m - 1
        else:
            l = m + 1
        m = (l + r) // 2

    return l


n, k = map(int, input().split())
aaa = list(map(int, input().split()))
print(solve(k, aaa))

Submission status: Runtime Error

Solution code:
import bisect


def preliminary(k, aaa):
    dp = [False] * k
    dp[0] = True
    curr_max = 0
    fwd = []
    for a in aaa:
        for i in range(min(curr_max, k - a - 1), -1, -1):
            if dp[i]:
                dp[i + a] = True
        fwd.append(dp.copy())
        curr_max += a

    dp = [False] * k
    dp[0] = True
    curr_max = 0
    bwd = []
    for a in reversed(aaa):
        for i in range(min(curr_max, k - a - 1), -1, -1):
            if dp[i]:
                dp[i + a] = True
        bwd.append([i for i, v in enumerate(dp) if v][1:])
        curr_max += a
    bwd.reverse()

    dummy = [False] * k
    dummy[0] = True
    fwd.append(dummy)
    bwd.append([])

    return fwd, bwd


def get_judge(k, aaa):
    fwd, bwd = preliminary(k, aaa)
    cache = [None] * k

    def judge(m):
        am = aaa[m]
        if cache[am] is None:
            dp = fwd[m - 1]
            for i in bwd[m + 1]:
                for j in range(k - i - 1, -1, -1):
                    if dp[j]:
                        dp[i + j] = True
            cache[am] = any(dp[-am:])
        return cache[am]

    return judge


def solve(k, aaa):
    if sum(aaa) < k:
        return n

    aaa.sort()
    aaa = aaa[:bisect.bisect_left(aaa, k)]
    judge = get_judge(k, aaa)

    l = 0
    r = len(aaa) - 1
    m = (l + r) // 2
    while l <= r:
        if judge(m):
            r = m - 1
        else:
            l = m + 1
        m = (l + r) // 2

    return l


n, k = map(int, input().split())
aaa = list(map(int, input().split()))
print(solve(k, aaa))

Submission status: Runtime Error

Solution code:
import bisect


def preliminary(k, aaa):
    dp = [False] * k
    dp[0] = True
    curr_max = 0
    fwd = []
    for a in aaa:
        for i in range(min(curr_max, k - a - 1), -1, -1):
            if dp[i]:
                dp[i + a] = True
        fwd.append(dp.copy())
        curr_max += a

    dp = [False] * k
    dp[0] = True
    curr_max = 0
    bwd = []
    for a in reversed(aaa):
        for i in range(min(curr_max, k - a - 1), -1, -1):
            if dp[i]:
                dp[i + a] = True
        bwd.append([i for i, v in enumerate(dp) if v][1:])
        curr_max += a
    bwd.reverse()

    dummy = [False] * k
    dummy[0] = True
    fwd.append(dummy)
    bwd.append([])

    return fwd, bwd


def get_judge(k, aaa):
    fwd, bwd = preliminary(k, aaa)
    cache = [None] * k

    def judge(m):
        am = aaa[m]
        if cache[am] is None:
            dp = fwd[m - 1]
            for i in bwd[m + 1]:
                for j in range(k - i - 1, -1, -1):
                    if dp[j]:
                        dp[i + j] = True
            cache[am] = any(dp[-am:])
        return cache[am]

    return judge


def solve(k, aaa):
    aaa.sort()
    uk = bisect.bisect_left(aaa, k)
    aaa = aaa[:uk]

    judge = get_judge(k, aaa)

    l = 0
    r = len(aaa) - 1
    m = (l + r) // 2
    while l <= r:
        if judge(m):
            r = m - 1
        else:
            l = m + 1
        m = (l + r) // 2

    return l


n, k = map(int, input().split())
aaa = list(map(int, input().split()))

# n = 5000
# k = 5000
# aaa = list(range(1, n + 1))

print(solve(k, aaa))

Submission status: Runtime Error

Solution code:
import bisect

import numpy as np
from scipy.ndimage.interpolation import shift


def preliminary(k, aaa):
    dp = np.zeros(k, np.uint8)
    dp[0] = 1
    fwd = []
    for a in aaa:
        dp |= shift(dp, a)
        fwd.append(dp.copy())

    dp = np.zeros(k, np.uint8)
    dp[0] = 1
    bwd = []
    for a in reversed(aaa):
        dp |= shift(dp, a)
        bwd.append(np.where(dp)[0])
    bwd.reverse()

    fwd.append(np.zeros(k, np.uint8))
    bwd.append([0])

    return fwd, bwd


def solve(k, aaa):
    aaa.sort()
    uk = bisect.bisect_left(aaa, k)
    aaa = aaa[:uk]

    fwd, bwd = preliminary(k, aaa)

    l = 0
    r = len(aaa) - 1
    m = (l + r) // 2
    while l <= r:
        dp = fwd[m - 1]
        for i in bwd[m + 1][1:]:
            dp |= shift(dp, i)
        if dp[-aaa[m]:].any():
            r = m - 1
        else:
            l = m + 1
        m = (l + r) // 2

    return l


n, k = map(int, input().split())
aaa = list(map(int, input().split()))
print(solve(k, aaa))

Submission status: Runtime Error

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

A = sorted([a for a in A if a < K])
N = len(A)
S = sum(A)

# あああああああああああああああああああ＼(＾o＾)／
if S - A[0] < K:
    print(0)
    exit()

l, r = -1, N
while r - l > 1:
    m = (l + r) // 2
    B = A[:m] + A[m + 1:]

    if S - A[m] < K - A[m]:
        l = m
        continue

    dp = [False] * (K + 1)
    dp[0] = True
    flg= False

    for i in range(N - 1):
        for j in range(K + 1)[::-1]:
            if B[i] > j:
                continue
            else:
                dp[j] = dp[j - B[i]]

            if dp[j] and K-A[m] <= j < K:
                r = m
                flg = True
                break
        if flg:
            flg = False
            break
    else:
        l = m

print(r)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))
from copy import deepcopy
from operator import add
from itertools import accumulate

N, K = inpl()
A = sorted(inpl())
S = list(accumulate(A, add))
A = A[::-1]
DP = [False for _ in range(K)]
DP[0] = 1
OK = [False for _ in range(N)]

for i, a in enumerate(A):
    DP0 = deepcopy(DP)
    if a >= K:
        OK[i] = True
        continue
    for j, d in enumerate(DP0[-S[::-1][i]:], max(0, K-S[::-1][i])):
        if d:
            if j + a >= K:
                OK[i] = True
                break
            else:
                DP[j+a] = True

if sum(OK) == 0:
    print(N)
else:
    print(OK[::-1].index(True))

Submission status: Runtime Error

Solution code:
# coding: utf-8

n, k = map(int, raw_input().split())
a = list(map(int, raw_input().split()))
a.sort()

left = 0
right = n - 1

while left != right:
    mid = (left + right + 1) / 2
    dp = [[0 for j in range(k + 1)] for i in range(n + 1)]
    dp[0][0] = 1
    for i in range(n):
        for j in range(k + 1):
            keep = dp[i][j]
            if j - a[i] >= 0:
                if i != mid:
                    if dp[i][j - a[i]] == 1:
                        keep = 1
            dp[i + 1][j] = keep

    flag = 0
    for i in range(k - a[mid], k):
        if dp[n][i] == 1:
            flag = 1
            break
    if flag == 1:
        right = mid - 1
    else:
        left = mid
    
print(left + 1)

Submission status: Runtime Error

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

nums = list(map(int, input().split()))
nums.sort()

if sum(nums) < K or nums[0] >= K:
    print(str(N))
    quit()

dp = [[False for i in range(0, N)] for j in range(0, K)]

import numpy as np
res = N
for i in range(0, N):
    dp_arr = np.array(dp[:])
    dp_arr[0, :] = True
    for j in range(1, K):
        idx = 1
        for k in range(0, N):
            if k == i or j - nums[k] < 0:
                continue
            if  dp_arr[j - nums[k]][idx - 1]:
                dp_arr[j][idx] = True
            idx += 1
    for j in range(K - nums[i], K):
        if sum(dp_arr[j]) > 0:
            res -= 1
            break
print(str(res))

Submission status: Runtime Error

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

nums = list(map(int, input().split()))
nums.sort()

if sum(nums) < K or nums[0] >= K:
    print(str(N))
    quit()

dp = [[0 for i in range(0, N)] for j in range(0, K)]
idx = 0
for i in range(1, K):
    for j in range(0, N):
        s = sum(nums[:j+1])
        if s >= i:
            dp[i][j] = s
res = N
for i in range(1, N):
    for j in range(K - nums[i], K):
        find = False
        for k in range(0, N):
            if k == i:
                continue
            if k < i:
                if dp[j][k] < K and dp[j][k] + nums[i] >= K:
                    res -= 1
                    find = True
                    break
            else:
                if dp[j][k] >= K and dp[j][k] - nums[i] < K:
                    res -= 1
                    find = True
                    break
        if find:
            break
print(str(res))

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
A.sort()
S = sum(A)

if S < K:
	print(N)
	exit()
elif A[0] >= K:
	print(0)
	exit()

def is_necessary(n):
	if A[n] >= K:
		return True
	dp = [False]*K
	dp[0] = True
	dp2 = [False]*K
	dp2[0] = True
	can_make = []
	can_make2 = [0]
	for i in range(N):
		if i == n:
			continue
		elif A[i] >= K:
			break
		a = A[i]
		for j in can_make2:
			if dp2[j] and j+a < K and not dp2[j+a]:
				if j + a >= K - A[n]:
					return True
				dp[j+a] = True
				can_make.append(j+a)
		can_make2.extend(can_make)
		can_make = []
		dp2 = dp[:]
	return False

l = -1
r = N
while r - l > 1:
	m = (r+l)//2
	while A[m-1] == A[m]:
		m -= 1
	if is_necessary(m):
		r = m
	else:
		l = m

print(l+1)