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

Solution (Python):
import numpy as np

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

dp_left = np.zeros((N + 1, K), dtype=bool)
dp_right = np.zeros((N + 1, K), dtype=bool)
dp_left[0, 0] = 1
dp_right[N, 0] = 1

for i in range(N):
    dp_left[i + 1] = dp_left[i]
    dp_right[N - i - 1] = dp_right[N - i]
    if (a := A[i]) < K:
        dp_left[i + 1, a:] |= dp_left[i, :-a]
    if (a := A[N - i - 1]) < K:
        dp_right[N - i - 1, a:] |= dp_right[N - i, :-a]

ans = 0
for i, a in enumerate(A):
    left_true = np.nonzero(dp_left[i])[0]
    right_true = np.nonzero(dp_right[i + 1])[0]

    ss = np.searchsorted(right_true, K - left_true) - 1
    if all(right_true[ss] + left_true + a < K):
        ans += 1

print(ans)

Solution (Python):
from itertools import accumulate

def main():
    N, K = map(int, input().split())
    As = list(map(int, input().split()))
    
    nonzeros = [1]
    for a in As:
        ndp = nonzeros[-1]
        if a <= K:
            ndp |= (nonzeros[-1] % (1 << (K-a))) << a
        nonzeros.append(ndp)
    dp = [0] * (K+1)
    dp[0] = 1
    acc = list(accumulate(dp)) + [0]
    ans = 0
    for i in range(N, 0, -1):
        a = As[i-1]
        ndp = []
        for j in range(K+1):
            t = dp[j] if j < a else dp[j] + dp[j-a]
            ndp.append(0 if t == 0 else 1)
        dp = ndp
        if a < K:
            nonzero = nonzeros[i-1]
            for y in range(K+1):
                if nonzero & 1:
                    t = K-y-a-1
                    if acc[K-y-1] > acc[t if t >= 0 else -1]:
                        break
                nonzero >>= 1
            else:
                ans += 1
        acc = list(accumulate(dp)) + [0]
    
    print(ans)

main()

Solution (Python):
N, K = map(int, input().split())
A = [0] + sorted(map(int, input().split()))


rdp_shift = [N + 1] * K  
rdp_shift[0] = 0
rdp = [0] * K  
rdp[0] = 1
for i in range(1, N + 1):
    rdp2 = [0] * K
    for j in range(K):
        if rdp[j] == 1:
            rdp2[j] = 1
            continue
        
        
        if j - A[-i] >= 0 and rdp[j - A[-i]] == 1:
            rdp2[j] = 1
            rdp_shift[j] = i
    rdp = rdp2


ldp = [0] * K
ldp[0] = 1
S = [0] * (K + 1)
ans = 0
for i in range(1, N + 1):
    
    
    for j in range(K):
        
        S[j + 1] = S[j]
        if rdp_shift[j] <= N - i:
            
            S[j + 1] += 1
            
            
    no_need = True
    for lval in range(K):
        
        if ldp[lval] == 0:
            continue
        
        rval = S[K - lval] - S[max(0, K - A[i] - lval)]
        
        
        
        if rval > 0:
            
            no_need = False
            break
    if no_need:
        ans += 1

    
    ldp2 = [0] * K
    for j in range(K):
        if ldp[j] == 1 or (j >= A[i] and ldp[j - A[i]] == 1):
            ldp2[j] = 1
    ldp = ldp2
print(ans)

Solution (Python):
import sys
N, K = map(int, input().split())
A = list(map(int, input().split()))

A.sort()

DP = [0 for k in range(K+1)] 
DP[0] = 1
for a in A:
  for k in range(K-a,-1,-1):
    DP[k+a] += DP[k]

"""
for k in range(1,2*K+1): 
  DP[k] += DP[k-1]
print(DP)
"""
"""
if sum(DP[0:K]) == 2**N:
  print(N)
  sys.exit()
"""



def det(t):
  a = A[t]
  if a >= K:
    return False
  DP_rev = [0 for _ in range(K)] 
  ans = True
  for i in range(K):
    DP_rev[i] = DP[i] 
    if i-a >= 0:
      DP_rev[i] -= DP_rev[i-a]
    if i >= K-a and DP_rev[i] > 0:
      ans = False
      break
  del DP_rev
  return ans

lt = 0
rt = N-1
if not det(lt):
  print(0)
  sys.exit()
if det(rt):
  print(rt+1)
  sys.exit()

