Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
from collections import deque
import bisect

N,K = map(int,input().split())
V = [int(i) for i in input().split()]

answer = 0
A = 0
while A <= min(N,K):
    B = 0
    while A + B <= min(N,K):
        have = deque()
        for i in range(A):
            bisect.insort_left(have, V[i])
        for i in range(B):
            bisect.insort_left(have, V[-(i+1)])
        
        throw = min(K - (A + B), len(have))
        for _ in range(throw):
            tmp = have.popleft()
            if tmp > 0:
                have.append(tmp)
                break

        answer = max(answer, sum(have))
        B += 1
    A += 1

print(answer)

Fixed submission:
from collections import deque
from bisect import insort_left

N,K = map(int,input().split())
V = [int(i) for i in input().split()]

answer = 0
A = 0
while A <= min(N,K):
    B = 0
    while A + B <= min(N,K):
        have = []
        for i in range(A):
            insort_left(have, V[i])
        for i in range(B):
            insort_left(have, V[-(i+1)])

        have = deque(have)

        throw = min(K - (A + B), len(have))
        for _ in range(throw):
            tmp = have.popleft()
            if tmp > 0:
                have.append(tmp)
                break

        answer = max(answer, sum(have))
        B += 1
    A += 1

print(answer)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
V = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]

ans = 0
for i in range(2 ** N):
    tmp = 0
    for j in range(N):
        if (i >> j) & 1:
            tmp += V[j] - C[j]
    ans = max(ans, tmp)

print(ans)

Fixed submission:
N = int(input())
V = [int(i) for i in input().split()]

for i,x in enumerate(input().split()):
    V[i] -= int(x)

V.sort()

ans = 0
for v in V:
    if v > 0:
        ans += v

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

N,M = map(int,input().split())

E = [[] for _ in range(N)]
root = [True] * N
for _ in range(N-1+M):
    A,B = map(int,input().split())
    E[A-1].append(B-1)
    root[B-1] = False
root = root.index(True)

dist = [-1] * N
dist[root] = 0
parent = [-1] * N
q = deque([root])
while q:
    par = q.popleft()
    for e in E[par]:
        if dist[e] < dist[par] + 1:
            parent[e] = par
            dist[e] = dist[par] + 1
            q.append(e)

for ans in parent:
    print(ans + 1)

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

# E[i]: 頂点iから伸びる頂点の集合
E = [[] for _ in range(N)]
# parent_cnt[i]: 頂点iの親
parent_cnt = [0] * N
for _ in range(N-1+M):
    A,B = map(int,input().split())
    E[A-1].append(B-1)
    parent_cnt[B-1] += 1

# 根を見つける
for i,num in enumerate(parent_cnt):
    if num == 0:
        root = i
        break

parent = [None] * N
parent[root] = 0

q = [root]
# DFS O(N+M)
while q:
    qq = []
    for V in q:
        for Vto in E[V]:
            parent_cnt[Vto] -= 1

            # 親が決定
            if parent_cnt[Vto] == 0:
                parent[Vto] = V + 1
                qq.append(Vto)
    
    q = qq

print(*parent, sep="\n")

Buggy python submission (verdict: Time Limit Exceeded):
N,M = map(int,input().split())
E = [[] for _ in range(N)]
root = [True] * N
for _ in range(N-1+M):
    A,B = map(int,input().split())
    E[A-1].append(B-1)
    root[B-1] = False
root = root.index(True)

from collections import deque

dist = [-1] * N
dist[root] = 0
parent = [-1] * N
q = deque([root])
while q:
    par = q.pop()
    for e in E[par]:
        if dist[e] < dist[par] + 1:
            parent[e] = par
            dist[e] = dist[par] + 1
        q.append(e)

for ans in parent:
    print(ans + 1)

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

# E[i]: 頂点iから伸びる頂点の集合
E = [[] for _ in range(N)]
# parent_cnt[i]: 頂点iの親
parent_cnt = [0] * N
for _ in range(N-1+M):
    A,B = map(int,input().split())
    E[A-1].append(B-1)
    parent_cnt[B-1] += 1

# 根を見つける
for i,num in enumerate(parent_cnt):
    if num == 0:
        root = i
        break

parent = [None] * N
parent[root] = 0

