Problem p03780 (python)

Fixed submission:
def main():
    N, K = map(int, input().split())
    A = [0] + list(map(int, input().split()))
    
    rdp_shift = [N + 1] * K  # rdp_shift[j] = (右からi個を使って部分和jを作れるような最初のi)
    rdp_shift[0] = 0
    rdp = [0] * K  # rdp[i][j] = (a(-1),...,a(-i)の部分和でjを作れるか)
    rdp[0] = 1
    for i in range(N):
        rdp2 = [0] * K
        for j in range(K):
            if rdp[j] == 1:
                rdp2[j] = 1
            elif (j >= A[-i] and rdp[j - A[-i]] == 1):
                # print(j - A[i])
                rdp2[j] = 1
                rdp_shift[j] = i
                # print(rdp_shift)
        rdp = rdp2
    # print(rdp_shift)
    ldp = [0] * K  # ldp[i][j] = (a1,...,aiの部分和でjを作れるか)
    ldp[0] = 1
    S = [0] * (K + 1)
    ans = 0
    for i in range(1, N + 1):
        # ここで一つ一つチェックしている！！
        # A[i]が不要かチェック
        for j in range(K):
            S[j + 1] = S[j]
            # print(N - i, rdp_shift[j])
            if rdp_shift[j] <= N - i:
                S[j + 1] += 1
        no_need = True
        for lval in range(K):
            if ldp[lval] == 0:
                continue
            # print(K - A[i] - lval)
            rval = S[K - lval] - S[max(0, K - A[i] - lval)]
            # print(S, K - lval, K - A[i] - lval, rval)
            if rval > 0:
                no_need = False
                break
        if no_need:
            ans += 1

        # ldp[i][:]の計算
        ldp2 = [0] * K
        for j in range(K):
            if ldp[j] == 1 or (j >= A[i] and ldp[j - A[i]] == 1):
                ldp2[j] = 1
        ldp = ldp2
    print(ans)
    # print(S)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
def main():
    N, K = map(int, input().split())
    A = [0] + list(map(int, input().split()))

    rdp_shift = [N + 1] * K  # rdp_shift[j] = (右からi個を使って部分和jを作れるような最初のi)
    rdp_shift[0] = 0
    rdp = [0] * K  # rdp[i][j] = (a(-1),...,a(-i)の部分和でjを作れるか)
    rdp[0] = 1
    for i in range(N):
        rdp2 = [0] * K
        for j in range(K):
            if rdp[j] == 1:
                rdp2[j] = 1
            elif (j >= A[-i] and rdp[j - A[-i]] == 1):
                # print(j - A[i])
                rdp2[j] = 1
                rdp_shift[j] = i
                # print(rdp_shift)
        rdp = rdp2
    # print(rdp_shift)
    ldp = [0] * K  # ldp[i][j] = (a1,...,aiの部分和でjを作れるか)
    ldp[0] = 1
    S = [0] * (K + 1)
    ans = 0
    for i in range(1, N + 1):
        # ここで一つ一つチェックしている！！
        # A[i]が不要かチェック
        for j in range(K):
            S[j + 1] = S[j]
            # print(N - i, rdp_shift[j])
            if rdp_shift[j] <= N - i:
                print(S, rdp_shift, j, N - i, A[i])
                S[j + 1] += 1
        no_need = True
        for lval in range(K):
            if ldp[lval] == 0:
                continue
            # print(K - A[i] - lval)
            rval = S[K - lval] - S[max(0, K - A[i] - lval)]
            # print(S, K - lval, K - A[i] - lval, rval)
            if rval > 0:
                no_need = False
                break
        if no_need:
            ans += 1

        # ldp[i][:]の計算
        ldp2 = [0] * K
        for j in range(K):
            if ldp[j] == 1 or (j >= A[i] and ldp[j - A[i]] == 1):
                ldp2[j] = 1
        ldp = ldp2
    print(ans)
    # print(S)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
N, K = map(int, input().split())
A = sorted(map(int, input().split()))

sum_A = sum(A)
if sum_A < K:
    print(len(A))
    exit()
elif sum_A == K:
    print(0)
    exit()

dp = [[False] * len(A) for i in range(len(A))]
sum_A_list = []
for i in range(N):
    if i == 0:
        sum_A_list.append(A[i])
        continue

    sum_A_list.append(sum_A_list[i - 1] + A[i])

idx = 0
for i in range(N - 1, -1, -1):
    if sum_A_list[i] < K:
        idx = i
        break

for i in range(idx + 1):
    if sum_A_list[idx + 1] - sum_A_list[i] >= K:
        continue
    else:
        idx = i - 1
        break

print(idx + 1)