Buggy python submission (verdict: Time Limit Exceeded):
from itertools import accumulate

def main():
    N, K = map(int, input().split())
    As = list(map(int, input().split()))
    
    nonzeros = [1]
    for a in As:
        ndp = nonzeros[-1]
        if a <= K:
            ndp |= (nonzeros[-1] & ((1 << (K-a)) - 1)) << a
        nonzeros.append(ndp)
    dp = [0] * (K+1)
    dp[0] = 1
    acc = list(accumulate(dp)) + [0]
    ans = 0
    for i in range(N, 0, -1):
        a = As[i-1]
        ndp = []
        for j in range(K+1):
            t = dp[j] if j < a else dp[j] + dp[j-a]
            ndp.append(0 if t == 0 else 1)
        dp = ndp
        if a < K:
            nonzero = nonzeros[i-1]
            for y in range(K+1):
                if nonzero & 1:
                    t = K-y-a-1
                    if acc[K-y-1] > acc[t if t >= 0 else -1]:
                        break
                nonzero >>= 1
            else:
                ans += 1
        acc = list(accumulate(dp)) + [0]
    
    print(ans)

main()


Fixed submission:
from itertools import accumulate

def main():
    N, K = map(int, input().split())
    As = list(map(int, input().split()))
    
    nonzeros = [1]
    for a in As:
        ndp = nonzeros[-1]
        if a <= K:
            ndp |= (nonzeros[-1] % (1 << (K-a))) << a
        nonzeros.append(ndp)
    dp = [0] * (K+1)
    dp[0] = 1
    acc = list(accumulate(dp)) + [0]
    ans = 0
    for i in range(N, 0, -1):
        a = As[i-1]
        ndp = []
        for j in range(K+1):
            t = dp[j] if j < a else dp[j] + dp[j-a]
            ndp.append(0 if t == 0 else 1)
        dp = ndp
        if a < K:
            nonzero = nonzeros[i-1]
            for y in range(K+1):
                if nonzero & 1:
                    t = K-y-a-1
                    if acc[K-y-1] > acc[t if t >= 0 else -1]:
                        break
                nonzero >>= 1
            else:
                ans += 1
        acc = list(accumulate(dp)) + [0]
    
    print(ans)

main()

Buggy python submission (verdict: Runtime Error):
from itertools import accumulate
import numpy as np

def main():
    N, K = map(int, input().split())
    As = list(map(int, input().split()))
    
    dp = np.array([0] * (K+1))
    dp[0] = 1
    nonzeros = [np.array([0])]
    for a in As:
        ndp = np.array([0] * (K+1))
        nonzero = []
        for i in range(K+1):
            t = dp[i] if i < a else dp[i] + dp[i-a]
            if t > 0:
                nonzero.append(i)
                ndp[i] = 1
        nonzeros.append(np.array(nonzero))
        dp = ndp
    
    dp = np.array([0] * (K+1))
    dp[0] = 1
    acc = list(accumulate(dp)) + [0]
    ans = 0
    for i in range(N, 0, -1):
        a = As[i-1]
        ndp = np.array([0] * (K+1))
        for j in range(K+1):
            t = dp[j] if j < a else dp[j] + dp[j-a]
            if t > 0:
                ndp[i] = 1
        dp = ndp
        if a < K:
            nonzero = nonzeros[i-1]
            for y in nonzero:
                t = K-y-a-1
                if acc[K-y-1] > acc[t if t >= 0 else -1]:
                    break
            else:
                ans += 1
        acc = list(accumulate(dp)) + [0]
    
    print(ans)

main()


Fixed submission:
from itertools import accumulate

def main():
    N, K = map(int, input().split())
    As = list(map(int, input().split()))
    
    nonzeros = [1]
    for a in As:
        ndp = nonzeros[-1]
        if a <= K:
            ndp |= (nonzeros[-1] % (1 << (K-a))) << a
        nonzeros.append(ndp)
    dp = [0] * (K+1)
    dp[0] = 1
    acc = list(accumulate(dp)) + [0]
    ans = 0
    for i in range(N, 0, -1):
        a = As[i-1]
        ndp = []
        for j in range(K+1):
            t = dp[j] if j < a else dp[j] + dp[j-a]
            ndp.append(0 if t == 0 else 1)
        dp = ndp
        if a < K:
            nonzero = nonzeros[i-1]
            for y in range(K+1):
                if nonzero & 1:
                    t = K-y-a-1
                    if acc[K-y-1] > acc[t if t >= 0 else -1]:
                        break
                nonzero >>= 1
            else:
                ans += 1
        acc = list(accumulate(dp)) + [0]
    
    print(ans)

