Submission #1610216

---

Source Code Expand

N,K = map(int,input().split())
src = list(map(int,input().split()))
src.sort(reverse=True)

def need(idx):
    a = src[idx]
    dp = [0 for i in range(K+1)]
    dp[0] = 1
    for i in range(N):
        if i == idx: continue
        b = src[i]
        for v, canmake in enumerate(list(dp)):
            if not canmake: continue
            if v+b < K-a:
                dp[v+b] = 1
            elif v+b < K:
                return True
    return False

l = 0
r = N
while r-l > 0:
    m = (l+r)//2
    if need(m):
        l = m+1
    else:
        r = m
print(N - l)

Submission Info

Judge Result