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: Runtime Error

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

def check(x):
    if A[x] >= K:
        return True
    dp = [False] * (K + 1)
    dp[0] = True
    for j, a in enumerate(A):
        if j == x:
            continue
        for i in range(K, 0, -1):
            if i >= a:
                dp[i] |= dp[i - a]
    for i in range(K - x, K):
        if dp[i]:
            return True
    return False
left = -1
right = N
while right - left > 1:
    mid = (left + right) // 2
    if check(mid):
        right = mid
    else:
        left = mid
print(right)

Submission status: Runtime Error

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

dp = [0] * (K + 1)
dp[0] = 1
for a in A:
    for i in range(K, 0, -1):
        if i >= a:
            dp[i] += dp[i - a]
ans = 0
for a in A:
    x = K - a
    necessary = False
    for i in range(x, K):
        if i >= a:
            if dp[i] - dp[i - a] >= 1:
                necessary = True
        else:
            if dp[i] >= 1:
                necessary = True
    if necessary:
        ans += 1
print(N - ans)

Submission status: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

def main():
    N, K = map(int, input().split())
    A = [0] + list(map(int, input().split()))
    """
    （aが不要なカード）＝（A-{a}からK-a以上の最小の部分和を取った時、それがK以上）
    まで言い換えてドボン。。。
    部分和の全列挙しなくても和がKまでで打ち切っていいんだから、ここでdpの発想が出なかったのは切腹。
    まずは部分点解法を実装してみる。
    """
    ans = 0
    for k in range(1, N + 1):
        # dp[i][j] = (i個使って(ただしA[k]を除く)部分和jが作れるか)
        dp = [1] + [0] * K
        for i in range(1, N + 1):
            if i == k: continue
            dp2 = [0] * (K + 1)
            for j in range(K + 1):
                if dp[j] == 1:
                    dp2[j] = 1
                    dp2[min(K, j + A[i])] = 1
            dp = dp2

        
        no_need = True
        for j in range(K - A[k], K):
            if dp[j] != 0:
                no_need = False
                break
        if no_need: ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
from bisect import bisect_left
def input(): return sys.stdin.readline().strip()

def main():
    N, K = map(int, input().split())
    A = [0] + list(map(int, input().split()))
    """
    （aが不要なカード）＝（A-{a}からK-a以上の最小の部分和を取った時、それがK以上）
    まで言い換えてドボン。。。
    部分和の全列挙しなくても和がKまでで打ち切っていいんだから、ここでdpの発想が出なかったのは切腹。
    まずは部分点解法を実装してみる。
    """
    ans = 0
    for k in range(1, N + 1):
        # dp[i][j] = (i個使って(ただしA[k]を除く)部分和jが作れるか)
        dp = [1] + [0] * K
        for i in range(1, N + 1):
            if i == k: continue
            dp2 = [0] * (K + 1)
            dp2[min(K, A[i])] = 1
            for j in range(K + 1):
                if dp[j] == 1:
                    dp2[j] = 1
                    dp2[min(K, j + A[i])] = 1
            dp = dp2

        
        no_need = True
        for j in range(K - A[k], K):
            if dp[j] != 0:
                no_need = False
                break
        if no_need: ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import collections
N, K = map(int, input().split())
a = [int(x) for x in input().split() if int(x) < K]
a.sort()

def renew_dp(dp, List, K): #Listの部分和がiならばdp[i]=True
    for x in List:
        dp_ = dp.copy()
        for i in range(1,K):
            if i-x < 0:
                continue
            if dp[i-x]:
                dp_[i] = True
        dp = dp_
    return dp

def judge(a, dp, K): #aが必要(True)か不必要(False)か
    for i in range(K-a,K):
        if dp[i]:
            return True 
    return False