q = [root]
# DFS O(N+M)
while q:
    qq = []
    for V in q:
        for Vto in E[V]:
            parent_cnt[Vto] -= 1

            # 親が決定
            if parent_cnt[Vto] == 0:
                parent[Vto] = V + 1
                qq.append(Vto)
    
    q = qq

print(*parent, sep="\n")
Buggy python submission (verdict: Runtime Error):
key = tuple("keyence")

S = input().rstrip("\n")

idx = 0
for i in S:
    if i == key[idx]:
        idx += 1

if idx == len(key):
    print("YES")
else:
    print("NO")

Fixed submission:
keyence = "keyence"

S = input()

flag = False
for sta in range(len(S)):
    for end in range(sta,len(S)):
        if S[:sta] + S[end:] == keyence:
            flag = True

if flag:
    print("YES")
else:
    print("NO")

Buggy python submission (verdict: Runtime Error):
from collections import Counter

key = "keyence"

S = input()

idx = 0
for i in S:
    if i == key[idx]:
        idx += 1

if idx == len(key):
    print("YES")
else:
    print("NO")

Fixed submission:
keyence = "keyence"

S = input()

flag = False
for sta in range(len(S)):
    for end in range(sta,len(S)):
        if S[:sta] + S[end:] == keyence:
            flag = True

if flag:
    print("YES")
else:
    print("NO")
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
from bisect import insort_left

def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    B = [int(i) for i in input().split()]
    
    if sum(A) < sum(B):
        print(-1)
        exit()

    ok = []
    ng_cnt = 0
    ng_num = 0
    for i in range(N):
        if A[i] - B[i] >= 0:
            insort_left(ok, A[i] - B[i])
        else:
            ng_cnt += 1
            ng_num += B[i] - A[i]
    ans = ng_cnt

    while ng_num > 0:
        ans += 1
        ng_num -= ok.pop()

    print(ans)

if __name__ == "__main__":
    main()

Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
from bisect import insort_left

def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    B = [int(i) for i in input().split()]
    
    if sum(A) < sum(B):
        print(-1)
        exit()

    ok = []
    ng_cnt = 0
    ng_num = 0
    for i in range(N):
        if A[i] - B[i] >= 0:
            ok.append(A[i] - B[i])
        else:
            ng_cnt += 1
            ng_num += B[i] - A[i]
    ok.sort()

    ans = ng_cnt

    while ng_num > 0:
        ans += 1
        ng_num -= ok.pop()

    print(ans)

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int,input().split())
h = [int(i) for i in input().split()]

# DPテーブルを初期化
dp = [float("inf")]*N

# 初期状態
dp[0] = 0

# 足場iから足場(i+j)にジャンプする
for i in range(0,N):
    for j in range(1,K+1):
        if (i+j) >= N:
            break
        dp[i+j] = min(dp[i+j], dp[i]+abs(h[i]-h[i+j]))

print(dp[-1])


Fixed submission:
N, K = map(int,input().split())
h = [int(i) for i in input().split()]

# DPテーブルを初期化
dp = [float("inf")]*N

# 初期状態
dp[0] = 0

# 足場iから足場(i+j)にジャンプする
for i in range(0,N):
    for j in range(1,K+1):
        if (i+j) >= N:
            break
        dp[i+j] = min(dp[i+j], dp[i]+abs(h[i]-h[i+j]))

print(dp[-1])
Buggy python submission (verdict: Runtime Error):
N = int(input())
V = [int(i) for i in input().split()]

Vodd = V[1::2]
Veven = V[::2]

from collections import Counter

Vodd = sorted(Counter(Vodd).items(), key=lambda x:x[1])
Veven = sorted(Counter(Veven).items(), key=lambda x:x[1])

if Vodd[-1][0] == Veven[-1][0]:
    if len(Vodd) == len(Veven) == 1:
        ans = N - Vodd[-1][1]
    elif len(Vodd) == 1:
        ans = N - Vodd[-1][1] - Veven[-2][1]
    elif len(Veven) == 1:
        ans = N - Vodd[-2][1] - Veven[-1][1]
    elif Vodd[-2][1] >= Veven[-2][1]:
        ans = N - Vodd[-2][1] - Veven[-1][1]
    else:
        ans = N - Vodd[-1][1] - Veven[-2][1]
else:
    ans = N - Vodd[-1][1] - Veven[-1][1]


print(ans)


Fixed submission:
n = list(input())

for i in range(3):
    if n[i] == "1":
        n[i] = "9"
    elif n[i] == "9":
        n[i] = "1"

