Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
from numpy.linalg import solve

N = int(input())
dam = list(map(int, input().split()))

mountains = []

for i in range(N):
    mount = [0] * N
    if i != N - 1:
        mount[i] = 0.5
        mount[i+1] = 0.5
    else:
        mount[0] = 0.5
        mount[i] = 0.5
    mountains.append(mount)

print(' '.join([str(int(x)) for x in solve(mountains, dam)]))


Fixed submission:
N = int(input())
dam = list(map(int, input().split()))

mountains = [0] * N

x2 = 0
for i in range(N):
    if i % 2:
        x2 -= dam[i]
    else:
        x2 += dam[i]

mountains[0] = x2 // 2
for i in range(N-1):
    mountains[i+1] = dam[i] - mountains[i]

print(' '.join([str(x*2) for x in mountains]))

Buggy python submission (verdict: Time Limit Exceeded):
from numpy.linalg import solve

N = int(input())
dam = list(map(int, input().split()))

mountains = [[0 for i in range(N)] for j in range(N)]

for i, mount in enumerate(mountains):
    if i != N - 1:
        mount[i] = 0.5
        mount[i+1] = 0.5
    else:
        mount[0] = 0.5
        mount[i] = 0.5

print(' '.join([str(int(x)) for x in solve(mountains, dam)]))


Fixed submission:
N = int(input())
dam = list(map(int, input().split()))

mountains = [0] * N

x2 = 0
for i in range(N):
    if i % 2:
        x2 -= dam[i]
    else:
        x2 += dam[i]

mountains[0] = x2 // 2
for i in range(N-1):
    mountains[i+1] = dam[i] - mountains[i]

print(' '.join([str(x*2) for x in mountains]))

Buggy python submission (verdict: Time Limit Exceeded):
from numpy.linalg import solve

N = int(input())
dam = list(map(int, input().split()))

mountains = [[0 for i in range(N)] for j in range(N)]

for i, mount in enumerate(mountains):
    if i != N - 1:
        mount[i] = 0.5
        mount[i+1] = 0.5
    else:
        mount[0] = 0.5
        mount[i] = 0.5

ans = solve(mountains, dam)

print(' '.join([str(int(x)) for x in solve(mountains, dam)]))


Fixed submission:
N = int(input())
dam = list(map(int, input().split()))

mountains = [0] * N

x2 = 0
for i in range(N):
    if i % 2:
        x2 -= dam[i]
    else:
        x2 += dam[i]

mountains[0] = x2 // 2
for i in range(N-1):
    mountains[i+1] = dam[i] - mountains[i]

print(' '.join([str(x*2) for x in mountains]))
Buggy python submission (verdict: Time Limit Exceeded):

import sys
from collections import defaultdict

# ----------

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


def combination(n, k):
    if k > n - k:
        return combination(n, n - k)
    return fact[n] * ifact[k] * ifact[n - k]


def permitation(n, k):
    # nPk = nCk * k!
    res = combination(n, k) * fact[k]
    return res % MOD


N, K = map(int, input().split())
to = defaultdict(list)
for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)

# nまでの階乗を前処理
n = 200005
fact = defaultdict(int)
fact[0] = 1
for i in range(1, n + 1):
    fact[i] = fact[i - 1] * i
    fact[i] %= MOD
# nまでの階乗の逆元を前処理
ifact = defaultdict(int)
ifact[n] = pow(fact[n], MOD - 2, MOD)
for i in reversed(range(1, n + 1)):
    ifact[i - 1] = ifact[i] * i
    ifact[i - 1] %= MOD


def dfs(v, p=-1):
    global ans
    for u in to[v]:
        if u == p:
            continue
        dfs(u, v)
    if p == -1:
        nk = K
        c = len(to[v]) + 1
    else:
        nk = K - 2
        c = len(to[v]) - 1
    ans *= permitation(nk, c)
    ans %= MOD


ans = 1
dfs(0)
print(ans)


Fixed submission:
import sys
from collections import defaultdict

# ----------

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


def combination(n, k):
    if k > n - k:
        return combination(n, n - k)
    return fact[n] * ifact[k] * ifact[n - k]


def permitation(n, k):
    # nPk = nCk * k!
    if n < 0:
        return 0
    res = combination(n, k) * fact[k]
    return res % MOD


N, K = map(int, input().split())
to = defaultdict(list)
for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)

