Problem p03782 (python)

Fixed submission:
import bisect


def solve(k, aaa):
    aaa = aaa[:bisect.bisect_left(aaa, k)]

    dp = [False] * k
    dp[0] = True
    curr_max = 0
    ans = len(aaa)
    for i, a in reversed(list(enumerate(aaa))):
        if curr_max + a >= k:
            ans = i
        f = True
        for j in range(min(curr_max, k - a - 1), -1, -1):
            if dp[j]:
                dp[j + a] = True
                if f:
                    curr_max = max(curr_max, j + a)
                    f = False
    return ans


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

print(solve(k, aaa))

Buggy submission (verdict: Runtime Error):
import bisect


def preliminary(k, aaa):
    dp = [False] * k
    dp[0] = True
    curr_max = 0
    fwd = {}
    pa = aaa[0]
    pdp, ppdp = dp[:], None
    for a in aaa:
        if pa != a:
            fwd[pa] = ppdp
        for i in range(min(curr_max, k - a - 1), -1, -1):
            if dp[i]:
                dp[i + a] = True
        curr_max += a
        pa = a
        ppdp = pdp
        pdp = dp[:]
    fwd[pa] = ppdp

    dp = [False] * k
    dp[0] = True
    curr_max = 0
    bwd = {}
    pa = 0
    pdp = []
    for a in reversed(aaa):
        if pa != a:
            bwd[a] = [i for i, v in enumerate(pdp) if v][1:]
        for i in range(min(curr_max, k - a - 1), -1, -1):
            if dp[i]:
                dp[i + a] = True
        curr_max += a
        pa = a
        pdp = dp[:]

    return fwd, bwd


def get_judge(k, aaa):
    fwd, bwd = preliminary(k, aaa)
    cache = [None] * k

    def judge(m):
        am = aaa[m]
        if cache[am] is None:
            dp = fwd[am]
            ndp = dp[:]
            for i in bwd[am]:
                for j in range(k - i - 1, -1, -1):
                    if dp[j]:
                        ndp[i + j] = True
            cache[am] = any(ndp[-am:])
        return cache[am]

    return judge


def solve(k, aaa):
    if sum(aaa) < k:
        return n

    aaa.sort()
    aaa = aaa[:bisect.bisect_left(aaa, k)]

    judge = get_judge(k, aaa)

    l = 0
    r = len(aaa) - 1
    m = (l + r) // 2
    while l <= r:
        if judge(m):
            r = m - 1
        else:
            l = m + 1
        m = (l + r) // 2

    return l


n, k = map(int, input().split())
aaa = list(map(int, input().split()))
print(solve(k, aaa))

Buggy submission (verdict: Runtime Error):
import bisect


def preliminary(k, aaa):
    dp = [False] * k
    dp[0] = True
    curr_max = 0
    fwd = []
    for a in aaa:
        for i in range(min(curr_max, k - a - 1), -1, -1):
            if dp[i]:
                dp[i + a] = True
        fwd.append(dp.copy())
        curr_max += a

    dp = [False] * k
    dp[0] = True
    curr_max = 0
    bwd = []
    for a in reversed(aaa):
        for i in range(min(curr_max, k - a - 1), -1, -1):
            if dp[i]:
                dp[i + a] = True
        bwd.append([i for i, v in enumerate(dp) if v][1:])
        curr_max += a
    bwd.reverse()

    dummy = [False] * k
    dummy[0] = True
    fwd.append(dummy)
    bwd.append([])

    return fwd, bwd


def get_judge(k, aaa):
    fwd, bwd = preliminary(k, aaa)
    cache = [None] * k

    def judge(m):
        am = aaa[m]
        if cache[am] is None:
            dp = fwd[m - 1]
            for i in bwd[m + 1]:
                for j in range(k - i - 1, -1, -1):
                    if dp[j]:
                        dp[i + j] = True
            cache[am] = any(dp[-am:])
        return cache[am]

    return judge


def solve(k, aaa):
    if sum(aaa) < k:
        return n

    aaa.sort()
    aaa = aaa[:bisect.bisect_left(aaa, k)]
    judge = get_judge(k, aaa)

    l = 0
    r = len(aaa) - 1
    m = (l + r) // 2
    while l <= r:
        if judge(m):
            r = m - 1
        else:
            l = m + 1
        m = (l + r) // 2

    return l


