Problem p03780 (python)

Fixed submission:
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)

Buggy submission (verdict: Runtime Error):
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)

Buggy submission (verdict: Runtime Error):
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)

Buggy submission (verdict: Runtime Error):
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)

Buggy submission (verdict: Runtime Error):
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)

Buggy submission (verdict: Runtime Error):
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)