# nまでの階乗を前処理
n = 200005
fact = defaultdict(int)
fact[0] = 1
for i in range(1, n + 1):
    fact[i] = fact[i - 1] * i
    fact[i] %= MOD
# nまでの階乗の逆元を前処理
ifact = defaultdict(int)
ifact[n] = pow(fact[n], MOD - 2, MOD)
for i in reversed(range(1, n + 1)):
    ifact[i - 1] = ifact[i] * i
    ifact[i - 1] %= MOD


def dfs(v, p=-1):
    global ans
    for u in to[v]:
        if u == p:
            continue
        dfs(u, v)
    if p == -1:
        nk = K
        c = len(to[v]) + 1
    else:
        nk = K - 2
        c = len(to[v]) - 1
    ans *= permitation(nk, c)
    ans %= MOD


ans = 1
dfs(0)
print(ans)
Buggy python submission (verdict: Runtime Error):
def abc():
    from math import ceil
    _a, _b, c, d = map(int, input().split())

    a = min(_a, _b)
    b = max(_a, _b)

    cnt_all = b - a + 1

    l = ceil(a / c)
    r = b // c
    cnt_c = r - l + 1

    l = ceil(a / d)
    r = b // d
    cnt_d = r - l + 1

    cd = lcm(c, d)
    l = ceil(a / cd)
    r = b // cd
    cnt_cd = r - l + 1

    print(cnt_all - (cnt_c + cnt_d - cnt_cd))


abc()


Fixed submission:
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd(a, b)


def abc():
    from math import ceil
    a, b, c, d = map(int, input().split())

    cnt_all = b - a + 1

    l = ceil(a / c)
    r = b // c
    cnt_c = r - l + 1

    l = ceil(a / d)
    r = b // d
    cnt_d = r - l + 1

    cd = lcm(c, d)
    l = ceil(a / cd)
    r = b // cd
    cnt_cd = r - l + 1

    ans = cnt_all - (cnt_c + cnt_d - cnt_cd)
    if ans < 0:
        ans = 0
    print(ans)


abc()
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
MOD = 1000000007

broken = []
for i in range(M):
    broken.append(int(input()))

dp = [0] * (N + 2)
dp[N] = 1
for i in reversed(range(N)):
    if i in broken:
        dp[i] = 0
        if len(broken) != 0:
            broken.pop(-1)
        continue
    dp[i] = (dp[i+1] + dp[i+2]) % MOD

print(dp[0])


Fixed submission:
def abc():
    p, q, r = map(int, input().split())
    print(min(p + q, q + r, r + p))


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

sys.setrecursionlimit(10 ** 7)
# ----------

INF = float("inf")
MOD = 10 ** 9 + 7

s = si()

dp = [[0] * 2 for _ in range(100005)]
dp[0][0] = 1

n = len(s)
for i in range(n):
    if s[i] == "0":
        dp[i + 1][0] = dp[i][0]
        dp[i + 1][1] = dp[i][1]
    else:
        dp[i + 1][1] = (dp[i][0] + dp[i][1]) % MOD

    if s[i] == "0":
        dp[i + 1][1] += dp[i][1] * 2 % MOD
    else:
        dp[i + 1][0] += dp[i][0] * 2 % MOD
        dp[i + 1][1] += dp[i][1] * 2 % MOD

ans = (dp[n][0] + dp[n][1]) % MOD
print(ans)

Fixed submission:

import sys

sys.setrecursionlimit(10 ** 7)
# ----------

INF = float("inf")
MOD = 10 ** 9 + 7

s = input().strip()

dp = [[0] * 2 for _ in range(100005)]
dp[0][0] = 1

n = len(s)
for i in range(n):
    if s[i] == "0":
        dp[i + 1][0] = dp[i][0]
        dp[i + 1][1] = dp[i][1]
    else:
        dp[i + 1][1] = (dp[i][0] + dp[i][1]) % MOD

    if s[i] == "0":
        dp[i + 1][1] += dp[i][1] * 2 % MOD
    else:
        dp[i + 1][0] += dp[i][0] * 2 % MOD
        dp[i + 1][1] += dp[i][1] * 2 % MOD

ans = (dp[n][0] + dp[n][1]) % MOD
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())

for i in range(M):
    l, r = map(int, input().split())
    if i == 0:
        s = set(range(l, r+1))
    s = s & set(range(l, r+1))

print(len(s))


