Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import os
import string
import sys
from collections import Counter
from functools import lru_cache

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


S = sys.stdin.buffer.readline().decode().rstrip()
N = len(S)

lefts = [{c: 0 for c in string.ascii_lowercase} for _ in range(N)]
rights = [{c: 0 for c in string.ascii_lowercase} for _ in range(N)]
for i in range(1, N):
    for c in string.ascii_lowercase:
        lefts[i][c] = lefts[i - 1][c]
    lefts[i][S[i - 1]] += 1
for i in reversed(range(N - 1)):
    for c in string.ascii_lowercase:
        rights[i][c] = rights[i + 1][c]
    rights[i][S[i + 1]] += 1
total = Counter(S)


def dump(counter):
    for c in sorted(counter.keys()):
        if counter[c] > 0:
            print(c, counter[c])
    print()


@lru_cache(maxsize=None)
def count_palindrome(l, r):
    if r <= l:
        assert False
    if l + 1 == r:
        return 1
    counts = total.copy()
    for c in string.ascii_lowercase:
        counts[c] -= lefts[l][c]
        counts[c] -= rights[r - 1][c]
    odds = 0
    for c in counts.values():
        odds += c % 2
    if odds <= 1:
        return 1

    ret = INF
    for i in range(l + 1, r):
        # i で split するときの両側の数
        cnt = count_palindrome(l, i) + count_palindrome(i, r)
        ret = min(cnt, ret)
    return ret


ans = count_palindrome(0, N)
print(ans)


Fixed submission:
import os
import sys
from collections import defaultdict

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


# 解説
S = sys.stdin.buffer.readline().decode().rstrip()
N = len(S)

cs = [0] * N
h = 0
for i, c in enumerate(S):
    h ^= 1 << (ord(c) - ord('a'))
    cs[i] = h


def dump(h):
    import numpy as np
    print(np.binary_repr(h, 26))


def dumpdp(dp):
    for k in dp.keys():
        if dp[k] < INF:
            dump(k)
            print(dp[k])
    print()


# dp[h]: それまでのハッシュが h である位置以前の分割方法の最小値
dp = defaultdict(lambda: INF)
dp[0] = 0
dp[cs[0]] = 1
for i in range(1, N):
    # print(S[i - 1])
    # dumpdp(dp)

    h = cs[i]
    if h == 0:
        continue
    d = 1
    while d < (1 << 26):
        # i から h^d の位置までまとめて 1 つ切り出せる
        dp[h] = min(dp[h], dp[h ^ d] + 1)
        d <<= 1

if cs[-1] == 0:
    print(1)
else:
    print(dp[cs[-1]])
Buggy python submission (verdict: Time Limit Exceeded):
import itertools
import sys

import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')

N, K = list(map(int, input().split()))
XY = np.array([list(map(int, input().split())) for _ in range(N)])

X = XY[:, 0]
Y = XY[:, 1]
X = X[Y.argsort()]
Y = Y[Y.argsort()]

ans = INF
for xi, xj in itertools.combinations(range(N), r=2):
    L, r = min(X[xi], X[xj]), max(X[xi], X[xj])
    xconds = (L <= X) & (X <= r)

    yi = 0
    yj = 1
    while yj < N:
        b, u = min(Y[yi], Y[yj]), max(Y[yi], Y[yj])
        count = np.sum(xconds & (b <= Y) & (Y <= u))
        if count >= K:
            ans = min(ans, (r - L) * (u - b))
            yi += 1
        else:
            yj += 1
        if yi == yj:
            yj += 1
print(ans)


Fixed submission:
import itertools
import sys

import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')

N, K = list(map(int, next(sys.stdin).split()))
XY = np.array([list(map(int, next(sys.stdin).split())) for _ in range(N)])

X = XY[:, 0]
Y = XY[:, 1]
X = X[Y.argsort()]
Y = Y[Y.argsort()]

ans = INF
for xi, xj in itertools.combinations(range(N), r=2):
    L, r = min(X[xi], X[xj]), max(X[xi], X[xj])
    xconds = (L <= X) & (X <= r)

    yi = 0
    yj = 1
    while yj < N:
        if np.sum(xconds[yi:yj + 1]) >= K:
            b, u = min(Y[yi], Y[yj]), max(Y[yi], Y[yj])
            ans = min(ans, (r - L) * (u - b))
            yi += 1
        else:
            yj += 1
        if yi == yj:
            yj += 1