main()

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import accumulate

def main():
    N, K = map(int, input().split())
    As = list(map(int, input().split()))
    
    dp = [0] * (K+1)
    dp[0] = 1
    nonzeros = [1]
    for a in As:
        ndp = []
        nonzero = 0
        for i in range(K+1):
            t = dp[i] if i < a else dp[i] + dp[i-a]
            if t == 0:
                ndp.append(0)
            else:
                nonzero |= 1 << i
                ndp.append(1)
        nonzeros.append(nonzero)
        dp = ndp
    dp = [0] * (K+1)
    dp[0] = 1
    acc = list(accumulate(dp)) + [0]
    ans = 0
    for i in range(N, 0, -1):
        a = As[i-1]
        ndp = []
        for j in range(K+1):
            t = dp[j] if j < a else dp[j] + dp[j-a]
            ndp.append(0 if t == 0 else 1)
        dp = ndp
        if a < K:
            nonzero = nonzeros[i-1]
            for y in range(K+1):
                if nonzero & 1:
                    t = K-y-a-1
                    if acc[K-y-1] > acc[t if t >= 0 else -1]:
                        break
                nonzero >>= 1
            else:
                ans += 1
        acc = list(accumulate(dp)) + [0]
    
    print(ans)

main()


Fixed submission:
from itertools import accumulate

def main():
    N, K = map(int, input().split())
    As = list(map(int, input().split()))
    
    nonzeros = [1]
    for a in As:
        ndp = nonzeros[-1]
        if a <= K:
            ndp |= (nonzeros[-1] % (1 << (K-a))) << a
        nonzeros.append(ndp)
    dp = [0] * (K+1)
    dp[0] = 1
    acc = list(accumulate(dp)) + [0]
    ans = 0
    for i in range(N, 0, -1):
        a = As[i-1]
        ndp = []
        for j in range(K+1):
            t = dp[j] if j < a else dp[j] + dp[j-a]
            ndp.append(0 if t == 0 else 1)
        dp = ndp
        if a < K:
            nonzero = nonzeros[i-1]
            for y in range(K+1):
                if nonzero & 1:
                    t = K-y-a-1
                    if acc[K-y-1] > acc[t if t >= 0 else -1]:
                        break
                nonzero >>= 1
            else:
                ans += 1
        acc = list(accumulate(dp)) + [0]
    
    print(ans)

main()

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import accumulate

def main():
    N, K = map(int, input().split())
    As = list(map(int, input().split()))
    
    dp = [0] * (K+1)
    dp[0] = 1
    nonzeros = [set([0])]
    for a in As:
        ndp = []
        nonzero = set()
        for i in range(K+1):
            t = dp[i] if i < a else dp[i] + dp[i-a]
            if t == 0:
                ndp.append(0)
            else:
                nonzero.add(i)
                ndp.append(1)
        nonzeros.append(nonzero)
        dp = ndp
    
    dp = [0] * (K+1)
    dp[0] = 1
    accs = [list(accumulate(dp)) + [0]]
    for a in reversed(As):
        ndp = []
        for i in range(K+1):
            t = dp[i] if i < a else dp[i] + dp[i-a]
            ndp.append(0 if t == 0 else 1)
        dp = ndp
        accs.append(list(accumulate(dp)) + [0])
    
    ans = 0
    for i in range(1, N+1):
        a = As[i-1]
        if a >= K:
            continue
        nonzero = nonzeros[i-1]
        acc = accs[N-i]
        for y in nonzero:
            t = K-y-a-1
            if acc[K-y-1] > acc[t if t >= 0 else -1]:
                break
        else:
            ans += 1
    print(ans)

main()


Fixed submission:
from itertools import accumulate

def main():
    N, K = map(int, input().split())
    As = list(map(int, input().split()))
    
    nonzeros = [1]
    for a in As:
        ndp = nonzeros[-1]
        if a <= K:
            ndp |= (nonzeros[-1] % (1 << (K-a))) << a
        nonzeros.append(ndp)
    dp = [0] * (K+1)
    dp[0] = 1
    acc = list(accumulate(dp)) + [0]
    ans = 0
    for i in range(N, 0, -1):
        a = As[i-1]
        ndp = []
        for j in range(K+1):
            t = dp[j] if j < a else dp[j] + dp[j-a]
            ndp.append(0 if t == 0 else 1)
        dp = ndp
        if a < K:
            nonzero = nonzeros[i-1]
            for y in range(K+1):
                if nonzero & 1:
                    t = K-y-a-1
                    if acc[K-y-1] > acc[t if t >= 0 else -1]:
                        break
                nonzero >>= 1
            else:
                ans += 1
        acc = list(accumulate(dp)) + [0]
    
    print(ans)