def binary_tree(List, base_List, K): #2分木探索
    center = len(List)//2 #2分する支点
    dp = {}
    dp = collections.defaultdict(lambda:False)
    dp[0] = True
    List_without_center = base_List.copy()
    List_without_center.remove(List[center])
    dp = renew_dp(dp, List_without_center, K) #centerのdp更新
    if len(List) == 1: #2分木のゴール
        if judge(List[center], dp, K):
            result = center
        else:
            result = center+1
    else: #再帰的に探索
        if judge(List[center], dp, K):
            result = binary_tree(List[:center], base_List, K)
        else:
            result =binary_tree(List[center:], base_List, K) + center
    return result

ans = binary_tree(a, a, K) #ans以下のjについて、a[j]は不必要
print(ans)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
a = [int(x) for x in input().split() if int(x)<K]

def bfs(List, remain, K): #幅優先探索
    over_K = K
    for x in List:
        if x == remain: #和がKとなる部分集合を構成できる場合
            return 0
    for x in List:
        if over_K == 0: #over_K=0なら即リターン
            return over_K
        next_remain = remain -x
        if next_remain < 0:
            over_K = min(over_K, -next_remain)
        else:
            copy_List = List.copy()
            copy_List.remove(x)
            over_K = min(over_K, bfs(copy_List, next_remain, K)) #1段だけ深く探索
    return over_K

no_need = 0
for x in a:
    copy_a = a.copy()
    copy_a.remove(x)
    result = bfs(copy_a, K-x, K)
    if result == 0:
        continue
    if result - x >= 0:
        no_need += 1
print(no_need)

Submission status: Runtime Error

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

ok = n
ng = -1
while ok - ng > 1:
    mid = (ok + ng) // 2

    a[mid] ^= a[n - 1]
    a[n - 1] ^= a[mid]
    a[mid] ^= a[n - 1]

    dp = [[False for j in range(k)] for i in range(n)]
    dp[0][0] = True

    for i in range(n - 1):
        for j in range(k):
            dp[i + 1][j] = dp[i + 1][j] or dp[i][j]
            if j + a[i] < k:
                dp[i + 1][j + a[i]] = dp[i + 1][j + a[i]] or dp[i][j]
    
    flg = False
    for j in range(k - a[n - 1], k):
        if dp[n - 1][j]:
            flg = True
            break
    
    if flg:
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
A=sorted(filter(lambda x:x<K,list(map(int,input().split()))))
N=len(A)
def judge(x):
  DP=1
  Z=(1<<K)-1
  for i in range(N):
    if i!=x:
      DP=((DP|(DP<<A[i]))&Z)
  r=0
  for i in range(K-A[x],K):
    r|=(DP&(1<<i))
  return r

if judge(0):
  print(0)
  exit()
L,R,M=1,N,0
while L!=R:
  M=(L+R)//2
  if judge(M)==0:
    L=max(L+1,M)
  else:
    R=M
print(L)

Submission status: Runtime Error

Solution code:
import sys

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 mkns(a,s,m):
    if a==0:
        return s
    else:
        return (((s+1)<<a)|s) & m

def main():
    N,K=map(int,sys.stdin.readline().strip().split())
    a=list(map(int,sys.stdin.readline().strip().split()))
    a.sort()
    ss=[0]*(N+1)
    pm=(1<<K)-1
    mask=lambda c:(1<<K)-(1<<c)
    nn=0
    def isunnec(i):
        if a[i]>=K:
            return False
        for j in range(i+1,N):
            if a[j]>=K:
                break
            ss[i]=(((ss[i]+1)<<a[j])|ss[i]) & pm
        # print(bin(ss[i]), bin(mask(K-c)),ss[i]&mask(K-c))
        if ss[i]&mask(K-a[i])==0:
            return True
        return False
    
    # for i in range(N):
    #      if a[i]>=K:
    #          break
    #      ss[i+1]=(((ss[i]+1)<<a[i])|ss[i]) & pm
    #      if isunnec(i):
    #          nn+=1
        # for j in range(i+1,N):
        #     if a[j]>=K:
        #         break
        #     ss[i]=mkns(a[j],ss[i],pm)
        # # print(bin(ss[i]), bin(mask(K-c)),ss[i]&mask(K-c))
        # if ss[i]&mask(K-a[i])==0:
        #     nn+=1
    m=len(list(filter(lambda x:x<K, a)))
    nn=biser(list(range(m)),isunnec)+1
    # print(list(map(bin,ss)))
    print(nn)