print(ans)

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

import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')

N, K = list(map(int, input().split()))
XY = np.array([list(map(int, input().split())) for _ in range(N)])
X = XY[:, 0]
Y = XY[:, 1]

ans = INF
for xi, xj in itertools.combinations(range(N), r=2):
    for yi, yj in itertools.combinations(range(N), r=2):
        L, r = min(X[xi], X[xj]), max(X[xi], X[xj])
        b, u = min(Y[yi], Y[yj]), max(Y[yi], Y[yj])
        count = np.sum((L <= X) & (X <= r) & (b <= Y) & (Y <= u))
        if count >= K:
            ans = min(ans, (r - L) * (u - b))
print(ans)


Fixed submission:
import itertools
import sys

import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')

N, K = list(map(int, next(sys.stdin).split()))
XY = np.array([list(map(int, next(sys.stdin).split())) for _ in range(N)])

X = XY[:, 0]
Y = XY[:, 1]
X = X[Y.argsort()]
Y = Y[Y.argsort()]

ans = INF
for xi, xj in itertools.combinations(range(N), r=2):
    L, r = min(X[xi], X[xj]), max(X[xi], X[xj])
    xconds = (L <= X) & (X <= r)

    yi = 0
    yj = 1
    while yj < N:
        if np.sum(xconds[yi:yj + 1]) >= K:
            b, u = min(Y[yi], Y[yj]), max(Y[yi], Y[yj])
            ans = min(ans, (r - L) * (u - b))
            yi += 1
        else:
            yj += 1
        if yi == yj:
            yj += 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import itertools
import sys

import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')

N = int(sys.stdin.readline())
A = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

A = np.array(A)


def solve():
    # 消していいやつ
    useless = np.zeros((N, N), dtype=bool)

    # 1 つ経由するのだけ考えれば OK
    for st, en in itertools.combinations(range(N), r=2):
        for via in range(N):
            if via in [st, en]:
                continue
            if A[st, via] + A[via, en] < A[st, en]:
                return -1
            if A[st, via] + A[via, en] == A[st, en]:
                useless[st, en] = True
                useless[en, st] = True

    return A[~useless].sum() // 2


print(solve())


Fixed submission:
import sys

import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')

N = int(sys.stdin.readline())
A = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

A = np.array(A, dtype=float)

useless = np.zeros((N, N), dtype=bool)
impossible = np.zeros((N, N), dtype=bool)
for via in range(N):
    # R[i][j]: i -> via -> j の距離
    R = sum(np.meshgrid(A[via], A[via]))
    R[via] = np.inf
    R[:, via] = np.inf
    useless |= R == A
    impossible |= R < A
if impossible.sum():
    print(-1)
else:
    print(int(A[~useless].sum() // 2))
Buggy python submission (verdict: Runtime Error):
import bisect
from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
import numpy as np
import re
import sys

sys.setrecursionlimit(10000)
INF = float('inf')

N = int(sys.stdin.readline())
P = list(map(int, sys.stdin.readline().split()))
P.insert(0, -1)

ans = 0
for i in range(len(P)):
    if i == P[i]:
        if i + 1 < len(P):
            P[i], P[i + 1] = P[i + 1], P[i]
        ans += 1
print(ans)


Fixed submission:
import sys

sys.setrecursionlimit(10000)
INF = float('inf')

N = int(sys.stdin.readline())
P = list(map(int, sys.stdin.readline().split()))
P.insert(0, -1)

ans = 0
for i in range(len(P)):
    if i == P[i]:
        if i + 1 < len(P):
            P[i], P[i + 1] = P[i + 1], P[i]
        ans += 1
print(ans)
Buggy python submission (verdict: Runtime Error):
import os
import sys
from collections import Counter

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = list(map(int, sys.stdin.readline().split()))
A = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

A = np.array(A, dtype=int)
idx = np.zeros(N, dtype=int)
used = np.zeros(M + 1, dtype=bool)

ans = INF
for _ in range(N):
    k, cnt = Counter(A[np.arange(N), idx]).most_common(1)[0]
    ans = min(ans, cnt)
    used[k] = True
    for i in range(N):
        while idx[i] < M and used[A[i, idx[i]]]:
            idx[i] += 1
print(ans)


Fixed submission:
import os
import sys
from collections import Counter

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = list(map(int, sys.stdin.readline().split()))
A = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

A = np.array(A, dtype=int)
idx = np.zeros(N, dtype=int)
used = np.zeros(M + 1, dtype=bool)

ans = INF
for _ in range(M):
    k, cnt = Counter(A[np.arange(N), idx]).most_common(1)[0]
    ans = min(ans, cnt)
    used[k] = True
    for i in range(N):
        while idx[i] < M and used[A[i, idx[i]]]:
            idx[i] += 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import bisect
import os
from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
import numpy as np
import re
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N = int(sys.stdin.readline())
X, Y = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(N)]))

