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

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):
    judge =0
    newal = sorted(al)
    if newal[h] > k:
        break
    else:
        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: Time Limit Exceeded

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):
    judge =0
    newal = sorted(al)
    if newal[h] > k:
        pass
    else:
        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: Time Limit Exceeded

Solution code:
import sys
N,K=map(int,input().split())
alist=list(map(int,input().split()))
alist.sort(reverse=True)
#print(alist)

slist=[alist[0]]
for i in range(1,N):
  slist.append(slist[-1]+alist[i])
#print(slist)

if alist[-1]>=K:
  print(0)
  sys.exit(0)
elif alist[-2]>=K:
  print(1)
  sys.exit(0)
  
if sum(alist)<K:
  print(len(alist))
  sys.exit(0)
elif sum(alist)==K:
  print(0)
  sys.exit(0)
  
need_list=[False]*N
for i in range(N):
  if alist[i]>=K:
    #print([alist[i]],i)
    need_list[i]=True
  else:
    l,r=i+1,i+1
    while r<N:
      #print(i,l,r)
      if alist[i]+slist[r]-slist[l-1]<K:
        r+=1
      else:
        #print(i,l,r,alist[i]+slist[r]-slist[l-1])
        need_list[i]=True
        for j in range(l,r+1):
          need_list[j]=True
        l+=1
        r=max(l,r)
        
  if not need_list[i]:
    break
        
#print(need_list)
print(need_list.count(False))

Submission status: Time Limit Exceeded

Solution code:
import sys
N,K=map(int,input().split())
alist=list(map(int,input().split()))
alist.sort(reverse=True)
#print(alist)

slist=[alist[0]]
for i in range(1,N):
  slist.append(slist[-1]+alist[i])
#print(slist)

if alist[-1]>=K:
  print(0)
  sys.exit(0)
  
if sum(alist)<K:
  print(len(alist))
  sys.exit(0)
elif sum(alist)==K:
  print(0)
  sys.exit(0)
  
need_list=[False]*N
for i in range(N):
  if alist[i]>=K:
    #print([alist[i]],i)
    need_list[i]=True
  else:
    l,r=i+1,i+1
    while r<N:
      #print(i,l,r)
      if alist[i]+slist[r]-slist[l-1]<K:
        r+=1
      else:
        #print(i,l,r,alist[i]+slist[r]-slist[l-1])
        need_list[i]=True
        for j in range(l,r+1):
          need_list[j]=True
        l+=1
        r=max(l,r)
        
  if not need_list[i]:
    break
        
#print(need_list)
print(need_list.count(False))

Submission status: Time Limit Exceeded

Solution code:
import sys
N,K=map(int,input().split())
alist=list(map(int,input().split()))
alist.sort(reverse=True)
#print(alist)

slist=[alist[0]]
for i in range(1,N):
  slist.append(slist[-1]+alist[i])
#print(slist)

if sum(alist)<K:
  print(len(alist))
  sys.exit(0)
elif sum(alist)==K:
  print(0)
  sys.exit(0)
  
need_list=[False]*N
for i in range(N):
  if alist[i]>=K:
    #print([alist[i]],i)
    need_list[i]=True
  else:
    l,r=i+1,i+1
    while r<N:
      #print(i,l,r)
      if alist[i]+slist[r]-slist[l-1]<K:
        r+=1
      else:
        #print(i,l,r,alist[i]+slist[r]-slist[l-1])
        need_list[i]=True
        for j in range(l,r+1):
          need_list[j]=True
        l+=1
        r=max(l,r)
        
  if not need_list[i]:
    break
        
#print(need_list)
print(need_list.count(False))

Submission status: Time Limit Exceeded

Solution code:
import sys
N,K=map(int,input().split())
alist=list(map(int,input().split()))
alist.sort(reverse=True)
#print(alist)

slist=[alist[0]]
for i in range(1,N):
  slist.append(slist[-1]+alist[i])
#print(slist)

if sum(alist)<K:
  print(len(alist))
  sys.exit(0)