if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys

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]


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()
    ci=list(range(N))
    def func(h):
        c=cards[h]
        cards[h]=0
        ret=findminsum(cards,K-c,N)>=K
        cards[h]=c
        return ret
    #nn=0
    nn=biser(ci,func)
    # 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)

if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10000)

def biser(lst,func):
    n=len(lst)
    nh=n//2
    if n==1:
        return lst[0]
    if func(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]


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()
    ci=list(range(N))
    def func(h):
        c=cards[h]
        cards[h]=0
        ret=findminsum(cards,K-c,N)>=K
        cards[h]=c
        return ret
    #nn=0
    nn=biser(ci,func)
    # 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)

if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys

def biser(lst,func):
    n=len(lst)
    nh=n//2
    if n==1:
        return lst[0]
    if func(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]


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()
    ci=list(range(N))
    def func(h):
        c=cards[h]
        cards[h]=0
        ret=findminsum(cards,K-c,N)>=K
        cards[h]=c
        return ret
    #nn=0
    nn=biser(ci,func)
    # 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)

if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys

def findminsum(lst,K,N,dp):
    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():
    inf=10**6
    dp=[[inf]*N for s in range(K+1)]
    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))
    cards.sort()
    N=len(cards)
    nn=0
    for i in range(N):
        if cards[i]<K:
            c=cards[i]
            cards[i]=0
            if findminsum(cards,K-c,N,dp)>=K:
                nn+=1
            cards[i]=c
        else:
            break
    print(nn)

if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys

def findminsum(lst,K,N):
    inf=10**10
    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]:
                ds[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.sort()
    nn=0
    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)

if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys

def findminsum(lst,K,N):
    inf=10**10
    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]
                ds[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.sort()
    nn=0
    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)

if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
from numba import njit

n, k = map(int, input().split())
a = tuple(map(int, input().split()))

dp = np.zeros((n + 1, k), bool)
dp[0][0] = True
for i, e in enumerate(a, 1):
    dp[i] = dp[i-1]
    dp[i, e:] |= dp[i-1, :-e]

dp2 = np.zeros((n + 1, k), bool)
dp2[0][0] = True
for i, e in enumerate(a[::-1], 1):
    dp2[i] = dp2[i-1]
    dp2[i, e:] |= dp2[i-1, :-e]


@njit
def f(a, dp, dp2):
    ret = 0
    for i, e in enumerate(a, 1):
        li = [j for j in range(k) if dp[i-1][j]]
        li2 = [j for j in range(k) if dp2[n-i][j]]

        j = len(li2) - 1
        mx = 0
        for e2 in li:
            while j > 0 and e2 + li2[j] >= k:
                j -= 1

            if e2 + li2[j] < k:
                mx = max(mx, e2 + li2[j])

        if mx + e < k:
            ret += 1

    return ret


ans = f(a, dp, dp2)
print(ans)

Submission status: Runtime Error

Solution code:
from numba import njit


@njit
def solve(n, k, a):
    dp = [[0] * k for _ in range(n + 1)]
    dp[0][0] = 1
    for i, e in enumerate(a, 1):
        for j in range(k):
            dp[i][j] = dp[i-1][j]

        for j in range(k - e):
            if dp[i-1][j]:
                dp[i][j+e] = 1

    dp2 = [[0] * k for _ in range(n + 1)]
    dp2[0][0] = 1
    for i, e in enumerate(a[::-1], 1):
        for j in range(k):
            dp2[i][j] = dp2[i-1][j]

        for j in range(k - e):
            if dp2[i-1][j]:
                dp2[i][j+e] = 1

    ans = 0
    for i, e in enumerate(a, 1):
        li = [j for j in range(k) if dp[i-1][j]]
        li2 = [j for j in range(k) if dp2[n-i][j]]

        j = len(li2) - 1
        mx = 0
        for e2 in li:
            while j > 0 and e2 + li2[j] >= k:
                j -= 1

            if e2 + li2[j] < k:
                mx = max(mx, e2 + li2[j])

        if mx + e < k:
            ans += 1

    print(ans)