while rt - lt > 1:
  ct = (lt + rt) // 2
  if det(ct):
    lt = ct
  else:
    rt = ct
print(rt)

Solution (Python):
def main():
    N, K = map(int, input().split())
    A = [0] + list(map(int, input().split()))
    
    rdp_shift = [N + 1] * K  
    rdp_shift[0] = 0
    rdp = [0] * K  
    rdp[0] = 1
    for i in range(N):
        rdp2 = [0] * K
        for j in range(K):
            if rdp[j] == 1:
                rdp2[j] = 1
            elif (j >= A[-i] and rdp[j - A[-i]] == 1):
                
                rdp2[j] = 1
                rdp_shift[j] = i
                
        rdp = rdp2
    
    ldp = [0] * K  
    ldp[0] = 1
    S = [0] * (K + 1)
    ans = 0
    for i in range(1, N + 1):
        
        
        for j in range(K):
            S[j + 1] = S[j]
            
            if rdp_shift[j] <= N - i:
                S[j + 1] += 1
        no_need = True
        for lval in range(K):
            if ldp[lval] == 0:
                continue
            
            rval = S[K - lval] - S[max(0, K - A[i] - lval)]
            
            if rval > 0:
                no_need = False
                break
        if no_need:
            ans += 1

        
        ldp2 = [0] * K
        for j in range(K):
            if ldp[j] == 1 or (j >= A[i] and ldp[j - A[i]] == 1):
                ldp2[j] = 1
        ldp = ldp2
    print(ans)
    


if __name__ == "__main__":
    main()

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse = True)
ans = n
s, cnt = 0, 0
for i in a:
    cnt += 1
    if s + i < k:
        s += i
    else:
        ans = n - cnt
print(ans)

Solution (Python):
import numpy as np

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    if sum(a) >= k:
        a.sort()
        L, R = -1, n-1
        while L+1 < R:
            P = (L+R+1)//2
            if k <= a[P]:
                R = P
                continue
            dp = np.zeros((k+1), dtype=np.bool)
            dp[0] = True
            for j in range(n):
                if k <= a[j] or j == P:
                    continue
                dp[a[j]:] |= dp[:-a[j]]
            f = False
            for j in range(k-a[P], k):
                f |= dp[j]
            if f:
                R = P
            else:
                L = P
        print(R)
    else:
        print(n)

if __name__ == "__main__":
    main()

Solution (Python):
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007



def main():
	
	n, k = tin()
	
	al = lin()
	al.sort(reverse = True)
	ss=sum(al)
	arrive=[0]*k
	arrive[0]=1
	useful_set=set()
	for v in al:
		ss -= v
		u_max=0
		if v >=k:
			useful_set.add(v)
			continue
		for i, _ in enumerate(arrive):
			p = k-i-1
			is_on = arrive[p]
			if is_on==1 and p+v >= k:
				useful_set.add(v)
				u_max=k
			elif is_on==1:
				arrive[p+v] = 1
				u_max=max(u_max, p+v)
		if u_max + ss >= k:
			useful_set.add(v)
	ret=0
	for v in al:
		if v not in useful_set:
			ret += 1
	return ret
			
		
	
	

isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):
import sys

def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  


N,K = MI()
A = LI()
A.sort()


def f(n):  
    B = [0] + [A[i] for i in range(N) if i != n]
    dp = [0]*K  
    dp[0] = 1
    for i in range(1,N):
        b = B[i]
        for j in range(K-1,-1,-1):
            if j >= b:
                dp[j] |= dp[j-b]
            else:
                dp[j] = dp[j]
    if sum(dp[j] for j in range(max(K-A[n],0),K)) != 0:
        return True
    else:
        return False


left = -1  
right = N  
while left + 1 < right:
    mid = (left + right)//2
    if f(mid):
        right = mid
    else:
        left = mid

print(right)

Solution (Python):
import sys

def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  


N,K = MI()
A = LI()
A.sort()


def f(n):  
    B = [0] + [A[i] for i in range(N) if i != n]
    dp = [[0]*K for _ in range(2)]  
    dp[0][0] = 1
    for i in range(1,N):
        b = B[i]
        for j in range(K):
            if j >= b:
                dp[i%2][j] = dp[1-i%2][j] | dp[1-i%2][j-b]
            else:
                dp[i%2][j] = dp[1-i%2][j]
    if sum(dp[(N-1) % 2][j] for j in range(max(K-A[n],0),K)) != 0:
        return True
    else:
        return False