elif sum(alist)==K:
  print(0)
  sys.exit(0)
  
need_list=[False]*N
for i in range(N):
  if alist[i]>=K:
    #print([alist[i]],i)
    need_list[i]=True
  else:
    l,r=i+1,i+1
    while r<N:
      #print(i,l,r)
      if alist[i]+slist[r]-slist[l-1]<K:
        r+=1
      else:
        #print(i,l,r,alist[i]+slist[r]-slist[l-1])
        need_list[i]=True
        for j in range(l,r+1):
          need_list[j]=True
        l+=1
        r=max(l,r)
        
#print(need_list)
print(need_list.count(False))

Submission status: Time Limit Exceeded

Solution code:
import sys
N,K=map(int,input().split())
alist=list(map(int,input().split()))
alist.sort(reverse=True)

if sum(alist)<K:
  print(len(alist))
  sys.exit(0)
elif sum(alist)==K:
  print(0)
  sys.exit(0)
  
need_list=[False]*N
for i in range(N):
  if alist[i]>=K:
    #print([alist[i]],i)
    need_list[i]=True
  else:
    for j in range(i+1,N):
      mlist=[alist[i]]
      msum=alist[i]
      ilist=[i]
      
      for k in range(j,N):
        mlist.append(alist[k])
        msum+=alist[k]
        ilist.append(k)        
        if msum>=K:
          #print(mlist,msum,ilist)
          for ii in ilist:
            need_list[ii]=True          
          break
        
#print(need_list)
print(need_list.count(False))

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
l=list(map(int,input().split()))
ans=0
for J,j in enumerate(l):
    dp=[0]*k
    dp[0]=1
    for I,i in enumerate(l):
        if i>=k or J==I:
            continue
        for x in range(k-1,i-1,-1):
            dp[x]+=dp[x-i]
    x=0
    for i in range(k):
        if dp[i]:
            x=i
    if k-j>x:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
l=list(map(int,input().split()))
ans=0
for J,j in enumerate(l):
    kumi=set()
    kumi.add(0)
    for I,i in enumerate(l):
        if i>=k or J==I:
            continue
        for x in list(kumi):
            if x+i<k:
                kumi.add(x+i)
    x=max(kumi)
    if k-j>x:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

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

dp_l = [[0] * (k + 1) for _ in range(n + 1)]
dp_l[0][0] = 1

for i, e in enumerate(a):
    for j in range(k + 1):
        dp_l[i+1][j] += dp_l[i][j]
        nxt = min(k, j + e)
        dp_l[i+1][nxt] += dp_l[i][j]

dp_r = [[0] * (k + 1) for _ in range(n + 1)]
dp_r[0][0] = 1

for i, e in enumerate(a[::-1]):
    for j in range(k + 1):
        dp_r[i+1][j] += dp_r[i][j]
        nxt = min(k, j + e)
        dp_r[i+1][nxt] += dp_r[i][j]

for i in range(n + 1):
    for j in range(k, 0, -1):
        dp_r[i][j-1] += dp_r[i][j]

base = dp_l[n][k]
ans = 0
for i in range(1, n + 1):
    cnt = 0
    for j in range(k + 1):
        cnt += dp_l[i-1][j] * dp_r[n-i][k-j]
    if 2 * cnt == base:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