if __name__ == "__main__":
    n, k = map(int, input().split())
    a = tuple(map(int, input().split()))
    solve(n, k, a)

Submission status: Runtime Error

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

def judge(x):
    b = [a[i] for i in range(N) if i!=x]
    dp = [[0]*K for _ in range(N)]
    dp[0][0] = 1
    
    for i in range(N-1):
        for j in range(K):
            dp[i+1][j] += dp[i][j]
            
            if j+b[i]<K:
                dp[i+1][j+b[i]] += dp[i][j]
    
    for i in range(K-x, K):
        if dp[N-1][i]>0:
            return False
    
    return True
    
def binary_search():
    l, r = 0, N-1
    
    while l<=r:
        m = (l+r)//2
        
        if judge(m):
            l = m+1
        else:
            r = m-1
    
    return r

N, K = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
print(binary_search()+1)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int N, K;
    cin >> N >> K;
    vector<int> a(N);
    REP(i, N) cin >> a[i];
    vector<vector<int>> dp_left(N+1, vector<int>(K));
    vector<vector<int>> dp_right(N+1, vector<int>(K));
    dp_left[0][0] = dp_right[N][0] = 1;
    REP(i, N) {
        REP(j, K) {
            dp_left[i+1][j] = dp_left[i][j];
            if (j >= a[i]) dp_left[i+1][j] |= dp_left[i][j-a[i]];
            dp_right[N-i-1][j] = dp_right[N-i][j];
            if (j >= a[N-i-1]) dp_right[N-i-1][j] |= dp_right[N-i][j-a[N-i-1]];
        }
    }
    int ans = 0;
    REP(i, N) {
        vector<int> cum(K+1);
        REP(j, K) cum[j+1] = cum[j] + dp_right[i+1][j];
        bool ok = true;
        REP(j, K) {
            if (!dp_left[i][j]) continue;
            if (cum[K-j] - cum[max(0, K-a[i]-j)] > 0) {
                ok = false;
                break;
            }
        }
        if (ok) ans++;
    }
    cout << ans << endl;
}

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
if a[0] >= k:
    print(0)
    exit()
if sum(a) < k:
    print(n)
    exit()
def search(m):
    if m >= k:
        return True
    x = k-a[m]
    dp = [[float("INF")]*(x+1) for i in range(n)]
    dp[0][0] = 0
    now = 0
    for i in range(n):
        if i == m:
            continue
        for j in range(x+1):
            if dp[now][j] !=float("INF"):
                dp[now+1][j] = min(dp[now][j],dp[now+1][j])
                if a[i]+j < x:
                    dp[now+1][a[i]+j] = a[i]+j
                else:    
                    dp[now+1][-1] = min(a[i]+j,dp[now+1][-1])
        now += 1
    if dp[-1][-1] == float("INF"):
        return True
    elif dp[-1][-1] >= k:
        return False
    else:
        return True
le = 0
ri = n


while ri > le+1:
    m = (ri+le)//2

    if search(m):
        ri = m
    else:
        le = m

print(le+1)

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
if a[0] >= k:
    print(0)
    exit()
def search(m):
    if m >= k:
        return True
    x = k-a[m]
    dp = [[float("INF")]*(x+1) for i in range(n)]
    dp[0][0] = 0
    now = 0
    for i in range(n):
        if i == m:
            continue
        for j in range(x+1):
            if dp[now][j] !=float("INF"):
                dp[now+1][j] = min(dp[now][j],dp[now+1][j])
                if a[i]+j < x:
                    dp[now+1][a[i]+j] == a[i]+j
                else:    
                    dp[now+1][-1] = min(a[i]+j,dp[now+1][-1])
        now += 1
    if dp[-1][-1] >= k:
        return False
    else:
        return True