left = -1  
right = N  
while left + 1 < right:
    mid = (left + right)//2
    if f(mid):
        right = mid
    else:
        left = mid

print(right)

Solution (Python):
import sys
import itertools

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



import sys
import itertools

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


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 - A[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)

Solution (Python):
N,K = map(int,input().split())
A = sorted(list(map(int,input().split())))[::-1]
S = 0
ans = 0

for a in A:
  if S+a<K:
    S+=a
    ans+=1
  else:
    ans=0

print(ans)

Solution (Python):
import sys
from itertools import accumulate
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の発想が出なかったのは切腹。
    まずは部分点解法を実装してみる。

    →次に二分探索でdpを行う回数を削減する。ai <= ajに対してajが不要ならばaiも不要なことが対偶を取って分かる。
    そこでAをソートしたうえで必要と不要の境目を見つければよい。

    →PypyだとO(NKlogN)は通らなかったので、O(NK)解法を実装。
    一度二分探索できる話は忘れて、A-{a}から作れる部分和は(aの左側からの部分和)+(aの右側からの部分和)と
    かけることに注意すれば、左側からとれる部分和と右側からとれる部分和を前計算しておけばよい。
    rdpのテーブルメモリが重くてMLEするので（信じられん）、rdp_shiftに1になった瞬間のiを記録することにする。
    """
    rdp_shift = [N + 1] * K  
    rdp_shift[0] = 0
    rdp = [0] * K  
    rdp[0] = 1
    for i in range(1, N):
        rdp2 = [0] * K
        for j in range(K):
            if rdp[j] == 1:
                rdp2[j] = 1
            elif (j >= A[-i] and rdp[j - A[-i]] == 1):
                rdp2[j] = 1
                rdp_shift[j] = i
        rdp = rdp2

    ldp = [0] * K  
    ldp[0] = 1
    S = [0] * (K + 1)
    ans = 0
    for i in range(1, N + 1):
        
        for j in range(K):
            S[j + 1] = S[j]
            if rdp_shift[j] <= N - i:
                S[j + 1] += 1
        no_need = True
        for lval in range(K):
            if ldp[lval] == 0: continue
            rval = S[K - lval] - S[max(0, K - A[i] - lval)]
            if rval > 0:
                no_need = False
                break
        if no_need: ans += 1

        
        ldp2 = [0] * K
        for j in range(K):
            if ldp[j] == 1 or (j >= A[i] and ldp[j - A[i]] == 1):
                ldp2[j] = 1
        ldp = ldp2
    print(ans)
    

if __name__ == "__main__":
    main()

Solution (Python):
def examA():
    N = DI()/dec(7)
    ans = N
    print(N)
    return

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

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

def examD():
    N, K = LI()
    A = LI()
    A.sort()
    mask = (1 << K) - 1

    noneed = -1; need = N
    while(need-noneed>1):
        
        i = (need+noneed)//2
        if A[i]>=K:
            is_need = True
        else:
            dp = 1
            for j in range(N):
                a = A[j]
                if a>K:
                    break
                if i == j:
                    continue
                dp |= ((dp << a) & mask)
            

            is_need = (dp > mask>>A[i])

            

        if is_need:
            need = i
        else:
            noneed = i

    ans = noneed + 1

    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

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

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


n,k = list(map(int, input().split()))
a = list(map(lambda x: min(int(x), k+1), input().split()))
a.sort()
mask = (1<<(k+1)) - 1
def sub(ii):
    dp = 1
    for i in range(n):
        if i==ii:
            continue
        dp |= (dp<<a[i]) & mask


    val = max(i for i in range(k) if (dp>>i)&1)
    return val+a[ii]>=k
if sub(0):
    ans = 0
elif not sub(n-1):
    ans = n
else:
    l = 0
    r = n-1
    while l<r-1:
        m = (l+r)//2
        if sub(m):
            r = m
        else:
            l = m
    ans = l+1
print(ans)

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

ans = 0
sum = 0
cnt = 0
for i in range(N):
  a = A[i]
  if sum+a>=K:
    ans += cnt+1
    cnt = 0
  else:
    sum += a
    cnt += 1
    
print(N-ans)

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





N,K = IL()
A = IL()
A.sort(reverse=True)

ans = 0
now = 0
cnt = 0
for i in range(N):
  a = A[i]
  if now+a>=K:
    ans += cnt+1
    cnt = 0
  else:
    now += a
    cnt += 1
    
print(N-ans)

Solution (Python):
N,K=map(int,input().split())
A=sorted(filter(lambda x:x<K,list(map(int,input().split()))))
N=len(A)
if N==0:
  print(0)
  exit()
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)

Solution (Python):
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
        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
    nn=biser(list(range(N)),isunnec)+1
    print(nn)

if __name__=='__main__':
    main()

Solution (Python):
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
        
        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
        
        
        
        
        
        
        
        
        
    
    nn=biser(list(range(N)),isunnec)+1
    
    print(nn)

if __name__=='__main__':
    main()

Solution (Python):




N, K = map(int, input().split())
a=list(map(int, input().split()))
a.sort()
ans = N
t = 0
for i in range(N-1, -1, -1) :
  if t+a[i] < K:
    t += a[i]
  else:
    ans = min(ans, i)
print(ans)

Solution (Python):
N, K = map(int, input().split())
a=list(map(int, input().split()))
a.sort()
ans = N
t = 0
for i in range(N-1, -1, -1) :
  if t+a[i] < K:
    t += a[i]
  else:
    ans = min(ans, i)
print(ans)

Solution (Python):
N, K = map(int, input().split())
a = list(map(int, input().split()))
 
a = sorted(a)
ans = N
t = 0

for i in range(N-1, -1, -1) :
    if t+a[i] < K :
        t += a[i]
    else :
        ans = min(ans, i)
 
print(ans)

Solution (Python):
import numpy as np


def check(x):
    dp = np.zeros(k, np.bool)
    dp[0] = True
    for e in a[:x] + a[x+1:]:
        dp[e:] |= dp[:-e]

    return dp[-a[x]:].any()


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

a.sort()

lb = -1
ub = n
while ub - lb > 1:
    m = (lb + ub) // 2
    if check(m):
        ub = m
    else:
        lb = m

print(ub)

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
import numpy as np
def bisearch(t):
  dp=np.full(k+1,False)
  dp[0]=True
  for i in range(n):
    if i==t:continue
    dp[a[i]:] = np.logical_or(dp[a[i]:], dp[:-a[i]]) 
  return any(dp[max(0,k-a[t]):k])
l,r=-1,n
while r-l>1:
  x=(l+r)//2
  if bisearch(x):
    r=x
  else:
    l=x
print(r)

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
import numpy as np
def bisearch(t):
  dp=np.full(k,False)
  dp[0]=True
  for i in range(n):
    if i==t:continue
    dp[a[i]:] = np.logical_or(dp[a[i]:], dp[:-a[i]]) 
  return any(dp[max(0,k-a[t]):])
l,r=-1,n
while r-l>1:
  x=(l+r)//2
  if bisearch(x):
    r=x
  else:
    l=x
print(r)

Solution (Python):
import sys
input = sys.stdin.buffer.readline


def solve(mid):
    """のぞいてもいいカードならTrueを返す"""
    dp = 1
    mask = (1 << k) - 1
    if k <= a[mid]:
        return False
    for i, weight in enumerate(a):
        if i == mid:
            continue
        dp |= dp << min(weight, k + 10)
        dp &= mask
    return dp >> (k - a[mid]) == 0
     

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

a.sort()
ok = 0
ng = n
if not solve(ok):
    print(0)
    exit()

while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if solve(mid):
        ok = mid
    else:
        ng = mid

print(ok + 1)

Solution (Python):

import sys
input = sys.stdin.readline









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

A.sort()

ans = N
total = 0

for i in range(N):
    
    a = A[N-1-i]
    
    if total + a < K:
        total += a
    
    else:
        ans = min(ans, N-1-i)

print(ans)

Solution (Python):
n,k = map(int,input().split())
a = [0]+sorted(filter(lambda x: x < k, map(int,input().split())))
n = len(a)

def search(m):

    dp = [1] + [0]*k
    for i in range(n):
        if i == m:
            continue
        for j in range(k,a[i]-1,-1):
            dp[j] |= dp[j-a[i]]
    for i in range(k-a[m],k):
        if dp[i]:
            return True
    return False
le = 0
ri = n


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

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

print(le)

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = []
for a in A:
  if a < K:
    B.append(a)

N = len(B)
B.sort(reverse=True)
check = [True] + [False]*N
dp = [[False]*(K+1) for i in range(N+1)]
dp[0][0] = True
for i, b in enumerate(B, 1):
  for j in range(K+1):
    dp[i][j] = dp[i-1][j]
    if K-b <= j <= K - 1 and dp[i][j]:
      check[i] = True
    if j >= b and dp[i-1][j-b]:
      dp[i][j] = True

ans = 0
for i in range(N, -1, -1):
  if check[i]:
    break
  ans += 1

print(ans)

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,K=map(int,input().split())
    a=list(map(int,input().split()))
    a.sort(reverse=1)
    dp0=[1]*N
    dp1=[1]*N
    mask=(1<<K)-1
    for i in range(N-1):
        if a[i]<K:
            dp0[i+1]=(dp0[i]|(dp0[i]<<a[i]))&mask
        else:
            dp0[i+1]=dp0[i]
        if a[N-i-1]<K:
            dp1[N-i-2]=(dp1[N-i-1]|(dp1[N-i-1]<<a[N-i-1]))&mask
        else:
            dp1[N-i-2]=dp1[N-i-1]
    ans=0
    def nibutan(ok,ng):
        while abs(ok-ng) > 1:
            mid = (ok + ng) // 2
            if solve(mid):
                ok = mid
            else:
                ng = mid
        return ok
    
    def solve(i):
        if a[i]<K:
            mask2=((1<<a[i])-1)<<(K-a[i])
            for j in range(dp0[i].bit_length()):
                if j>mask2.bit_length():
                    return True
                if (dp0[i]>>j)&1:
                    if dp1[i]&(mask2>>j):
                        return True
        else:
            return True
        return False
    
    res=nibutan(-1,N)
    print(N-1-res)
    


if __name__ == '__main__':
    main()

Solution (Python):
from itertools import accumulate
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
acc = list(accumulate(a))

def maxsum(ls,k):
  l = len(ls)
  if l==0:
    return 0
  dp = [0 for i in range(l+1)]
  dp[0] = 1
  for i in range(1,l+1):
    dp[i] = (dp[i-1]|(dp[i-1]<<ls[i-1]))&((1<<k)-1)
  for b in range(k-1,-1,-1):
    if dp[l] & 1<<b:
      return b

for i in range(n):
  if a[i]>=k:
    a = a[:i]
    break
n = len(a)
if acc[n-1] < k:
  print(n)
  exit()
sepa=[]
for i in range(n-1):
  if acc[i]<a[i+1]:
    sepa.append(i)
m=len(sepa)
if m==0:
  print(0)
  exit()
lf = 0
r = m-1
while lf<r:
  mid = (lf+r)//2
  x=sepa[mid]
  sumx = acc[x]
  if maxsum(a[x+1:],k)+sumx >= k:
    r = mid
  else:
    lf = mid+1
if r==0:
  t=sepa[0]
  if maxsum(a[t+1:],k)+acc[t]>=k:
    print(0)
  else:
    print(sepa[r]+1)
else:
  print(sepa[r]+1)

Solution (Python):

N, K = map(int, input().split())
a = list(map(int, input().split()))
 
a = sorted(a)
ans = N
t = 0

for i in range(N-1, -1, -1) :
    if t+a[i] < K :
        t += a[i]
    else :
        ans = min(ans, i)
 
print(ans)

Solution (Python):

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





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, a - 1, -1):
            dp[j] |= dp[j - a]
    rst = any(dp[k] for k in range(max(0, K - A[n]), K))
    if rst:
        ok = mid
    else:
        ng = mid
print(ok)

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


    
    
    
    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, a - 1, -1):
                dp[j] |= dp[j - a]
        rst = any(dp[k] for k in range(max(0, K - A[n]), K))
        if rst:
            ok = mid
        else:
            ng = mid
    print(ok)


main()

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


    
    
    
    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)


main()

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
def card(N,K,A):
    card = sorted(A,reverse=True)
    s=0
    ans=0
    for i in card:
        if s+i<K:
            s+=i
            ans+=1
        else:
            ans=0
    return ans
print(card(n,k,a))

Solution (Python):
def main():
    import numpy as np
    from bisect import bisect_left as bl
    mod = 10**9+7
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    dp = np.zeros(k, dtype=np.int32)
    dp[0] = 1
    m = bl(a, k)
    for i in range(m):
        aa = a[i]
        dp[aa:] = (dp[aa:]+dp[:k-aa]) % mod

    def b_search(ok, ng):
        while abs(ok-ng) > 1:
            mid = (ok+ng)//2
            if value(mid):
                ok = mid
            else:
                ng = mid
        return ok

    def value(i):
        if i == -1:
            return True
        if i == m:
            return False
        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
        for j in range(k-aa, k):
            if dp2[j] != 0:
                return False
        return True
    print(b_search(-1, m)+1)


main()