def main():
    N, K = map(int,input().split())
    a = sorted(list(map(int,input().split())))
    ans = 0
    lo = -1
    hi = N
    while hi-lo > 1:
        mid = (hi+lo)//2
        dp = np.zeros((N+1,K+1),dtype=np.bool)
        dp[0][0] = True
        f = 0
        for i in range(N):
            if i == mid:
                f = 1
            else:
                for j in range(K+1):
                    if j >= a[i]:
                        dp[i+1-f][j] = dp[i-f][j] or dp[i-f][j-a[i]]
                    else:
                        dp[i+1-f][j] = dp[i-f][j]
        f = 1
        for i in range(max(0,K-a[mid]),K):
            if dp[N-1][i] == True:
                f = 0
                break
        if f == 0:
            hi = mid
        else:
            lo = mid
    print(hi)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def main():
    N, K = map(int,input().split())
    a = sorted(list(map(int,input().split())))
    ans = 0
    lo = -1
    hi = N
    while hi-lo > 1:
        mid = (hi+lo)//2
        dp = [[0]*(K+1) for _ in range(N+1)]
        dp[0][0] = 1
        f = 0
        for i in range(N):
            if i == mid:
                f = 1
            else:
                for j in range(K+1):
                    if j >= a[i]:
                        dp[i+1-f][j] = dp[i-f][j] or dp[i-f][j-a[i]]
                    else:
                        dp[i+1-f][j] = dp[i-f][j]
        f = 1
        for i in range(max(0,K-a[mid]),K):
            if dp[N-1][i] == 1:
                f = 0
                break
        if f == 0:
            hi = mid
        else:
            lo = mid
    print(hi)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left


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

dp1 = [[False] * (K + 1) for _ in range(N + 1)]

for i in range(N + 1):
    dp1[i][0] = True
for i in range(N):
    a = A[i]
    d = K if a >= K else a - 1
    for j in range(K, d, -1):
        dp1[i + 1][j] = dp1[i][j] | dp1[i][j - a]

dp2 = [[False] * (K + 1) for _ in range(N + 1)]
for i in range(N + 1):
    dp2[i][0] = True
for i in range(N):
    a = A[N - 1 - i]
    d = K if a >= K else a - 1
    for j in range(K, d, -1):
        dp2[i + 1][j] = dp2[i][j] | dp2[i][j - a]


def solve(i):
    d1 = []
    d2 = []
    n = A[i]
    for j, k in enumerate(dp1[i]):
        if k:
            d1.append(j)
    for j, k in enumerate(dp2[N - 1 - i]):
        if k:
            d2.append(j)
    for a in d1:
        l = bisect_left(d2, K - n - a)
        r = bisect_left(d2, K - a)
        if r - l >= 1:
            return True
    return False


# [ok, ng) - Maximum
# (ng, ok] - Minimum
# ok が 最終的な答え
ok = N
ng = -1
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if solve(mid):
        ok = mid
    else:
        ng = mid


print(ok)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left


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

dp1 = [[0] * (K + 1) for _ in range(N + 1)]

for i in range(N + 1):
    dp1[i][0] = 1
for i in range(N):
    a = A[i]
    d = K if a >= K else a - 1
    for j in range(K, d, -1):
        dp1[i + 1][j] = dp1[i][j] | dp1[i][j - a]

dp2 = [[0] * (K + 1) for _ in range(N + 1)]
for i in range(N + 1):
    dp2[i][0] = 1
for i in range(N):
    a = A[N - 1 - i]
    d = K if a >= K else a - 1
    for j in range(K, d, -1):
        dp2[i + 1][j] = dp2[i][j] | dp2[i][j - a]


def solve(i):
    d1 = []
    d2 = []
    n = A[i]
    for j, k in enumerate(dp1[i]):
        if k:
            d1.append(j)
    for j, k in enumerate(dp2[N - 1 - i]):
        if k:
            d2.append(j)
    for a in d1:
        l = bisect_left(d2, K - n - a)
        r = bisect_left(d2, K - a)
        if r - l >= 1:
            return True
    return False


# [ok, ng) - Maximum
# (ng, ok] - Minimum
# ok が 最終的な答え
ok = N
ng = -1
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if solve(mid):
        ok = mid
    else:
        ng = mid


print(ok)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right


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

dp1 = [[0] * (K + 1) for _ in range(N + 1)]
dp1[0][0] = 1
for i in range(N):
    a = A[i]
    for j in range(K + 1):
        here = dp1[i][j]
        dp1[i + 1][min(K, j + a)] |= here
        dp1[i + 1][j] |= here

dp2 = [[0] * (K + 1) for _ in range(N + 1)]
dp2[0][0] = 1
for i in range(N):
    a = A[N - 1 - i]
    for j in range(K + 1):
        here = dp2[i][j]
        dp2[i + 1][min(K, j + a)] |= here
        dp2[i + 1][j] |= here