main()

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import accumulate

def main():
    N, K = map(int, input().split())
    As = list(map(int, input().split()))
    
    dp1 = [[0] * (K+1)]
    dp1[0][0] = 1
    for a in As:
        ndp = []
        pdp = dp1[-1]
        for i in range(K+1):
            ndp.append(pdp[i] if i < a else pdp[i] + pdp[i-a])
        dp1.append(ndp)
    
    dp2 = [[0] * (K+1)]
    dp2[0][0] = 1
    for a in reversed(As):
        ndp = []
        pdp = dp2[-1]
        for i in range(K+1):
            ndp.append(pdp[i] if i < a else pdp[i] + pdp[i-a])
        dp2.append(ndp)
    accs2 = [list(accumulate(dp)) + [0] for dp in dp2]
    
    ans = 0
    for i in range(1, N+1):
        a = As[i-1]
        if a >= K:
            continue
        dp = dp1[i-1]
        acc2 = accs2[N-i]
        for y in range(K+1):
            if dp[y] == 0:
                continue
            t = K-y-a-1
            if acc2[K-y-1] > acc2[t if t >= 0 else -1]:
                break
        else:
            ans += 1
    print(ans)

main()


Fixed submission:
from itertools import accumulate

def main():
    N, K = map(int, input().split())
    As = list(map(int, input().split()))
    
    nonzeros = [1]
    for a in As:
        ndp = nonzeros[-1]
        if a <= K:
            ndp |= (nonzeros[-1] % (1 << (K-a))) << a
        nonzeros.append(ndp)
    dp = [0] * (K+1)
    dp[0] = 1
    acc = list(accumulate(dp)) + [0]
    ans = 0
    for i in range(N, 0, -1):
        a = As[i-1]
        ndp = []
        for j in range(K+1):
            t = dp[j] if j < a else dp[j] + dp[j-a]
            ndp.append(0 if t == 0 else 1)
        dp = ndp
        if a < K:
            nonzero = nonzeros[i-1]
            for y in range(K+1):
                if nonzero & 1:
                    t = K-y-a-1
                    if acc[K-y-1] > acc[t if t >= 0 else -1]:
                        break
                nonzero >>= 1
            else:
                ans += 1
        acc = list(accumulate(dp)) + [0]
    
    print(ans)

main()

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import accumulate
N, K = map(int, input().split())
As = list(map(int, input().split()))

dp1 = [[0] * (K+1)]
dp1[0][0] = 1
for a in As:
    ndp = []
    pdp = dp1[-1]
    for i in range(K+1):
        ndp.append(pdp[i] if i < a else pdp[i] + pdp[i-a])
    dp1.append(ndp)

dp2 = [[0] * (K+1)]
dp2[0][0] = 1
for a in reversed(As):
    ndp = []
    pdp = dp2[-1]
    for i in range(K+1):
        ndp.append(pdp[i] if i < a else pdp[i] + pdp[i-a])
    dp2.append(ndp)
accs2 = [list(accumulate(dp)) + [0] for dp in dp2]

ans = 0
for i in range(1, N+1):
    a = As[i-1]
    if a >= K:
        continue
    dp = dp1[i-1]
    acc2 = accs2[N-i]
    for y in range(K+1):
        if dp[y] == 0:
            continue
        t = K-y-a-1
        if acc2[K-y-1] > acc2[t if t >= 0 else -1]:
            break
    else:
        ans += 1
print(ans)


Fixed submission:
from itertools import accumulate

def main():
    N, K = map(int, input().split())
    As = list(map(int, input().split()))
    
    nonzeros = [1]
    for a in As:
        ndp = nonzeros[-1]
        if a <= K:
            ndp |= (nonzeros[-1] % (1 << (K-a))) << a
        nonzeros.append(ndp)
    dp = [0] * (K+1)
    dp[0] = 1
    acc = list(accumulate(dp)) + [0]
    ans = 0
    for i in range(N, 0, -1):
        a = As[i-1]
        ndp = []
        for j in range(K+1):
            t = dp[j] if j < a else dp[j] + dp[j-a]
            ndp.append(0 if t == 0 else 1)
        dp = ndp
        if a < K:
            nonzero = nonzeros[i-1]
            for y in range(K+1):
                if nonzero & 1:
                    t = K-y-a-1
                    if acc[K-y-1] > acc[t if t >= 0 else -1]:
                        break
                nonzero >>= 1
            else:
                ans += 1
        acc = list(accumulate(dp)) + [0]
    
    print(ans)

main()