Fixed submission:
N, M = map(int, input().split())

left = 0
right = N
for i in range(M):
    L, R = map(int, input().split())
    left = max(left, L)
    right = min(right, R)

if left > right:
    print(0)
else:
    print(right - left + 1)
Buggy python submission (verdict: Runtime Error):
from itertools import groupby
from numpy import cumsum


N, K = map(int, input().split())
S = input().strip()

if len(set(S)) == 1:
    print(N)
    exit()

# ランレングス圧縮
G = []
for k, v in groupby(S):
    G.append(len(list(v)))
# 1 0 1 0 1...の配列が欲しいので、
# 先頭、末尾が0ならダミーの要素をそれぞれ追加する
if S[0] == '0':
    G.insert(0, 0)
if S[-1] == '0':
    G.append(0)

cum = [0]
cum.extend(list(cumsum(G)))
cum.append(0)

ans = 0
gc = len(G)
w = min(gc, 3+(K-1)*2)
for i in range(0, gc, 2):
    ans = max(ans, cum[i+w]-cum[i])
print(ans)


Fixed submission:
from itertools import groupby
from numpy import cumsum


N, K = map(int, input().split())
S = input().strip()

if len(set(S)) == 1:
    print(N)
    exit()

G = []
if S[0] == '0':
    G.append(0)
for k, v in groupby(S):
    G.append(len(list(v)))
G.append(0)

cum = [0]
cum.extend(list(cumsum(G)))
cum.append(0)

ans = 0
gc = len(G)
w = min(gc, 3+(K-1)*2)
for i in range(0, gc-w+2, 2):
    ans = max(ans, cum[i+w]-cum[i])
print(ans)

Buggy python submission (verdict: Runtime Error):
from itertools import groupby
from numpy import cumsum


N, K = map(int, input().split())
S = input().strip()

if len(set(S)) == 1:
    print(N)
    exit()

# ランレングス圧縮
G = []
for k, v in groupby(S):
    G.append(len(list(v)))
# 1 0 1 0 1...の配列が欲しいので、
# 先頭、末尾が0ならダミーの要素をそれぞれ追加する
if S[0] == '0':
    G.insert(0, 0)
if S[-1] == '0':
    G.append(0)

cum = [0]
cum.extend(list(cumsum(G)))
cum.append(0)

ans = 0
gc = len(G)
w = min(gc, 3+(K-1)*2)
for i in range(0, w, 2):
    ans = max(ans, cum[i+w]-cum[i])
print(ans)


Fixed submission:
from itertools import groupby
from numpy import cumsum


N, K = map(int, input().split())
S = input().strip()

if len(set(S)) == 1:
    print(N)
    exit()

G = []
if S[0] == '0':
    G.append(0)
for k, v in groupby(S):
    G.append(len(list(v)))
G.append(0)

cum = [0]
cum.extend(list(cumsum(G)))
cum.append(0)

ans = 0
gc = len(G)
w = min(gc, 3+(K-1)*2)
for i in range(0, gc-w+2, 2):
    ans = max(ans, cum[i+w]-cum[i])
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = int(input())
B = int(input())
C = int(input())
D = int(input())
E = int(input())

d = {
    1: N,
    2: 0,
    3: 0,
    4: 0,
    5: 0,
    6: 0,
}

ans = 0
while d[6] != N:
    m = min(d[5], E)
    d[5] -= m
    d[6] += m

    m = min(d[4], D)
    d[4] -= m
    d[5] += m

    m = min(d[3], C)
    d[3] -= m
    d[4] += m

    m = min(d[2], B)
    d[2] -= m
    d[3] += m

    m = min(d[1], A)
    d[1] -= m
    d[2] += m

    ans += 1

print(ans)


Fixed submission:
from math import ceil

N = int(input())
A = int(input())
B = int(input())
C = int(input())
D = int(input())
E = int(input())

min_move = min(A, B, C, D, E)

ans = ceil(N / min_move) + 4

print(ans)
Buggy python submission (verdict: Runtime Error):
X, Y, Z, K = map(int, input().split())

A = sorted(map(int, input().split()), reverse=True)
B = sorted(map(int, input().split()), reverse=True)
C = sorted(map(int, input().split()), reverse=True)

ABC = []
for a in range(X):
    for b in range(Y):
        if (a + 1) + (b + 1) > K:
            break
        for c in range(Z):
            if (a + 1) + (b + 1) * (c + 1) > K:
                break
            ABC.append(A[a] + B[b] + C[c])