cnt = 0
for i in range(N):
    d1 = []
    d2 = []
    n = A[i]
    for j, k in enumerate(dp1[i]):
        if k:
            d1.append(j)
    for j, k in enumerate(dp2[N - 1 - i]):
        if k:
            d2.append(j)
    for a in d1:
        l = bisect_left(d2, K - n - a)
        r = bisect_left(d2, K - a)
        if r - l >= 1:
            cnt += 1
            break
    
print(N - cnt)

Submission status: Time Limit Exceeded

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


# [ok, ng) - Maximum
# (ng, ok] - Minimum
# ok が 最終的な答え
ok = N
ng = -1
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    n = mid
    dp = set()
    dp.add(0)
    for i in range(N):
        a = A[i]
        if i == n or a >= K:
            continue
        for j in range(K - a - 1, -1, -1):
            if j in dp:
                dp.add(j + a)
    rst = any(k in dp for k in range(max(0, K - A[n]), K))
    if rst:
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Time Limit Exceeded

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


# [ok, ng) - Maximum
# (ng, ok] - Minimum
# ok が 最終的な答え
ok = N
ng = -1
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    n = mid
    dp = [0] * (K + 1)
    dp[0] = 1
    for i in range(N):
        a = A[i]
        if i == n or a >= K:
            continue
        for j in range(K, -1, -1):
            dp[min(K, j + a)] |= dp[j]
    rst = any(dp[k] for k in range(max(0, K - A[n]), K))
    if rst:
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Time Limit Exceeded

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


# [ok, ng) - Maximum
# (ng, ok] - Minimum
# ok が 最終的な答え
ok = N
ng = -1
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    n = mid
    dp = [0] * (K + 1)
    dp[0] = 1
    for i in range(N):
        a = 0 if i == n else A[i]
        for j in range(K, -1, -1):
            dp[min(K, j + a)] |= dp[j]
    rst = any(dp[k] for k in range(max(0, K - A[n]), K))
    if rst:
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Time Limit Exceeded

Solution code:
def solve(n):
    global N, K
    dp = [[0] * (K + 1) for _ in range(N + 1)]
    dp[0][0] = 1
    for i in range(N):
        a = 0 if i == n else A[i]
        for j in range(max(0, K - a + 1)):
            here = dp[i][j]
            dp[i + 1][j + a] |= here
            dp[i + 1][j] |= here
    rst = any(dp[N][k] for k in range(max(0, K - A[n]), K))
    return rst


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


# [ok, ng) - Maximum
# (ng, ok] - Minimum
# ok が 最終的な答え
ok = N
ng = -1
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    n = mid
    dp = [[0] * (K + 1) for _ in range(N + 1)]
    dp[0][0] = 1
    for i in range(N):
        a = 0 if i == n else A[i]
        for j in range(K + 1):
            here = dp[i][j]
            dp[i + 1][min(K, j + a)] |= here
            dp[i + 1][j] |= here
    rst = any(dp[N][k] for k in range(max(0, K - A[n]), K))
    if rst:
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import numpy as np
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    mod = 10**9+7
    dp = np.zeros(k, dtype=np.int32)
    dp[0] = 1
    for i in range(n):
        aa = a[i]
        if aa >= k:
            continue
        dp[aa:] = (dp[aa:]+dp[:k-aa]) % mod
    b = [1]*n
    for i in range(n):
        if a[i] >= k:
            b[i] = 0
            continue
        aa = a[i]
        dp2 = np.zeros(k, dtype=np.int32)
        dp2[:aa] = dp[:aa]
        for j in range(aa, k):
            dp2[j] = (dp[j]-dp2[j-aa]) % mod
        if sum(dp2[k-aa:]) != 0:
            b[i] = 0
    print(sum(b))


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    mod = 10**9+7
    dp = [0]*k
    dp[0] = 1
    for i in range(n):
        aa = a[i]
        if aa >= k:
            continue
        for j in range(k-aa-1, -1, -1):
            dp[aa+j] = (dp[aa+j]+dp[j]) % mod
    b = [1]*n
    for i in range(n):
        if a[i] >= k:
            b[i] = 0
            continue
        aa = a[i]
        dp2 = [0]*k
        for j in range(aa):
            dp2[j] = dp[j]
        for j in range(aa, k):
            dp2[j] = (dp[j]-dp2[j-aa]) % mod
        for j in range(k-aa, k):
            if dp2[j] != 0:
                b[i] = 0
                break
    print(sum(b))