print(*n,sep="")
Buggy python submission (verdict: Time Limit Exceeded):
# 解説AC
from itertools import accumulate

N,X = map(int, input().split())
S = list(accumulate([0] + [int(i) for i in input().split()]))

ans = float("inf")
for k in range(1, N + 1):
    cost = (N + k) * X
    for i, now in enumerate(range(N, 0, -k), start = 1):
        x = S[now] - S[max(0, now - k)]
        cost += 5 * x if (i == 1) else (2 * i + 1) * x

    ans = min(ans, cost)

print(ans)

Fixed submission:
# 解説AC
from itertools import accumulate

def main():
    N,X = map(int, input().split())
    T = [0] + [int(i) for i in input().split()]
    S = list(accumulate(T))

    ans = float("inf")
    for k in range(1, N + 1):
        cost = (N + k) * X
        for i, now in enumerate(range(N, 0, -k), start = 1):
            x = S[now] - S[max(0, now - k)]
            cost += 5 * x if (i == 1) else (2 * i + 1) * x

        ans = min(ans, cost)

    print(ans)

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
# 解説AC
N,K,Q = map(int, input().split())
A = [int(i) for i in input().split()]

ans = float("inf")

# A[i]: 最小値X
for i in range(N):
    # 最大値Yの候補
    can = []

    # A[left:right]: A[i]以上の連続部分列
    left = 0
    while left < N:
        right = left
        while right < N and A[i] <= A[right]:
            right += 1

        # 連続部分列長
        L = right - left

        tmp = sorted([A[j] for j in range(left, right)])
        can += tmp[:max(0, L - K + 1)]

        left = right + 1
    
    # Q番目に小さいものがYの最小値
    can.sort()
    if len(can) >= Q:
        ans = min(ans, can[Q - 1] - A[i])

print(ans)

Fixed submission:
# 解説AC
N,K,Q = map(int, input().split())
A = [int(i) for i in input().split()]

def main():
    ans = float("inf")

    # A[i]: 最小値X
    for i in range(N):
        # 最大値Yの候補
        can = []

        # A[left:right]: A[i]以上の連続部分列
        left = 0
        while left < N:
            right = left
            while right < N and A[i] <= A[right]:
                right += 1

            # 連続部分列長
            L = right - left

            tmp = sorted([A[j] for j in range(left, right)])
            can += tmp[:max(0, L - K + 1)]

            left = right + 1
        
        # Q番目に小さいものがYの最小値
        can.sort()
        if len(can) >= Q:
            ans = min(ans, can[Q - 1] - A[i])

    print(ans)

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

def is_symmetric(a):
    return np.array_equal(a, a.T)

def main():
    N = int(input())
    S = [[] for _ in range(N)]
    for i in range(N):
        for s in list(input()):
            S[i].append(ord(s) - ord("a"))

    S = np.array(S)

    ans = 0
    for A in range(N):
        for B in range(N):
            if is_symmetric(np.roll(np.roll(S, A, axis=0), B, axis=1)):
                ans += 1

    print(ans)

if __name__ == "__main__":
    main()

Fixed submission:
# 解説AC
import numpy as np

def is_symmetric(a):
    """
    対象行列判定 O(N * N)
    """
    return np.array_equal(a, a.T)

def main():
    N = int(input())
    S = [[ord(s) - ord("a") for s in list(input())] for _ in range(N)]

    S = np.array(S)

    ans = 0
    for B in range(N):
        if is_symmetric(np.roll(S, B, axis=1)):
            ans += N

    print(ans)

if __name__ == "__main__":
    main()

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

def is_symmetric(a):
    return np.array_equal(a, a.T)

def main():
    N = int(input())
    S = [[] for _ in range(N)]
    for i in range(N):
        for s in list(input()):
            S[i].append(ord(s) - ord("a"))

    S = np.array(S)

    ans = 0
    for A in range(N):
        for B in range(N):
            if is_symmetric(np.roll(S, (A, B), axis=(0,1))):
                ans += 1

    print(ans)

if __name__ == "__main__":
    main()

Fixed submission:
# 解説AC
import numpy as np

def is_symmetric(a):
    """
    対象行列判定 O(N * N)
    """
    return np.array_equal(a, a.T)

