Problem p03780 (python)

Fixed submission:
def main():
    import sys
    from array import array
    input = sys.stdin.readline

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

    dp_left = [array('b', [0] * K) for _ in range(N + 1)]
    dp_right = [array('b', [0] * K) for _ in range(N + 1)]
    dp_left[0][0] = 1
    dp_right[0][0] = 1
    for i, a in enumerate(A):
        for j in range(K):
            if dp_left[i][j]:
                dp_left[i + 1][j] = 1
                if j + a < K:
                    dp_left[i + 1][j + a] = 1
    for i, a in enumerate(reversed(A)):
        for j in range(K):
            if dp_right[i][j]:
                dp_right[i + 1][j] = 1
                if j + a < K:
                    dp_right[i + 1][j + a] = 1

    ok = N
    ng = -1
    mid = (ok+ng)//2
    while ok - ng > 1:
        a = A[mid]
        if a >= K:
            ok = mid
            mid = (ok+ng)//2
            continue
        flg = 0
        l = 0
        r = K-1
        while True:
            if dp_right[N-mid-1][r]:
                break
            r -= 1
        while True:
            if K-a <= l+r < K:
                flg = 1
                break
            elif l+r >= K:
                r -= 1
                if r < 0:
                    break
                while True:
                    if dp_right[N-mid-1][r]:
                        break
                    r -= 1
            else:
                l += 1
                if l >= K:
                    break
                while True:
                    if dp_left[mid][l]:
                        break
                    l += 1
                    if l >= K:
                        break
        if flg:
            ok = mid
        else:
            ng = mid
        mid = (ok+ng)//2
    print(ng+1)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
N, K = map(int, input().split())
a = list(map(int, input().split()))
a.sort()

dp = [[10 ** 11 for _ in range(2*K-1)] for _ in range(N+1)]
for i in range(N+1):
    dp[i][0] = 10 ** 10
for i in range(N):
    for j in range(K):
        if dp[i][j] < 10 ** 10 + 1:
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            if j + a[i] <= 2*(K-1):
                dp[i+1][j+a[i]] = min(dp[i+1][j+a[i]], dp[i][j], a[i])

dp_last = dp[-1][K:]
ans = 0
i = 0
prev = 0
for i in range(N):
    if a[i] == prev:
        i += 1
        ans += 1
        continue
    else:
        prev = a[i]
    ok = 0
    for j in range(a[i]):
        if dp_last[j] <= a[i]:
            ok = 1
            break
    if ok:
        break
    else:
        ans += 1

print(ans)

Buggy submission (verdict: Runtime Error):
def main():
    N, K = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    num = [0] * K
    c = 0
    ok = float('inf')
    for i, ai in enumerate(a):
        if ai >= K:
            a = a[:i]
        else:
            num[ai] += 1
            c += ai
        if c >= K:
            ok = i - num[ai] + 1
    if not a:
        print(0)
        exit()
    n = len(a)
    if ok > n:
        ok = n
    ng = -1
    mid = (ok + ng) // 2
    while ok - ng > 1:
        flg = 0
        dp = [[0 for _ in range(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:
                    if i != mid:
                        if j + a[i] <= K-1:
                            dp[i+1][j+a[i]] = 1
                    dp[i+1][j] = 1
        for i in range(-1, -a[mid]-1, -1):
            if dp[-1][i] == 1:
                flg = 1
                break
        if flg:
            ok = mid
        else:
            ng = mid
        mid = (ok + ng) // 2
    if ng == -1:
        print(0)
        exit()
    print(sum(num[:a[ng]+1]))


if __name__ == '__main__':
    main()