Problem p03780 (python)

Fixed submission:
import bisect
def main():
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    a.sort()
    l=0
    r=n
    d = {}
    if sum(a)<k:
        print(n)
    else:
        while l!=r:
            i=(l+r)//2
            ta = a[i]
            if ta in d.keys():
                flag = d[ta]
            elif ta>=k:flag=True
            else:
                flag = False
                na = a[:i]+a[i+1:]
                dp = [False for _ in range(k+1)]
                dp[0]=True
                for j in range(n-1):
                    for m in range(k,0,-1):
                        if m-na[j]>=0:
                            dp[m]=dp[m] or dp[m-na[j]]
                        if m != k and m>=k-ta and dp[m]:
                            flag = True
                            break
                    if flag:break
                d[ta] = flag
            
            if flag:
                r=i
            else:
                l=i+1
        print(l)

main()

Buggy submission (verdict: Runtime Error):
import bisect
def main():
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    a.sort()
    l=0
    r=n
    d = {}
    if sum(a)<k:
        print(n)
    else:
        while l!=r:
            i=(l+r)//2
            ta = a[i]
            if ta in d.values():
                flag = d[ta]
            elif ta>=k:flag=True
            else:
                flag = False
                na = a[:i]+a[i+1:]
                dp = [False for _ in range(k+1)]
                dp[0]=True
                for j in range(n-1):
                    for m in range(k,0,-1):
                        if m-na[j]>=0:
                            dp[m]=dp[m] or dp[m-na[j]]
                        if m != k and m>=k-ta and dp[m]:
                            flag = True
                            break
                    if flag:break
                d[ta] = flag
            
            if flag:
                r=i
            else:
                l=i+1
        print(l)

main()

Buggy submission (verdict: Runtime Error):
import bisect
def main():
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    a.sort()
    l=0
    r=n
    if sum(a)<k:
        print(n)
    else:
        while l!=r:
            i=(l+r)//2
            ta = a[i]
            if ta>=k:flag=True
            else:
                na = a[:i]+a[i+1:]
                dp = [False for _ in range(k+1)]
                dp[0]=True
                for j in range(n-1):
                    for m in range(k,0,-1):
                        if m-na[j]>=0:
                            dp[m]=dp[m] or dp[m-na[j]]
                        if m != k and m>=k-ta and dp[m]:
                            flag = True
                            break
                    if flag:break
            if flag:
                r=i
            else:
                l=i+1
        print(l)

main()

Buggy submission (verdict: Runtime Error):
import bisect
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
l=0
r=n
while l!=r:
    i=(l+r)//2
    ta = a[i]
    na = a[:i]+a[i+1:]
    dp = [False for _ in range(k+1)]
    dp[0]=True
    for j in range(n-1):
        for m in range(k,0,-1):
            if m-na[j]>=0:
                dp[m]=dp[m] or dp[m-na[j]]
    flag = False
    for j in range(k-ta,k):
        if dp[j]:
            flag = True
            break
    if flag:
        r=i
    else:
        l=i+1
print(l)

Buggy submission (verdict: Runtime Error):
import bisect
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
fa = a[:bisect.bisect_left(a,k)]
fa.reverse()
nn = len(fa)
for i in range(nn):
    flag = 0
    ta = fa[i]
    na = fa[:i]+fa[i+1:]
    dp = [False for _ in range(k+1)]
    dp[0]=True
    for j in range(nn-1):
        for l in range(k,0,-1):
            if l-na[j]>=0:
                dp[l]=dp[l] or dp[l-na[j]]
    for j in range(k-ta,k):
        if dp[j]:
            flag = 1
            break
    if flag == 0:
        res = i
        break
print(nn-i)