n, k = map(int, input().split())
aaa = list(map(int, input().split()))
print(solve(k, aaa))

Buggy submission (verdict: Runtime Error):
import bisect


def preliminary(k, aaa):
    dp = [False] * k
    dp[0] = True
    curr_max = 0
    fwd = []
    for a in aaa:
        for i in range(min(curr_max, k - a - 1), -1, -1):
            if dp[i]:
                dp[i + a] = True
        fwd.append(dp.copy())
        curr_max += a

    dp = [False] * k
    dp[0] = True
    curr_max = 0
    bwd = []
    for a in reversed(aaa):
        for i in range(min(curr_max, k - a - 1), -1, -1):
            if dp[i]:
                dp[i + a] = True
        bwd.append([i for i, v in enumerate(dp) if v][1:])
        curr_max += a
    bwd.reverse()

    dummy = [False] * k
    dummy[0] = True
    fwd.append(dummy)
    bwd.append([])

    return fwd, bwd


def get_judge(k, aaa):
    fwd, bwd = preliminary(k, aaa)
    cache = [None] * k

    def judge(m):
        am = aaa[m]
        if cache[am] is None:
            dp = fwd[m - 1]
            for i in bwd[m + 1]:
                for j in range(k - i - 1, -1, -1):
                    if dp[j]:
                        dp[i + j] = True
            cache[am] = any(dp[-am:])
        return cache[am]

    return judge


def solve(k, aaa):
    aaa.sort()
    uk = bisect.bisect_left(aaa, k)
    aaa = aaa[:uk]

    judge = get_judge(k, aaa)

    l = 0
    r = len(aaa) - 1
    m = (l + r) // 2
    while l <= r:
        if judge(m):
            r = m - 1
        else:
            l = m + 1
        m = (l + r) // 2

    return l


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

# n = 5000
# k = 5000
# aaa = list(range(1, n + 1))

print(solve(k, aaa))

Buggy submission (verdict: Runtime Error):
import bisect

import numpy as np
from scipy.ndimage.interpolation import shift


def preliminary(k, aaa):
    dp = np.zeros(k, np.uint8)
    dp[0] = 1
    fwd = []
    for a in aaa:
        dp |= shift(dp, a)
        fwd.append(dp.copy())

    dp = np.zeros(k, np.uint8)
    dp[0] = 1
    bwd = []
    for a in reversed(aaa):
        dp |= shift(dp, a)
        bwd.append(np.where(dp)[0])
    bwd.reverse()

    fwd.append(np.zeros(k, np.uint8))
    bwd.append([0])

    return fwd, bwd


def solve(k, aaa):
    aaa.sort()
    uk = bisect.bisect_left(aaa, k)
    aaa = aaa[:uk]

    fwd, bwd = preliminary(k, aaa)

    l = 0
    r = len(aaa) - 1
    m = (l + r) // 2
    while l <= r:
        dp = fwd[m - 1]
        for i in bwd[m + 1][1:]:
            dp |= shift(dp, i)
        if dp[-aaa[m]:].any():
            r = m - 1
        else:
            l = m + 1
        m = (l + r) // 2

    return l


n, k = map(int, input().split())
aaa = list(map(int, input().split()))
print(solve(k, aaa))

Buggy submission (verdict: Runtime Error):
import bisect
import numpy as np
from scipy.ndimage.interpolation import shift


def judge(e):
    ae = aaa[e]
    dp = np.zeros(k, np.uint8)
    dp[0] = 1
    for i, a in enumerate(aaa):
        if i == e:
            continue
        dp |= shift(dp, a)
    return dp[-ae:].any()


def solve(k, aaa):
    l = 0
    r = bisect.bisect_left(aaa, k) - 1
    m = (l + r) // 2
    while l <= r:
        if judge(m):
            r = m - 1
        else:
            l = m + 1
        m = (l + r) // 2

    return l


n, k = map(int, input().split())
aaa = list(map(int, input().split()))
aaa.sort()
print(solve(k, aaa))