main()

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
def f(x):
  if a[x]>=k:
    return True
  dp=[False]*k
  dp[0]=True
  y=0
  for i in range(n):
    if i==x:
      continue
    for j in range(y,-1,-1):
      if j+a[i]>=k:
        continue
      dp[j+a[i]]|=dp[j]
    y=min(k-1,y+a[i])
  return sum(dp[k-a[x]:k])
if not f(n-1):
  print(n)
  exit()
if f(0):
  print(0)
  exit()
l,r=0,n-1
while r-l>1:
  mid=(r+l)//2
  if f(mid):
    r=mid
  else:
    l=mid
print(r)

Submission status: Time Limit Exceeded

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

l=N
for i in range(0,N):
    if A[i]>=K:
        l=i
        break
A=A[:l]
N=l
#A[num]が必要な数か判定
def condition(num):
    if N-1>num:
        test=A[:num]+A[num+1:]
    else:
        test=A[:num]
    if A[num]>=K:
        return True
    else:
        dp=[False for i in range(0,K)]
        for i in range(K-A[num],K):
            dp[i]=True

        for i in range(1,N):
            for j in range(0,K-test[i-1]):
                dp[j]=dp[j] or dp[j+test[i-1]]
        return dp[0]

#必要な数のうち最小のもの
if N==0:
    print(0)
elif N==1:
    if A[0]>=K:
        print(0)
    else:
        print(1)
else:
    start=0
    end=N-1
    while end-start>1:
        t=(end+start)//2
        if condition(t):
            end=t
        else:
            start=t

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

Submission status: Time Limit Exceeded

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

#A[num]が必要な数か判定
def condition(num):
    if N-1>num:
        test=A[:num]+A[num+1:]
    else:
        test=A[:num]
    if A[num]>=K:
        return True
    else:
        dp=[False for i in range(0,K)]
        for i in range(K-A[num],K):
            dp[i]=True

        for i in range(1,N):
            for j in range(0,K-test[i-1]):
                dp[j]=dp[j] or dp[j+test[i-1]]
        return dp[0]

#必要な数のうち最小のもの
if N==0:
    print(0)
elif N==1:
    if A[0]>=K:
        print(0)
    else:
        print(1)
else:
    start=0
    end=N-1
    while end-start>1:
        t=(end+start)//2
        if condition(t):
            end=t
        else:
            start=t

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

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
#A[num]が必要な数か判定
def condition(num):
    if N-1>num:
        test=A[:num]+A[num+1:]
    else:
        test=A[:num]
    if A[num]>=K:
        return True
    else:
        dp=[False for i in range(0,K)]
        for i in range(K-A[num],K):
            dp[i]=True

        for i in range(1,N):
            for j in range(0,K-test[i-1]):
                if dp[j+test[i-1]]:
                    dp[j]=True
        return dp[0]

#必要な数のうち最小のもの
if N==1:
    if A[0]>=K:
        print(0)
    else:
        print(1)
else:
    start=0
    end=N-1
    while end-start>1:
        t=(end+start)//2
        if condition(t):
            end=t
        else:
            start=t

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

Submission status: Time Limit Exceeded

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