ABC.sort(reverse=True)
for i in range(K):
    print(ABC[i])


Fixed submission:
X, Y, Z, K = map(int, input().split())

A = sorted(map(int, input().split()), reverse=True)
B = sorted(map(int, input().split()), reverse=True)
C = sorted(map(int, input().split()), reverse=True)

AB = []
for i in range(X):
    for j in range(Y):
        AB.append(A[i] + B[j])

AB.sort(reverse=True)

ABC = []
for i in range(min(K, len(AB))):
    for j in range(Z):
        ABC.append(AB[i] + C[j])

ABC.sort(reverse=True)
for i in range(K):
    print(ABC[i])

Buggy python submission (verdict: Runtime Error):
X, Y, Z, K = map(int, input().split())

A = sorted(map(int, input().split()), reverse=True)
B = sorted(map(int, input().split()), reverse=True)
C = sorted(map(int, input().split()), reverse=True)

ABC = []
for a in range(X):
    for b in range(Y):
        if (a + 1) + (b + 1) > K:
            break
        for c in range(Z):
            if (a + 1) + (b + 1) * (c + 1) > K:
                break
            ABC.append(A[a] + B[b] + C[c])

ABC.sort(reverse=True)
for i in range(K):
    print(ABC[i])


Fixed submission:
X, Y, Z, K = map(int, input().split())

A = sorted(map(int, input().split()), reverse=True)
B = sorted(map(int, input().split()), reverse=True)
C = sorted(map(int, input().split()), reverse=True)

AB = []
for i in range(X):
    for j in range(Y):
        AB.append(A[i] + B[j])

AB.sort(reverse=True)

ABC = []
for i in range(min(K, len(AB))):
    for j in range(Z):
        ABC.append(AB[i] + C[j])

ABC.sort(reverse=True)
for i in range(K):
    print(ABC[i])

Buggy python submission (verdict: Time Limit Exceeded):
X, Y, Z, K = map(int, input().split())

A = sorted(map(int, input().split()), reverse=True)
B = sorted(map(int, input().split()), reverse=True)
C = sorted(map(int, input().split()), reverse=True)

AB = []
for i in range(X):
    for j in range(Y):
        AB.append(A[i] + B[j])

AB.sort(reverse=True)

ABC = []
for i in range(min(K, len(AB))):
    for j in range(Z):
        ABC.append(AB[i] + C[j])

ABC.sort(reverse=True)
for i in range(K):
    print(ABC[i])


Fixed submission:
X, Y, Z, K = map(int, input().split())

A = sorted(map(int, input().split()), reverse=True)
B = sorted(map(int, input().split()), reverse=True)
C = sorted(map(int, input().split()), reverse=True)

AB = []
for i in range(X):
    for j in range(Y):
        AB.append(A[i] + B[j])

AB.sort(reverse=True)

ABC = []
for i in range(min(K, len(AB))):
    for j in range(Z):
        ABC.append(AB[i] + C[j])

ABC.sort(reverse=True)
for i in range(K):
    print(ABC[i])
Buggy python submission (verdict: Time Limit Exceeded):
import re

N, Q = map(int, input().split())
S = input().rstrip()

for i in range(Q):
    l, r = map(int, input().split())
    s = S[l-1:r]
    print(len(re.findall('AC', s)))



Fixed submission:
N, Q = map(int, input().split())
S = input().rstrip()

cs = [0]
cnt = 0

for i in range(N-1):
    if S[i:i+2] == 'AC':
        cnt += 1
    cs.append(cnt)

for i in range(Q):
    l, r = map(int, input().split())
    print(cs[r-1]-cs[l-1])
Buggy python submission (verdict: Runtime Error):
G = [0] * 4
for i in range(3):
    a, b = mii()
    a -= 1
    b -= 1
    G[a] += 1
    G[b] += 1

for i in range(4):
    if G[i] == 3:
        print('NO')
        exit()

print('YES')


Fixed submission:
G = [0] * 4
for i in range(3):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a] += 1
    G[b] += 1

for i in range(4):
    if G[i] == 3:
        print('NO')
        exit()

print('YES')
Buggy python submission (verdict: Runtime Error):
l = sorted(map(int, input().split()))
if ''.join(l) == '1479':
    print('YES')