def main():
    N = int(input())
    S = [[ord(s) - ord("a") for s in list(input())] for _ in range(N)]

    S = np.array(S)

    ans = 0
    for B in range(N):
        if is_symmetric(np.roll(S, B, axis=1)):
            ans += N

    print(ans)

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
from itertools import accumulate

def main():
    H,W,D = map(int,input().split())
    A = [None] * (H*W+1)
    for i in range(H):
        j = 1
        for x in input().split():
            A[int(x)] = (i+1,j)
            j += 1

    # クエリ
    Q = int(input())
    for _ in range(Q):
        ans = 0
        L, R = map(int,input().split())

        for i in range(L+D,R+1,D):
            ans += abs(A[i][0] - A[i-D][0])
            ans += abs(A[i][1] - A[i-D][1])
        
        print(ans)

if __name__ == "__main__":
    main()

Fixed submission:
import sys
input = sys.stdin.readline
from itertools import accumulate

def main():
    H,W,D = map(int,input().split())
    A = [None] * (H*W+1)
    for i in range(H):
        j = 1
        for x in input().split():
            A[int(x)] = [0,(i+1,j)]
            j += 1

    for i in range(1,H*W+1):
        if i <= D:
            continue
        A[i][0] += A[i-D][0]
        A[i][0] += abs(A[i][1][0] - A[i-D][1][0])
        A[i][0] += abs(A[i][1][1] - A[i-D][1][1])

    # クエリ
    Q = int(input())
    for _ in range(Q):
        L, R = map(int,input().split())

        print(A[R][0] - A[L][0])

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
# [l,r]での素数リスト
def primes(l,r):
    is_prime = [True] * (r + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(r**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, r + 1, i):
            is_prime[j] = False
    return len([i for i in range(l,r + 1) if is_prime[i] and i % 2 == 1 and is_prime[(i+1)//2]])

import sys
input = sys.stdin.readline

Q = int(input())
lr = [[int(i) for i in input().split()] for _ in range(Q)]

for i in range(Q):
    print(primes(lr[i][0],lr[i][1]))

Fixed submission:
MAXN = 10**5 + 1

# c[i]: [0,i]での素数の個数
f = [False] * (MAXN)
for i in range(2,MAXN):
    if not f[i]:
        for j in range(i+i,MAXN,i):
            f[j] = True
c = [0] * (MAXN)
for i in range(3,MAXN):
    if not f[i] and not f[(i+1)//2]:
        c[i] += 1
    c[i] += c[i-1]

Q = int(input())
for _ in range(Q):
    L,R = map(int,input().split())
    print(c[R] - c[L-1])
Buggy python submission (verdict: Time Limit Exceeded):
# 解説AC
N,M = map(int, input().split())
edge = [[] for _ in range(N)]
for _ in range(M):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

color = [0] * N

def is_bipartite():
    """ 二部グラフか判定する """
    stack = [(0,1)]
    while stack:
        v, c = stack.pop()
        color[v] = c
        for w in edge[v]:
            if color[w] == c: return False
            if color[w] == 0:
                stack.append((w, (-1) * c))
    return True

if is_bipartite():
    B = color.count(1)
    W = color.count(-1)
    print(B * W - M)
else:
    print(N * (N - 1) // 2 - M)

Fixed submission:
# 解説AC
N,M = map(int, input().split())
edge = [[] for _ in range(N)]
for _ in range(M):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

color = [0] * N

def is_bipartite():
    """ 二部グラフか判定する """
    stack = [(0,1)]
    while stack:
        v, c = stack.pop()
        color[v] = c
        for w in edge[v]:
            if color[w] == c: return False
            if color[w] == 0:
                stack.append((w, (-1) * c))
    return True

if is_bipartite():
    B = color.count(1)
    W = N - B
    print(B * W - M)
else:
    print(N * (N - 1) // 2 - M)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
from copy import deepcopy

def warshall_floyd(n,a):
    d = deepcopy(a)
    is_via = np.full((n,n), False)
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if i == j:
                    continue
                # 経由する場合
                if (d[i][k] != 0 and d[k][j] != 0) and (d[i][j] == d[i][k] + d[k][j]):
                    is_via[i][j] = True
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    flag = np.all(a == d)
    return flag, is_via

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

flag, is_via = warshall_floyd(N,A)

if not flag:
    print(-1)
    exit()

ans = 0
for i in range(N):
    for j in range(i,N):
        if is_via[i][j]:
            continue
        ans += A[i][j]

print(ans)

Fixed submission:
from copy import deepcopy

def warshall_floyd(n,a):
    d = deepcopy(a)
    is_via = [[False] * n for _ in range(n)]
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if i == j:
                    continue
                # 経由する場合
                if (d[i][k] != 0 and d[k][j] != 0) and (d[i][j] == d[i][k] + d[k][j]):
                    is_via[i][j] = True
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    flag = a == d
    return flag, is_via

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

flag, is_via = warshall_floyd(N,A)

if not flag:
    print(-1)
    exit()

ans = 0
for i in range(N):
    for j in range(i,N):
        if is_via[i][j]:
            continue
        ans += A[i][j]

print(ans)
Buggy python submission (verdict: Runtime Error):
# https://atcoder.jp/contests/abc067/tasks/arc078_b

from collections import deque

N = int(input())
E = [[] for _ in range(N)]
for _ in range(N-1):
    a,b = map(int,input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)

def dist_from_X(X):
    dist = [-1] * N
    
    que = deque([X])
    dist[X] = 0
    while que:
        v = que.popleft()
        d = dist[v]
        for e in E[v]:
            if dist[e] > -1:
                continue
            dist[e] = d + 1
            que.append(e)
    
    return dist

Fennec = dist_from_X(0)
Sunuke = dist_from_X(N-1)

cnt = [0,0]
for i,j in zip(Fennec, Sunuke):
    if i <= j:
        cnt[0] += 1
    else:
        cnt[1] += 1

assert cnt[0] != cnt[1]
if cnt[0] > cnt[1]:
    print("Fennec")
else:
    print("Sunuke")

Fixed submission:
import numpy as np
from collections import deque

N = int(input())
E = [[] for _ in range(N)]
for _ in range(N-1):
    a,b = map(int,input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)

# BFS
def dist_from_X(X:int):
    dist = np.full(N, -1)
    que = deque([X])
    dist[X] = 0
    while que:
        v = que.popleft()
        d = dist[v]
        for e in E[v]:
            if dist[e] > -1:
                continue
            dist[e] = d + 1
            que.append(e)
    return dist

Fennec = dist_from_X(0)
Sunuke = dist_from_X(N-1)

cnt = np.count_nonzero(Fennec <= Sunuke)

if cnt > N - cnt:
    print("Fennec")
else:
    print("Snuke")
Buggy python submission (verdict: Time Limit Exceeded):
N,A,B = map(int, input().split())
H = [int(input()) for i in range(N)]

def check(X):
    """ X回以下の爆発で全滅するか """
    ans = 0
    for h in H:
        cnt = ((h - B * X) + (A - B) - 1) // (A - B)
        ans += max(0, cnt)
    return ans <= X

ng = 0
ok = 10 ** 18
while ok - ng > 1:
    mid = (ok + ng) // 2
    if check(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Fixed submission:
from math import ceil

N,A,B = map(int,input().split())
h = sorted([int(input()) for _ in range(N)], reverse=True)

# C回以下の爆発で倒せるか
def is_all_kill(C:int):
    cnt = 0
    for HP in h:
        # あるモンスターに中心ダメージを何回与えるか
        tmp = ceil((HP-B*C)/(A-B))
        # オーバーキルの場合
        if tmp <= 0:
            break
        cnt += tmp
    return cnt <= C

ok = 10 ** 18
ng = 0
while ok - ng > 1:
    mid = (ok + ng) // 2
    if is_all_kill(mid):
        ok = mid
    else:
        ng = mid

print(ok)

Buggy python submission (verdict: Time Limit Exceeded):
from math import ceil

N,A,B = map(int,input().split())
h = [int(input()) for _ in range(N)]

# C回以下の爆発で倒せるか
def is_all_kill(C:int):
    cnt = 0
    for HP in h:
        # あるモンスターに中心ダメージを何回与えるか
        tmp = ceil((HP-B*C)/(A-B))
        # オーバーキルの場合
        if tmp <= 0:
            continue
        cnt += tmp
    return cnt <= C

ok = 10 ** 18
ng = 0
while ok - ng > 1:
    mid = (ok + ng) // 2
    if is_all_kill(mid):
        ok = mid
    else:
        ng = mid

print(ok)

Fixed submission:
from math import ceil

N,A,B = map(int,input().split())
h = sorted([int(input()) for _ in range(N)], reverse=True)

# C回以下の爆発で倒せるか
def is_all_kill(C:int):
    cnt = 0
    for HP in h:
        # あるモンスターに中心ダメージを何回与えるか
        tmp = ceil((HP-B*C)/(A-B))
        # オーバーキルの場合
        if tmp <= 0:
            break
        cnt += tmp
    return cnt <= C

ok = 10 ** 18
ng = 0
while ok - ng > 1:
    mid = (ok + ng) // 2
    if is_all_kill(mid):
        ok = mid
    else:
        ng = mid

print(ok)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict

N,W = map(int, input().split())
WV = [[int(i) for i in input().split()] for _ in range(N)]

w0 = WV[0][0]
for i in range(N):
    WV[i][0] -= w0

# (i, j, k): i番目まででj個選んで総重量がk以下のときの最大値
dp = defaultdict(lambda: -float("inf"))

# 初期条件
dp[(0, 0, 0)] = 0

# 配るDP
for i, (w, v) in enumerate(WV):
    for j in range(i + 1):
        for k in range(300):
            dp[(i + 1, j, k)] = max(dp[(i + 1, j, k)], dp[(i, j, k)])
            dp[(i + 1, j  + 1, k + w)] = max(dp[(i + 1, j  + 1, k + w)], dp[(i, j, k)] + v)

ans = 0
for j in range(N + 1):
    for k in range(300):
        if j * w0 + k <= W:
            ans = max(ans, dp[(N, j, k)])

print(ans)

Fixed submission:
import sys
input = sys.stdin.readline
from itertools import accumulate

N,W = map(int,input().split())
WV = [[int(i) for i in input().split()] for _ in range(N)]

MINW = WV[0][0]

W0 = sorted([0] + [v for w,v in WV if w == MINW])
W1 = sorted([0] + [v for w,v in WV if w == MINW+1])
W2 = sorted([0] + [v for w,v in WV if w == MINW+2])
W3 = sorted([0] + [v for w,v in WV if w == MINW+3])

W0 = tuple(accumulate(W0))
W1 = tuple(accumulate(W1))
W2 = tuple(accumulate(W2))
W3 = tuple(accumulate(W3))

ans = 0
for w0 in range(len(W0)):
    for w1 in range(len(W1)):
        for w2 in range(len(W2)):
            for w3 in range(len(W3)):
                tmp = (len(W0) - (w0 + 1)) * MINW
                tmp += (len(W1) - (w1 + 1)) * (MINW+1)
                tmp += (len(W2) - (w2 + 1)) * (MINW+2)
                tmp += (len(W3) - (w3 + 1)) * (MINW+3)

                if tmp <= W:
                    tmp = W0[-1] - W0[w0]
                    tmp += W1[-1] - W1[w1]
                    tmp += W2[-1] - W2[w2]
                    tmp += W3[-1] - W3[w3]
                    ans = max(ans, tmp)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

n = int(input())
a = [int(i) for i in input().split()]

# i番目までの和が正(i: 奇数)
res1 = 0
cum = 0
for i in range(n):
    cum += a[i]
    if i % 2 == 1:
        while cum <= 0:
            cum += 1
            res1 += 1
    else:
        while cum >= 0:
            cum -= 1
            res1 += 1

# i番目までの和が負(i: 奇数)
res2 = 0
cum = 0
for i in range(n):
    cum += a[i]
    if i % 2 == 0:
        while cum <= 0:
            cum += 1
            res2 += 1
    else:
        while cum >= 0:
            cum -= 1
            res2 += 1

print(min(res1,res2))

Fixed submission:
import sys
input = sys.stdin.readline

n = int(input())
a = [int(i) for i in input().split()]

# i番目までの和が正(i: 奇数)
res1 = 0
cum = 0
for i in range(n):
    cum += a[i]
    if i % 2 == 1:
        if cum <= 0:
            res1 += (1 - cum)
            cum = 1
    else:
        if cum >= 0:
            res1 += (cum + 1)
            cum = -1

# i番目までの和が正(i: 偶数)
res2 = 0
cum = 0
for i in range(n):
    cum += a[i]
    if i % 2 == 0:
        if cum <= 0:
            res2 += (1 - cum)
            cum = 1
    else:
        if cum >= 0:
            res2 += (cum + 1)
            cum = -1

print(min(res1,res2))