#A[num]が必要な数か判定
def condition(num):
    if N-1>num:
        test=A[:num]+A[num+1:]
    else:
        test=A[:num]
    if A[num]>=K:
        dp=[[False for i in range(0,K)] for i in range(0,N)]
        for i in range(0,K):
            dp[0][i]=True

        for i in range(1,N):
            for j in range(0,K):
                if K>j+test[i-1]:
                    dp[i][j]=dp[i-1][j] or dp[i-1][j+test[i-1]]
                else:
                    dp[i][j]=dp[i-1][j]

        return dp[N-1][0]

    else:
        dp=[[False for i in range(0,K)] for i in range(0,N)]
        for i in range(0,K):
            if i>=K-A[num]:
                dp[0][i]=True

        for i in range(1,N):
            for j in range(0,K):
                if K>j+test[i-1]:
                    dp[i][j]=dp[i-1][j] or dp[i-1][j+test[i-1]]
                else:
                    dp[i][j]=dp[i-1][j]

        return dp[N-1][0]

#必要な数のうち最小のもの
if N==1:
    if A[0]>=K:
        print(0)
    else:
        print(1)
else:
    start=0
    end=N-1
    while end-start>1:
        t=(end+start)//2
        if condition(t):
            end=t
        else:
            start=t

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

Submission status: Time Limit Exceeded

Solution code:
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    N,K=MI()
    a=LI()#下位の連続するn枚が不要なはず
    a.sort()
    for i in range(N):#K以上ならば必要
        if a[i]>=K:
            a=a[:i]
            break
    N=len(a)
                    
                    
    #x番目の数が必要かどうかの判定 
    #必要なものだけで構成された集合をもとに考えれば良いわけではない，不必要な分も考えなければならない             
    def ch(x):
        
        #使い回す，i番目まででjが作れるか
        dp=[False]*K
        dp[0]=True
        for i in range(N):
            if i==x:
                continue
            else:
                for j in range(K-1,a[i]-1,-1):
                    dp[j]|=dp[j-a[i]]
                
                        
        #K未満K-a[x]以上が作れれば良い    
        for j in range(K-a[x],K):
            if  dp[j]:
                return True
        return False
            
    
                        
    ng=-1
    ok=N
    while abs(ok-ng)>1:
        med=(ok+ng)//2
        
        if ch(med):
            ok=med
        else:
            ng=med
            
    print(ng+1)
    


main()

Submission status: Time Limit Exceeded

Solution code:
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    N,K=MI()
    a=LI()#下位の連続するn枚が不要なはず
    a.sort()
                    
                    
    #x番目の数が必要かどうかの判定 
    #必要なものだけで構成された集合をもとに考えれば良いわけではない，不必要な分も考えなければならない             
    def ch(x):
        if a[x]>=K:
            return True
        else:
            #使い回す，i番目まででjが作れるか
            dp=[False]*K
            dp[0]=True
            for i in range(N):
                if i==x:
                    continue
                else:
                    for j in range(K-1,a[i]-1,-1):
                        dp[j]|=dp[j-a[i]]
                    
                            
            #K未満K-a[x]以上が作れれば良い    
            for j in range(K-a[x],K):
                if  dp[j]:
                    return True
            return False
                
            
            
        return False
    
                        
    ng=-1
    ok=N
    while abs(ok-ng)>1:
        med=(ok+ng)//2
        
        if ch(med):
            ok=med
        else:
            ng=med
            
    print(ng+1)
    
    
   
    
            
    
    
    

main()

Submission status: Time Limit Exceeded

Solution code:
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    N,K=MI()
    a=LI()#下位の連続するn枚が不要なはず
    a.sort()
                    
                    
    #x番目の数が必要かどうかの判定 
    #必要なものだけで構成された集合をもとに考えれば良いわけではない，不必要な分も考えなければならない             
    def ch(x):
        if a[x]>=K:
            return True
        else:
            #使い回す，i番目まででjが作れるか
            dp=[False]*K
            dp[0]=True
            for i in range(N):
                if i==x:
                    continue
                else:
                    for j in range(K-1,-1,-1):
                        jj=j-a[i]
                        if jj>=0:
                            if dp[jj]:
                                dp[j]=True
                    
                            
            #K未満K-a[x]以上が作れれば良い    
            for j in range(K-a[x],K):
                if  dp[j]:
                    return True
            return False
                
            
            
        return False
    
                        
    ng=-1
    ok=N
    while abs(ok-ng)>1:
        med=(ok+ng)//2
        
        if ch(med):
            ok=med
        else:
            ng=med
            
    print(ng+1)
    
    
   
    
            
    
    
    