else:
    print('NO')

Fixed submission:
l = sorted(input().split())
if ''.join(l) == '1479':
    print('YES')
else:
    print('NO')
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
h = list(map(int, input().split()))

dp = [10 ** 9 for i in range(N + K)]
dp[0] = 0
for i in range(N):
    for j in range(1, K + 1):
        if i + j < N:
            dp[i + j] = min(dp[i + j], dp[i] + abs(h[i] - h[i + j]))

print(dp[N - 1])


Fixed submission:
INF = float('inf')
N, K = map(int, input().split())
h = list(map(int, input().split()))

dp = [INF for _ in range(N)]
dp[0] = 0
for i in range(N):
    for j in range(K):
        j += 1
        if i + j < N:
            dp[i+j] = min(dp[i+j], dp[i] + abs(h[i+j] - h[i]))

print(dp[N-1])

Buggy python submission (verdict: Time Limit Exceeded):
INF = float('inf')
N, K = map(int, input().split())
h = list(map(int, input().split()))

dp = [INF for _ in range(N)]
dp[0] = 0
for i in range(N):
    for j in range(1, K+1):
        if i + j < N:
            dp[i+j] = min(dp[i+j], dp[i] + abs(h[i+j] - h[i]))

print(dp[N-1])


Fixed submission:
INF = float('inf')
N, K = map(int, input().split())
h = list(map(int, input().split()))

dp = [INF for _ in range(N)]
dp[0] = 0
for i in range(N):
    for j in range(K):
        j += 1
        if i + j < N:
            dp[i+j] = min(dp[i+j], dp[i] + abs(h[i+j] - h[i]))

print(dp[N-1])
Buggy python submission (verdict: Time Limit Exceeded):
N, W = map(int, input().split())
weight = []
value = []
for i in range(N):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)
dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
for i in range(N):
    for j in range(W+1):
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])
        if j - weight[i] >= 0:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j-weight[i]]+value[i])
print(dp[N][W])



Fixed submission:
N, W = map(int, input().split())

dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
weight = [0]
value = [0]
for i in range(N):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)

for i in range(N):
    i += 1
    for sum_w in range(W+1):
        # i 番目の品物を選ぶ場合
        if sum_w >= weight[i]:
            dp[i][sum_w] = max(dp[i][sum_w], dp[i-1][sum_w - weight[i]] + value[i])
        # i 番目の品物を選ばない場合
        dp[i][sum_w] = max(dp[i][sum_w], dp[i-1][sum_w])

print(dp[N][W])

Buggy python submission (verdict: Runtime Error):

N, W = map(int, input().split())
weight = []
value = []
for i in range(N):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)
dp = [[0 for _ in range(W)] for _ in range(N)]
for i in range(N):
    for j in range(W+1):
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])
        if j - weight[i] >= 0:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j-weight[i]]+value[i])
print(dp[N][W])



Fixed submission:
N, W = map(int, input().split())

dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
weight = [0]
value = [0]
for i in range(N):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)

for i in range(N):
    i += 1
    for sum_w in range(W+1):
        # i 番目の品物を選ぶ場合
        if sum_w >= weight[i]:
            dp[i][sum_w] = max(dp[i][sum_w], dp[i-1][sum_w - weight[i]] + value[i])
        # i 番目の品物を選ばない場合
        dp[i][sum_w] = max(dp[i][sum_w], dp[i-1][sum_w])

print(dp[N][W])

Buggy python submission (verdict: Time Limit Exceeded):
N, W = map(int, input().split())

dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
weight = [0]
value = [0]
for i in range(N):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)

for i in range(N):
    i += 1
    for sum_w in range(W+1):
        # i 番目の品物を選ぶ場合
        if sum_w >= weight[i]:
            dp[i][sum_w] = max(dp[i][sum_w], dp[i-1][sum_w - weight[i]] + value[i])
        # i 番目の品物を選ばない場合
        dp[i][sum_w] = max(dp[i][sum_w], dp[i-1][sum_w])

print(dp[N][W])

Fixed submission:
N, W = map(int, input().split())

dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
weight = [0]
value = [0]
for i in range(N):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)

for i in range(N):
    i += 1
    for sum_w in range(W+1):
        # i 番目の品物を選ぶ場合
        if sum_w >= weight[i]:
            dp[i][sum_w] = max(dp[i][sum_w], dp[i-1][sum_w - weight[i]] + value[i])
        # i 番目の品物を選ばない場合
        dp[i][sum_w] = max(dp[i][sum_w], dp[i-1][sum_w])