X = np.array(X)
Y = np.array(Y)
fixed = np.zeros(N, dtype=bool)
fixed[0] = True
cnt = 1
ans = 0

# プリム法 くっつけてく
heap = list(zip(np.minimum(abs(X - X[0]), abs(Y - Y[0])), range(N)))[1:]
heapq.heapify(heap)
while cnt < N:
    dist, v = heapq.heappop(heap)
    if fixed[v]:
        continue
    fixed[v] = True
    ans += dist

    for du in zip(np.minimum(abs(X[~fixed] - X[v]), abs(Y[~fixed] - Y[v])), np.where(~fixed)[0]):
        heapq.heappush(heap, du)
    cnt += 1
print(ans)


Fixed submission:
import bisect
import os
from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
import numpy as np
import re
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N = int(sys.stdin.readline())
X, Y = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(N)]))

X = np.array(X)
Y = np.array(Y)
Xargs = X.argsort()
Yargs = Y.argsort()

# X 座標上または Y 座標上で隣り合わないやつは隣り合うやつをたどっていけるので考えなくていい
graph = [[] for _ in range(N)]
for v, u in zip(Xargs[:-1], Xargs[1:]):
    graph[v].append((abs(X[v] - X[u]), u))
    graph[u].append((abs(X[v] - X[u]), v))
for v, u in zip(Yargs[:-1], Yargs[1:]):
    graph[v].append((abs(Y[v] - Y[u]), u))
    graph[u].append((abs(Y[v] - Y[u]), v))

heap = graph[0]
heapq.heapify(heap)
fixed = np.zeros(N, dtype=bool)
fixed[0] = True

cnt = 1
ans = 0
while cnt < N:
    dist, v = heapq.heappop(heap)
    if fixed[v]:
        continue
    fixed[v] = True
    cnt += 1
    ans += dist
    for d, u in graph[v]:
        if fixed[u]:
            continue
        heapq.heappush(heap, (d, u))

print(ans)
Buggy python submission (verdict: Runtime Error):
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

H, W, A, B = list(map(int, sys.stdin.readline().split()))
if H % A == 0 and W % B == 0:
    print('No')
    exit()