le = 0
ri = n


while ri > le+1:
    m = (ri+le)//2

    if search(m):
        ri = m
    else:
        le = m

print(le+1)

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
if a[0] >= k:
    print(0)
    exit()
def search(m):
    if m >= k:
        return True
    x = k-a[m]
    dp = [[float("INF")]*(x+1) for i in range(n)]
    dp[0][0] = 0
    now = 0
    for i in range(n):
        if i == m:
            continue
        for j in range(x+1):
            if dp[now][j] !=float("INF"):
                dp[now+1][j] = min(dp[now][j],dp[now+1][j])
                if a[i]+j < x:
                    dp[now+1][a[i]+j] == a[i]+j
                else:    
                    dp[now+1][-1] = min(a[i]+j,dp[now+1][-1])
        now += 1
    if dp[-1][-1] >= k:
        return False
    else:
        return True
le = -1
ri = n


while ri > le+1:
    m = (ri+le)//2

    if search(m):
        ri = m
    else:
        le = m

print(le+1)

Submission status: Runtime Error

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

def search(m):
    if m >= k:
        return True
    x = k-a[m]
    dp = [[float("INF")]*(x+1) for i in range(n)]
    dp[0][0] = 0
    now = 0
    for i in range(n):
        if i == m:
            continue
        for j in range(x+1):
            if dp[now][j] !=float("INF"):
                dp[now+1][j] = min(dp[now][j],dp[now+1][j])
                if a[i]+j < x:
                    dp[now+1][a[i]+j] == a[i]+j
                else:    
                    dp[now+1][-1] = min(a[i]+j,dp[now+1][-1])
        now += 1
    if dp[-1][-1] >= k:
        return False
    else:
        return True
le = -1
ri = n


while ri > le+1:
    m = (ri+le)//2

    if search(m):
        ri = m
    else:
        le = m

print(le+1)

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
if sum(a) < k:
    print(n)
    exit()

def search(m):
    if m >= k:
        return True
    x = k-a[m]
    dp = [[float("INF")]*(x+1) for i in range(n)]
    dp[0][0] = 0
    now = 0
    for i in range(n):
        if i == m:
            continue
        for j in range(x+1):
            if dp[now][j] !=float("INF"):
                dp[now+1][j] = min(dp[now][j],dp[now+1][j])
                if a[i]+j < x:
                    dp[now+1][a[i]+j] == a[i]+j
                else:    
                    dp[now+1][-1] = min(a[i]+j,dp[now+1][-1])
        now += 1
    if dp[-1][-1] >= k:
        return False
    else:
        return True
le = -1
ri = n+1


while ri > le+1:
    m = (ri+le)//2

    if search(m):
        ri = m
    else:
        le = m

print(le+1)

Submission status: Runtime Error

Solution code:


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

if sum(al) < k:
    print(n)
    exit()
res = 0
for h in range(n):
    dp=[[0 for i in range(k)] for j in range(n)]
    dp[0][0]=1
    judge =0
    newal = sorted(al)
    xk = k-newal[h]
    newal.pop(h)
    for i in range(n-1):
        for j in range(k):
            if newal[i]<=j: #i+1番目の数字a[i]を足せるかも
                dp[i+1][j]=dp[i][j-newal[i]] or dp[i][j]
            else: #入る可能性はない
                dp[i+1][j]=dp[i][j]
    for l in range(xk,k):
        if dp[n-1][l] ==1:
            print(n-h-1)
            exit()

Submission status: Runtime Error

Solution code:

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

if sum(al) < k:
    print(n)
    exit()
dp=[[0 for i in range(k)] for j in range(n)]
dp[0][0]=1