print(dp[N][W])
Buggy python submission (verdict: Time Limit Exceeded):
N, W = map(int, input().split())

dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
weight = []
value = []
for i in range(N):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)

for i in range(N):
    for sum_w in range(W+1):
        # i 番目の品物を選ぶ場合
        if sum_w >= weight[i]:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w - weight[i]] + value[i])
        # i 番目の品物を選ばない場合
        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])

print(dp[N][W])

Fixed submission:
N, W = map(int, input().split())
INF = float('inf')
MAX_V = 100100

dp = [[INF for _ in range(MAX_V+1)] for _ in range(N+1)]
dp[0][0] = 0
weight = []
value = []
for i in range(N):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)

for i in range(N):
    for sum_v in range(MAX_V + 1):
        # i 番目の品物を選ぶ場合
        if sum_v - value[i] >= 0:
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v - value[i]] + weight[i])
        # i 番目の品物を選ばない場合
        dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])

ans = 0
for sum_v in range(MAX_V + 1):
    if dp[N][sum_v] <= W:
        ans = sum_v

print(ans)

Buggy python submission (verdict: Runtime Error):
 N, W = map(int, input().split())

dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
weight = []
value = []
for i in range(N):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)

for i in range(N):
    for sum_w in range(W+1):
        # i 番目の品物を選ぶ場合
        if sum_w >= weight[i]:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w - weight[i]] + value[i])
        # i 番目の品物を選ばない場合
        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])

print(dp[N][W])


Fixed submission:
N, W = map(int, input().split())
INF = float('inf')
MAX_V = 100100

dp = [[INF for _ in range(MAX_V+1)] for _ in range(N+1)]
dp[0][0] = 0
weight = []
value = []
for i in range(N):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)

for i in range(N):
    for sum_v in range(MAX_V + 1):
        # i 番目の品物を選ぶ場合
        if sum_v - value[i] >= 0:
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v - value[i]] + weight[i])
        # i 番目の品物を選ばない場合
        dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])

ans = 0
for sum_v in range(MAX_V + 1):
    if dp[N][sum_v] <= W:
        ans = sum_v

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

s = input().strip()
t = input().strip()

dp = np.zeros((3100, 3100))

for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+1)
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j])
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j+1])

ans = ""
i = len(s)
j = len(t)
while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ans = s[i-1] + ans
        i -= 1
        j -= 1

print(ans)


Fixed submission:
s = input().strip()
t = input().strip()

dp = [[0 for _ in range(3100)] for _ in range(3100)]

for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+1)
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j])
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j+1])

ans = ""
i = len(s)
j = len(t)
while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ans = s[i-1] + ans
        i -= 1
        j -= 1

print(ans)
Buggy python submission (verdict: Runtime Error):
import heapq
from collections import defaultdict, deque
from math import ceil, factorial

si = lambda: input().strip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
lmii = lambda: list(map(int, input().split()))
smii = lambda: sorted(map(int, input().split()))

N, M = mii()
edge = defaultdict(list)
memo = defaultdict(int)
done = defaultdict(bool)


def dp(v):
    if done[v]:
        return memo[v]
    ret = 0
    for to in edge[v]:
        ret = max(ret, dp(to) + 1)
    done[v] = True
    memo[v] = ret
    return ret


for i in range(M):
    x, y = mii()
    edge[x].append(y)
ans = 0
for v in range(1, N+1):
    ans = max(ans, dp(v))

print(ans)

Fixed submission:
import heapq
from collections import defaultdict, deque
from math import ceil, factorial
import sys
sys.setrecursionlimit(10**7)

si = lambda: input().strip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
lmii = lambda: list(map(int, input().split()))
smii = lambda: sorted(map(int, input().split()))
# ---
N, M = mii()
edge = defaultdict(list)
memo = defaultdict(int)
done = defaultdict(bool)


def dp(v):
    if done[v]:
        return memo[v]
    ret = 0
    for to in edge[v]:
        ret = max(ret, dp(to) + 1)
    done[v] = True
    memo[v] = ret
    return ret


for i in range(M):
    x, y = mii()
    edge[x].append(y)
ans = 0
for v in range(1, N+1):
    ans = max(ans, dp(v))

print(ans)