print('Yes')
MAX = 998244353
ans = np.full((H, W), MAX // (A * B - 1), dtype=int)
if A > 1 and B > 1:
    ans[np.arange(A - 1, H, A), np.arange(B - 1, W, B)] = -MAX
elif A == 1:
    ans[:, np.arange(B - 1, W, B)] = -MAX
else:
    ans[np.arange(A - 1, H, A), :] = -MAX
print('\n'.join(map(lambda r: ' '.join(r), ans.astype(str))))


Fixed submission:
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

H, W, A, B = list(map(int, sys.stdin.readline().split()))
if H % A == 0 and W % B == 0:
    print('No')
    exit()

print('Yes')
MAX = 998244353
ans = np.full((H, W), MAX // (A * B - 1), dtype=int)
if A > 1 and B > 1:
    ans[np.meshgrid(np.arange(A - 1, H, A), np.arange(B - 1, W, B))] = -MAX-1
elif A == 1:
    ans[:, np.arange(B - 1, W, B)] = -MAX-1
else:
    ans[np.arange(A - 1, H, A), :] = -MAX-1
print('\n'.join(map(lambda r: ' '.join(r), ans.astype(str))))

Buggy python submission (verdict: Runtime Error):
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

H, W, A, B = list(map(int, sys.stdin.readline().split()))
if H % A == 0 and W % B == 0:
    print('No')
    exit()

print('Yes')
ans = np.ones((H, W), dtype=int)
ans[np.arange(A - 1, H, A), np.arange(B - 1, W, B)] = - A * B
print('\n'.join(map(lambda r: ' '.join(r), ans.astype(str))))


Fixed submission:
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

H, W, A, B = list(map(int, sys.stdin.readline().split()))
if H % A == 0 and W % B == 0:
    print('No')
    exit()

print('Yes')
MAX = 998244353
ans = np.full((H, W), MAX // (A * B - 1), dtype=int)
if A > 1 and B > 1:
    ans[np.meshgrid(np.arange(A - 1, H, A), np.arange(B - 1, W, B))] = -MAX-1
elif A == 1:
    ans[:, np.arange(B - 1, W, B)] = -MAX-1
else:
    ans[np.arange(A - 1, H, A), :] = -MAX-1
print('\n'.join(map(lambda r: ' '.join(r), ans.astype(str))))
Buggy python submission (verdict: Runtime Error):
import bisect
import os
from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
import numpy as np
import re
import string
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N, M = list(map(int, sys.stdin.readline().split()))
ABC = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]

graph = [[] for _ in range(N + 1)]

for a, b, c in ABC:
    graph[b].append((a, c))


@lru_cache(maxsize=None)
def solve(n):
    # 1 から n までの最長距離
    ret = -INF
    for prev, c in graph[n]:
        ret = max(ret, solve(prev) + c)
    if n == 1:
        return 0
    return ret


try:
    print(solve(N))
except:
    print('inf')


Fixed submission:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N, M = list(map(int, sys.stdin.readline().split()))
ABC = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]
sys.setrecursionlimit(200000)

graph = [[] for _ in range(N + 1)]

for a, b, c in ABC:
    graph[b].append((a, c))
graph[1].append((0, 0))

vd = [(N, 0)]
# N までの最長距離
ans = [-INF] * (N + 1)
ans[N] = 0
for _ in range(N + 1):
    nexts = []
    for v, d in vd:
        for u, c in graph[v]:
            if ans[u] < d + c:
                ans[u] = d + c
                nexts.append((u, d + c))
    vd = nexts
if vd:
    print('inf')
else:
    print(ans[0])
Buggy python submission (verdict: Runtime Error):
import bisect
import os
from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
import numpy as np
import re
import sys
import string

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

#
# A, B, C = list(map(int, sys.stdin.readline().split()))
# a = A
# ok = False
# for _ in range(1000):
#     ok |= a % B == C
#     a += A
# if ok:
#     print('YES')
# else:
#     print('NO')
#
#
# A, B = [int(sys.stdin.readline()) for _ in range(2)]
# if A>B:
#     print('GREATER')
# elif A<B:
#     print('LESS')
# else:
#     print('EQUAL')


O, E = [sys.stdin.readline().rstrip() for _ in range(2)]
ans = ''
for i in range(len(O)):
    ans += O[i]
    ans += E[i]

print(ans)


Fixed submission:
import bisect
import os
from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
import numpy as np
import re
import sys
import string

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")


import bisect
import os
from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
import numpy as np
import re
import sys
import string

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

#
# A, B, C = list(map(int, sys.stdin.readline().split()))
# a = A
# ok = False
# for _ in range(1000):
#     ok |= a % B == C
#     a += A
# if ok:
#     print('YES')
# else:
#     print('NO')
#
#
# A, B = [int(sys.stdin.readline()) for _ in range(2)]
# if A>B:
#     print('GREATER')
# elif A<B:
#     print('LESS')
# else:
#     print('EQUAL')


O, E = [sys.stdin.readline().rstrip() for _ in range(2)]
ans = ''
for i in range(len(O)):
    ans += O[i]
    if i < len(E):
        ans += E[i]

print(ans)



#
# N, M = list(map(int, sys.stdin.readline().split()))
# A, B = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(N)]))
# C, D = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(M)]))
#
# O, E = [sys.stdin.readline().rstrip() for _ in range(2)]
# ans = ''
# for i in range(len(O)):
#     ans += O[i]
#     ans += E[i]
#
# print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

MOD = 10 ** 9 + 7

N, M = list(map(int, sys.stdin.readline().split()))
X = list(map(int, sys.stdin.readline().split()))
Y = list(map(int, sys.stdin.readline().split()))


def ModInt(mod):
    class _ModInt:
        def __init__(self, value):
            self.value = value % mod

        def __add__(self, other):
            return _ModInt(self.value + other.value)

        def __mul__(self, other):
            return _ModInt(self.value * other.value)

        def __repr__(self):
            return str(self.value)

    return _ModInt


MI = ModInt(MOD)
X = np.diff(X)
Y = np.diff(Y)
X = np.array([MI(x) for x in X])
Y = np.array([MI(y) for y in Y])

#  あるエリアが何回カウントされるか
xc = np.cumsum([MI(x) for x in range(len(X), -len(X), -2)])
yc = np.cumsum([MI(y) for y in range(len(Y), -len(Y), -2)])

print(np.dot(X, xc) * np.dot(Y, yc))


Fixed submission:
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

MOD = 10 ** 9 + 7

N, M = list(map(int, sys.stdin.readline().split()))
X = list(map(int, sys.stdin.readline().split()))
Y = list(map(int, sys.stdin.readline().split()))


def ModInt(mod):
    class _ModInt:
        def __init__(self, value):
            self.value = value % mod

        def __add__(self, other):
            if isinstance(other, _ModInt):
                return _ModInt(self.value + other.value)
            else:
                return _ModInt(self.value + other)

        def __radd__(self, other):
            return self.__add__(other)

        def __mul__(self, other):
            if isinstance(other, _ModInt):
                return _ModInt(self.value * other.value)
            else:
                return _ModInt(self.value * other)

        def __truediv__(self, other):
            # TODO: 実装
            raise NotImplementedError()

        def __repr__(self):
            return str(self.value)

    return _ModInt


MI = ModInt(MOD)
X = np.diff(X)
Y = np.diff(Y)
X = np.array([MI(x) for x in X])
Y = np.array([MI(y) for y in Y])

#  あるエリアが何回カウントされるか
xc = np.arange(len(X), -len(X), -2).cumsum()
yc = np.arange(len(Y), -len(Y), -2).cumsum()

print(np.dot(X, xc) * np.dot(Y, yc))
Buggy python submission (verdict: Time Limit Exceeded):
import bisect
import heapq
import itertools
import math
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N, K = list(map(int, sys.stdin.readline().split()))
A = list(map(int, sys.stdin.readline().split()))


def is_necessary(ai):
    # A[ai] が必要かどうか
    # A[ai] を使わずに K-A[ai] 以上 K 未満を作れるか

    # dp[j]: j を作れる
    dp = np.zeros(K, dtype=bool)
    dp[0] = 1
    for i, a in enumerate(A):
        if i == ai:
            continue
        dp[a:] = dp[a:] | dp[:-a]
    return any(dp[K - A[ai]:])


ans = N
for i, a in enumerate(A):
    ans -= is_necessary(i)
print(ans)


Fixed submission:
import bisect
import heapq
import itertools
import math
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N, K = list(map(int, sys.stdin.readline().split()))
A = list(map(int, sys.stdin.readline().split()))


def bisect_left_callable(fn, x, lo, hi):
    """
    (memo) いっぱい呼ぶなら np.searchsorted のほうがベクトル化されててはやそう
    lo から hi-1 のうち、fn の結果が x 以上となる、最も左の値
    bisect.bisect_left と同じ
    https://docs.python.org/ja/3/library/bisect.html
    :param callable fn:
    :param x:
    :param int lo: 最小値
    :param int hi: 最大値 + 1
    :return: lo <= ret <= hi
    """
    while lo < hi:
        mid = (lo + hi) // 2
        if fn(mid) < x:
            lo = mid + 1
        else:
            hi = mid
    return lo


def is_necessary(ai):
    # A[ai] が必要かどうか
    # A[ai] を使わずに K-A[ai] 以上 K 未満を作れるか

    # dp[j]: j を作れる
    dp = np.zeros(K, dtype=bool)
    dp[0] = 1
    for i, a in enumerate(A):
        if i == ai:
            continue
        dp[a:] = dp[a:] | dp[:-a]
    return any(dp[K - A[ai]:])


A.sort()
unnecessary = bisect_left_callable(is_necessary, 1, lo=0, hi=N)
print(unnecessary)
Buggy python submission (verdict: Time Limit Exceeded):
import bisect
import heapq
import itertools
import math
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

K, S = list(map(int, sys.stdin.readline().split()))

a = np.array(list(itertools.product(range(K + 1), repeat=2)))
s = a.sum(axis=1)
print(((S - K <= s) & (s <= S)).sum())


Fixed submission:
import bisect
import os
from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
import numpy as np
import re
import string
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

K, S = list(map(int, sys.stdin.readline().split()))

ans = 0
for x in range(K + 1):
    yz = S - x
    if yz < 0 or 2 * K < yz:
        continue
    ans += yz + 1
    ans -= max(0, yz - K) * 2
print(ans)