main()

Submission status: Time Limit Exceeded

Solution code:
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    N,K=MI()
    a=LI()#下位の連続するn枚が不要なはず
    a.sort(reverse = True)
    
    
    #i番目までを使ってjが作れるかどうか
    dp=[[False]*K for _ in range(N+1)]
    dp[0][0]=1
    for i in range(N):
        for j in range(K):
            if dp[i][j]==1:
                dp[i+1][j]=1
                jj=j+a[i]
                if jj<K:
                    dp[i+1][jj]=1
                    
                    
    #i番目以降を使ってjが作れるかどうか
    dp2=[[0]*K for _ in range(N+1)]
    dp2[-1][0]=True
    for i in range(N):
        for j in range(K):
            if dp2[-1-i][j]==True:
                dp2[-2-i][j]=True
                jj=j+a[-1-i]
                if jj<K:
                    dp2[-2-i][jj]=True
    
    #累積和チックに
    for i in range(N+1):
        for j in range(K-1):
            dp[i][j+1]+=dp[i][j]
                    
                    
    #x番目の数が必要かどうかの判定 
    #必要なものだけで構成された集合をもとに考えれば良いわけではない，不必要な分も考えなければならない             
    def ch(x):
        if a[x]>=K:
            return True
        else:
            #dp2でsを作り，dpで，K-s未満，K-a[x]-s以上のものが作れれば良い，
            #この範囲内で1が一つでもあれば良いので，累積和の差分が1以上ならok
            for s in range(K-a[x]):
                if dp2[x+1][s]==True:
                    if dp[x][K-s-1] - dp[x][K-a[x]-s-1]>=1:
                        return True
        return False
    
                        
    ng=N
    ok=-1
    while abs(ok-ng)>1:
        med=(ok+ng)//2
        
        if ch(med):
            ok=med
        else:
            ng=med
            
    print(N-(ok+1))
    
    
   
    
            
    
    
    

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
a = list(map(int, input().split())) + [10 ** 10]
a.sort()

def check(x):
  dp = [0] * (K + 1)
  dp[0] = 1
  for i in range(N):
    for j in range(K - 1, -1, -1):
      if i == x: continue
      if dp[j]:
        dp[min(K, j + a[i])] = dp[j]
  for j in range(max(0, K - a[x]), K):
    if dp[j]: return True
  return False
#for i in range(N): print(check(i))

if check(0):
  print(0)
  exit(0)
ok = N + 1
ng = 0
while ok - ng > 1:
  m = (ok + ng) // 2
  if check(m): ok = m
  else: ng = m
print(ok)

Submission status: Time Limit Exceeded

Solution code:
'''
1枚抜いてDPをN枚についてやれば良い, がこれでは間に合わない
そこで必要不要の境界を二分探索で探す
するとO(N^2K)→O(NKlogN)となって間に合う

もう1つの方法は分からない
'''

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    N,K = map(int, input().split())
    a = list(map(int, input().split()))
    a = sorted(a)
    a = a[:bisect_left(a, K)]
    n = len(a)
    def dp(num):
        dp = [[0]*(K) for _ in range(n)]
        dp[0][0] = 1
        b = a[:num]+a[num+1:] #N-1個
        for i in range(n-1):
            for j in range(K):
                if b[i]<=j:
                    dp[i+1][j] = dp[i][j-b[i]] or dp[i][j]
                else:
                    dp[i+1][j]=dp[i][j]
        return any(dp[n-1][K-a[num]:])

    left = 0
    right = n-1
    while left<=right:
        mid = (left+right)//2
        if dp(mid):
            right = mid-1
        else:
            left = mid+1
    print(right+1)

if __name__ == '__main__':
    main()