res = 0
for h in range(n):
    judge =0
    newal = sorted(al)
    xk = k-newal[h]
    newal.pop(h)
    for i in range(n-1):
        for j in range(k):
            if newal[i]<=j: #i+1番目の数字a[i]を足せるかも
                dp[i+1][j]=dp[i][j-newal[i]] or dp[i][j]
            else: #入る可能性はない
                dp[i+1][j]=dp[i][j]
    for l in range(xk,k):
        if dp[n-1][l] ==1:
            print(n-h-1)
            exit()

Submission status: Runtime Error

Solution code:

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

if sum(al) < k:
    print(n)
    exit()
dp=[[0 for i in range(k)] for j in range(n)]
dp[0][0]=1

res = 0
for h in range(n):
    judge =0
    newal = sorted(al)
    xk = k-newal[h]
    newal.pop(h)
    for i in range(n-1):
        for j in range(k):
            if newal[i]<=j: #i+1番目の数字a[i]を足せるかも
                dp[i+1][j]=dp[i][j-newal[i]] or dp[i][j]
            else: #入る可能性はない
                dp[i+1][j]=dp[i][j]
    for l in range(xk,k):
        if dp[n-1][l] ==1:
            print(n-h)
            exit()

Submission status: Runtime Error

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

if sum(al) < k:
    print(n)
    exit()

newal = sorted(al)
for m in range(n):
    if newal[m] >k:
        cut = m
        al = newal[:cut]
        break
n = len(al)

dp=[[0 for i in range(k*2)] for j in range(n)]
dp[0][0]=1

res = 0
for h in range(n):
    judge =0
    newal = sorted(al)
    xk = k-newal[h]
    newal.pop(h)
    for i in range(n-1):
        for j in range(k*2):
            if newal[i]<=j: #i+1番目の数字a[i]を足せるかも
                dp[i+1][j]=dp[i][j-newal[i]] or dp[i][j]
            else: #入る可能性はない
                dp[i+1][j]=dp[i][j]
    for l in range(xk,k*2):
        if judge ==1:
            break
        if dp[n-1][l] ==1:
            mins = l
            if l >=k:
                res += 1
                judge = 1
            else:
                judge = 1
print(res)

Submission status: Runtime Error

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

if sum(al) < k:
    print(n)
    exit()

newal = sorted(al)
for m in range(n):
    if newal[m] >k:
        cut = m
        break
al = newal[:m]
n = len(al)

dp=[[0 for i in range(k*2)] for j in range(n)]
dp[0][0]=1

res = 0
for h in range(n):
    judge =0
    newal = sorted(al)
    xk = k-newal[h]
    newal.pop(h)
    for i in range(n-1):
        for j in range(k*2):
            if newal[i]<=j: #i+1番目の数字a[i]を足せるかも
                dp[i+1][j]=dp[i][j-newal[i]] or dp[i][j]
            else: #入る可能性はない
                dp[i+1][j]=dp[i][j]
    for l in range(xk,k*2):
        if judge ==1:
            break
        if dp[n-1][l] ==1:
            mins = l
            if l >=k:
                res += 1
                judge = 1
            else:
                judge = 1
print(res)

Submission status: Runtime Error

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

if sum(al) < k:
    print(n)
    exit()
dp=[[0 for i in range(k*2)] for j in range(n)]
dp[0][0]=1

res = 0
for h in range(n):
    if newal[h] > k:
        pass
    else:
        judge =0
        newal = sorted(al)
        xk = k-newal[h]
        newal.pop(h)
        for i in range(n-1):
            for j in range(k*2):
                if newal[i]<=j: #i+1番目の数字a[i]を足せるかも
                    dp[i+1][j]=dp[i][j-newal[i]] or dp[i][j]
                else: #入る可能性はない
                    dp[i+1][j]=dp[i][j]
        for l in range(xk,k*2):
            if judge ==1:
                break
            if dp[n-1][l] ==1:
                mins = l
                if l >=k:
                    res += 1
                    judge = 1
                else:
                    judge = 1
print(res)