Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from itertools import combinations

# https://ikatakos.com/pot/programming_algorithm/data_structure/union_find_tree
class UnionFind:
    def __init__(self, n):
        # 負  : 根であることを示す。絶対値はランクを示す
        # 非負: 根でないことを示す。値は親を示す
        self.table = [-1] * n
        self.n = n
        self.max_inconvenience = n * (n - 1) // 2

    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

    def find(self, x, y):
        return self._root(x) == self._root(y)

    def inconvenience(self):
        res = self.max_inconvenience
        for i, j in combinations(range(self.n), 2):
            if self.find(i, j):
                res -= 1
        return res

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        # ランクの取得
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2


def main():
    input = sys.stdin.buffer.readline
    n, m = map(int, input().split())
    bridges = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(m)]
    ans = [0] * m
    ans[-1] = n * (n - 1) // 2
    uf = UnionFind(n)
    for i in range(m - 2, -1, -1):
        uf.union(*bridges[i + 1])
        ans[i] = uf.inconvenience()
    for i in range(m):
        print(ans[i])


if __name__ == "__main__":
    main()


Fixed submission:
import sys
from itertools import combinations

# https://ikatakos.com/pot/programming_algorithm/data_structure/union_find_tree
class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n
        self.n = n
        self.inconvenience = n * (n - 1) // 2

    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

    def find(self, x, y):
        return self._root(x) == self._root(y)

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        self.inconvenience -= d1 * d2
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1


def main():
    input = sys.stdin.buffer.readline
    n, m = map(int, input().split())
    bridges = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(m)]
    ans = [0] * m
    ans[-1] = n * (n - 1) // 2
    uf = UnionFind(n)
    for i in range(m - 2, -1, -1):
        uf.union(*bridges[i + 1])
        ans[i] = uf.inconvenience
    for i in range(m):
        print(ans[i])


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
H = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(m)]
ct = 0
for i in range(1, n + 1):
    high = H[i-1]
    flag = 0
    for j in range(m):
        if AB[j][0] == i:
            if H[AB[j][1] - 1] >= high:
                flag = 1
                break
        elif AB[j][1] == i:
            if H[AB[j][0] - 1] >= high:
                flag = 1
                break
    if flag == 0:
        ct += 1
print(ct)

Fixed submission:
n, m = map(int, input().split())
H = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(m)]
no = []
for i in AB:
    if H[i[0] - 1] > H[i[1] - 1]:
        no.append(i[1] - 1)
    elif H[i[0] - 1] < H[i[1] - 1]:
        no.append(i[0] - 1)
    else:
        no.append(i[1] - 1)
        no.append(i[0] - 1)
print(n - len(set(no)))

Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
H = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(m)]
ct = 0
for i in range(1, n + 1):
    high = H[i-1]
    flag = 0
    for j in range(m):
        if AB[j][0] == i:
            if H[AB[j][1] - 1] >= high:
                flag = 1
                break
        elif AB[j][1] == i:
            if H[AB[j][0] - 1] >= high:
                flag = 1
                break
    if flag == 0:
        ct += 1
print(ct)

Fixed submission:
n, m = map(int, input().split())
H = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(m)]
no = []
for i in AB:
    if H[i[0] - 1] > H[i[1] - 1]:
        no.append(i[1] - 1)
    elif H[i[0] - 1] < H[i[1] - 1]:
        no.append(i[0] - 1)
    else:
        no.append(i[1] - 1)
        no.append(i[0] - 1)
print(n - len(set(no)))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
A = list(map(int, input().split()))
ct = 0
for i in range(n):
    for j in range(i, n):
        if j - i == A[i] + A[j]:
            ct += 1
print(ct)

Fixed submission:
n = int(input())
A = list(map(int, input().split()))
dic = {}
ans = 0
for i in range(n):
    L = i + A[i]
    if L not in dic:
        dic[L] = 1
    else:
        dic[L] += 1
for j in range(n):
    R = j - A[j]
    if R in dic:
        ans += dic[R]
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
A = list(map(int, input().split()))
Am = sorted(A, reverse = True)
m = Am[0] + Am[1]
ct = 0
for i in range(n):
    for j in range(i, n):
        if j - i > m:
            break
        elif j - i == A[i] + A[j]:
            ct += 1
print(ct)

Fixed submission:
n = int(input())
A = list(map(int, input().split()))
dic = {}
ans = 0
for i in range(n):
    L = i + A[i]
    if L not in dic:
        dic[L] = 1
    else:
        dic[L] += 1
for j in range(n):
    R = j - A[j]
    if R in dic:
        ans += dic[R]
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
A = list(map(int, input().split()))
Am = sorted(A, reverse = True)
m = Am[0] + Am[1]
ct = 0
for i in range(n):
    for j in range(i, n):
        if j - i > m:
            break
        elif j - i == A[i] + A[j]:
            ct += 1
print(ct)

Fixed submission:
n = int(input())
A = list(map(int, input().split()))
dic = {}
ans = 0
for i in range(n):
    L = i + A[i]
    if L not in dic:
        dic[L] = 1
    else:
        dic[L] += 1
for j in range(n):
    R = j - A[j]
    if R in dic:
        ans += dic[R]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
a, b, n = map(int, input().split())
ans = 0
for x in range(1, min(b,n) + 1):
    fx = int(a*x/b) - a * int(x/b)
    if ans < fx:
        ans = fx
print(ans)

Fixed submission:
a, b, n = map(int, input().split())
y = 0
if n >= b:
    y = b - 1
else:
    y = n
print(int(a*y/b))

Buggy python submission (verdict: Time Limit Exceeded):
a, b, n = map(int, input().split())
ans = 0
for x in range(1, min(b,n) + 1):
    fx = int(a*x/b) - a * int(x/b)
    if ans < fx:
        ans = fx
print(ans)

Fixed submission:
a, b, n = map(int, input().split())
y = 0
if n >= b:
    y = b - 1
else:
    y = n
print(int(a*y/b))

Buggy python submission (verdict: Time Limit Exceeded):
a, b, n = map(int, input().split())
fx = [int(a*x/b) - a * int(x/b) for x in range(1, n+1)]
print(max(fx))

Fixed submission:
a, b, n = map(int, input().split())
y = 0
if n >= b:
    y = b - 1
else:
    y = n
print(int(a*y/b))

Buggy python submission (verdict: Time Limit Exceeded):
import math
a, b, n = map(int, input().split())
ans = -100
for x in range(1, n+1):
    fx = math.floor(a*x/b) - a * math.floor(x/b)
    if ans < fx:
        ans = fx
print(ans)

Fixed submission:
a, b, n = map(int, input().split())
y = 0
if n >= b:
    y = b - 1
else:
    y = n
print(int(a*y/b))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = [input() for _ in range(N)]
list = []
for i in range(N):
    if not S[i] in list:
        list.append(S[i])
print(len(list))

Fixed submission:
N = int(input())
S = [input() for _ in range(N)]
dict = {}
for i in range(N):
    if S[i] not in dict:
        dict[S[i]] = 1
print(len(dict))
Buggy python submission (verdict: Runtime Error):
S = list(input().split())
if S[2] == S[3] or S[4] == S[5]:
  print("Yes")
else:
  print("No")

Fixed submission:
S = input()
 
if S[2]==S[3] and S[4]==S[5]:
    print("Yes")
else:
    print("No")
Buggy python submission (verdict: Runtime Error):
K, N = int(input().split())
A = list(map(int, input().split()))
max = A[1] - A[0]
for i in range(1, N-1):
    if max < A[i+1] - A[i]:
        max = A[i+1] - A[i]
if max < K - A[N-1]:
    max = K - A[N+1]
print(K - max)

Fixed submission:
K,N = map(int,input().split())
A = list(map(int, input().split()))
max = K + A[0] - A[N-1]
for i in range(N-1):
    if max < A[i+1] - A[i]:
        max = A[i+1] - A[i]
print(K - max)
Buggy python submission (verdict: Runtime Error):
n = int(input())
A = []
X = []
for i in range(n):
    a = int(input())
    A.append(a)
    lis = []
    for j in range(a):
        lis.append(list(map(int, input().split())))
    X.append(lis)

ans = 0
for i in range(2 ** n):
    H_lis = [0 for i in range(n)]
    for j in range(n):
        if ((i >> j) & 1):
            H_lis[j] = 1
    flag = True
    j = 0
    while j < n and flag:
        if H_lis[j] == 1:
            for k in range(A[k]):
                if X[j][k][1] != H_lis[X[j][k][0] - 1]:
                    flag = False
                    break
        j += 1
    if flag:
        ans = max(ans, H_lis.count(1))
print(ans)

Fixed submission:
n = int(input())
A = []
X = []
for i in range(n):
    a = int(input())
    A.append(a)
    lis = []
    for j in range(a):
        lis.append(list(map(int, input().split())))
    X.append(lis)

ans = 0
for i in range(2 ** n):
    H_lis = [0 for i in range(n)]
    for j in range(n):
        if ((i >> j) & 1):
            H_lis[j] = 1
    flag = True
    j = 0
    while j < n and flag:
        if H_lis[j] == 1:
            for k in range(A[j]):
                if X[j][k][1] != H_lis[X[j][k][0] - 1]:
                    flag = False
                    break
        j += 1
    if flag:
        ans = max(ans, H_lis.count(1))
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s = input()

ans = 0

for i in range(1000):
    p100 = i // 100
    ki = i % 100
    p10  = ki // 10
    ki = ki % 10
    p1   = ki // 1
    j = 0
    flag = False
    while j < n:
        if flag:
            break
        if int(s[j]) == p100:
            j += 1
            while j < n:
                if flag:
                    break
                if int(s[j]) == p10:
                    j += 1
                    while j < n:
                        if flag:
                            break
                        if int(s[j]) == p1:
                            ans += 1
                            flag = True
                            break
                        else:
                            j += 1
                else:
                    j += 1
        else:
            j += 1
            
print(ans)

Fixed submission:
n = int(input())
S = input()
ct = 0

for i in range(10):
    if str(i) in S:
        p = S.index(str(i))
        Si = S[p+1 :]
        for j in range(10):
            if str(j) in Si:
                q = Si.index(str(j))
                Sj = Si[q+1 :]
                for k in range(10):
                    if str(k) in Sj:
                        ct += 1
print(ct)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s = input()

ans = 0

for i in range(1000):
    p100 = i // 100
    ki = i % 100
    p10  = ki // 10
    ki = ki % 10
    p1   = ki // 1
    flag1, flag2, flag3 = False, False, False
    for j in range(n):
        if (not flag1) and int(s[j]) == p100:
            flag1 = True
            continue
        if (not flag2) and flag1 and int(s[j]) == p10:
            flag2 = True
            continue
        if (not flag3) and flag1 and flag2 and int(s[j]) == p1:
            flag3 = True
            break
    if flag1 and flag2 and flag3:
        ans += 1

print(ans)

Fixed submission:
n = int(input())
S = input()
ct = 0

for i in range(10):
    if str(i) in S:
        p = S.index(str(i))
        Si = S[p+1 :]
        for j in range(10):
            if str(j) in Si:
                q = Si.index(str(j))
                Sj = Si[q+1 :]
                for k in range(10):
                    if str(k) in Sj:
                        ct += 1
print(ct)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
S = input()
D = {}
for i in range(n):
    for j in range(i+1, n):
        for k in range(j+1, n):
            Si = str(S[i] + S[j] + S[k])
            if (Si) not in D:
                D[Si] = 1
print(len(D))

Fixed submission:
n = int(input())
S = input()
ct = 0

for i in range(10):
    if str(i) in S:
        p = S.index(str(i))
        Si = S[p+1 :]
        for j in range(10):
            if str(j) in Si:
                q = Si.index(str(j))
                Sj = Si[q+1 :]
                for k in range(10):
                    if str(k) in Sj:
                        ct += 1
print(ct)
Buggy python submission (verdict: Time Limit Exceeded):
import sys

n, m = map(int, input().split())
A = []
for i in range(m):
    A.append(int(input()))
dp = [0] * (n+1)
mod = 1000000007
dp[0] = 1
if 1 in A:
    if 2 in A:
        print(0)
        sys.exit()
else:
    dp[1] = 1
for i in range(2, n+1):
    if i in A:
        dp[i] = 0
    else:
        dp[i] = (dp[i-1] + dp[i-2]) % mod
print(dp[-1])

Fixed submission:
n, m = map(int, input().split())
ct = [0] * (n+1)
A = [True] * n
for _ in range(m):
    A[int(input())-1] = False

ct[0] = 1
mod = 1000000007
for i in range(1, n+1):
    if A[i-2] == True:
        ct[i] += ct[i-1]
    if i > 1 and A[i-3] == True:
        ct[i] += ct[i-2]
    ct[i] %= mod
print(ct[-1])

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

n, m = map(int, input().split())
A = []
for i in range(m):
    A.append(int(input()))
dp = [0] * (n+1)
mod = 1000000007
dp[0] = 1
if 1 in A:
    if 2 in A:
        print(0)
        sys.exit()
else:
    dp[1] = 1
for i in range(2, n+1):
    if i in A:
        dp[i] = 0
    else:
        dp[i] = (dp[i-1] + dp[i-2]) % mod
print(dp[-1])

Fixed submission:
n, m = map(int, input().split())
ct = [0] * (n+1)
A = [True] * n
for _ in range(m):
    A[int(input())-1] = False

ct[0] = 1
mod = 1000000007
for i in range(1, n+1):
    if A[i-2] == True:
        ct[i] += ct[i-1]
    if i > 1 and A[i-3] == True:
        ct[i] += ct[i-2]
    ct[i] %= mod
print(ct[-1])
Buggy python submission (verdict: Runtime Error):
n, w = map(int, input().split())
W, V = [], []
for i in range(n):
    wi, vi = map(int, input().split())
    W.append(wi)
    V.append(vi)
    
# Dp[i][sum_w] := i-1 番目までの品物から重さがsum_wを超えないように選んだときの、価値の総和の最大値
Dp = [[0] * (w + 1) for _ in range(n+1)]

for i in range(n):
    for sum_w in range(w+1):
        # i番目の商品を選ぶ場合
        if sum_w - W[i] >= 0:
            Dp[i+1][sum_w] = max(Dp[i+1][sum_w], Dp[i][sum_w - W[i]] + V[i])
        # i番目の商品を選ばない場合
        Dp[i+1][sum_w] = max(Dp[i+1][sum_w], Dp[i][sum_w])
print(Dp[-1][-1])

Fixed submission:
n = int(input())
H = list(map(int, input().split()))

DP = [10 ** 9] * n
DP[0] = 0

for i in range(1, n):
    DP[i] = min(DP[i], DP[i-1] + abs(H[i] - H[i-1]))
    if i > 1:
        DP[i] = min(DP[i], DP[i-2] + abs(H[i] - H[i-2]))
print(DP[-1])

Buggy python submission (verdict: Runtime Error):
n = int(input())
DP = [[0] * 3 for _ in range(n+1)]
A = []
for i in range(n):
    A.append(list(map(int, input().split())))
for i in range(1, n+1):
    for j in range(0, 3):
        for k in range(0, 3):
            if j != k:
                DP[i][j] = max(DP[i][j], DP[i-1][k] + A[i-1][j])
print(max(DP[-1]))

Fixed submission:
n = int(input())
H = list(map(int, input().split()))

DP = [10 ** 9] * n
DP[0] = 0

for i in range(1, n):
    DP[i] = min(DP[i], DP[i-1] + abs(H[i] - H[i-1]))
    if i > 1:
        DP[i] = min(DP[i], DP[i-2] + abs(H[i] - H[i-2]))
print(DP[-1])
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
h = list(map(int, input().split()))

memo = [10**9] * n
memo[0] = 0

for i in range(1, n):
  for j in range(1, k+1):
    if i - j < 0:
      break
    else:
      memo[i] = min(memo[i], memo[i-j] + abs(h[i] - h[i-j]))

print(memo[-1])

Fixed submission:
n, k = map(int, input().split())
H = list(map(int, input().split()))

DP = [10 ** 9] * n
DP[0] = 0

for i in range(1, n):
    j = 1
    while i - j >= 0 and j <= k:
        DP[i] = min(DP[i], DP[i-j] + abs(H[i] - H[i-j]))
        j += 1
print(DP[-1])

Buggy python submission (verdict: Time Limit Exceeded):
n, k  = map(int, input().split())
H = list(map(int, input().split()))

memo = [10**9 for _ in range(n)]
memo[0] = 0
for i in range(1, n):
  for j in range(1, k+1):
    if i - j >= 0:
      memo[i] = min(memo[i], memo[i-j] + abs(H[i] - H[i-j]))
print(memo[-1])

Fixed submission:
n, k = map(int, input().split())
H = list(map(int, input().split()))

DP = [10 ** 9] * n
DP[0] = 0

for i in range(1, n):
    j = 1
    while i - j >= 0 and j <= k:
        DP[i] = min(DP[i], DP[i-j] + abs(H[i] - H[i-j]))
        j += 1
print(DP[-1])

Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
H = list(map(int, input().split()))

DP = [10 ** 9] * n
DP[0] = 0

for i in range(1, n):
    j = 1
    while i - j >= 0 and j <= k:
        DP[i] = min(DP[i], DP[i-j] + abs(H[i] - H[i-j]))
        j += 1
print(DP[-1])

Fixed submission:
n, k = map(int, input().split())
H = list(map(int, input().split()))

DP = [10 ** 9] * n
DP[0] = 0

for i in range(1, n):
    j = 1
    while i - j >= 0 and j <= k:
        DP[i] = min(DP[i], DP[i-j] + abs(H[i] - H[i-j]))
        j += 1
print(DP[-1])
Buggy python submission (verdict: Time Limit Exceeded):
n, w = map(int, input().split())
W, V = [], []
sum_w = 0
for i in range(n):
  wi, vi = map(int ,input().split())
  W.append(wi)
  V.append(vi)
  sum_w += wi

memo = [[0] * (w + 1) for _ in range(n+1)]

for i in range(n):
  for w_i in range(w + 1):
    memo[i+1][w_i] = max(memo[i+1][w_i], memo[i][w_i])
    if w_i - W[i] >= 0:
      memo[i+1][w_i] = max(memo[i+1][w_i], memo[i][w_i-W[i]] + V[i])
print(memo[-1][-1])

Fixed submission:
n, w = map(int, input().split())
W, V = [], []
for i in range(n):
    wi, vi = map(int, input().split())
    W.append(wi)
    V.append(vi)
    
# Dp[i][sum_w] := i-1 番目までの品物から重さがsum_wを超えないように選んだときの、価値の総和の最大値
Dp = [[0] * (w + 1) for _ in range(n+1)]

for i in range(n):
    for sum_w in range(w+1):
        # i番目の商品を選ぶ場合
        if sum_w - W[i] >= 0:
            Dp[i+1][sum_w] = max(Dp[i+1][sum_w], Dp[i][sum_w - W[i]] + V[i])
        # i番目の商品を選ばない場合
        Dp[i+1][sum_w] = max(Dp[i+1][sum_w], Dp[i][sum_w])
print(Dp[-1][-1])

Buggy python submission (verdict: Time Limit Exceeded):
n, w = map(int, input().split())
W, V = [], []
for i in range(n):
    wi, vi = map(int, input().split())
    W.append(wi)
    V.append(vi)
    
# Dp[i][sum_w] := i-1 番目までの品物から重さがsum_wを超えないように選んだときの、価値の総和の最大値
Dp = [[0] * (w + 1) for _ in range(n+1)]

for i in range(n):
    for sum_w in range(w+1):
        # i番目の商品を選ぶ場合
        if sum_w - W[i] >= 0:
            Dp[i+1][sum_w] = max(Dp[i+1][sum_w], Dp[i][sum_w - W[i]] + V[i])
        # i番目の商品を選ばない場合
        Dp[i+1][sum_w] = max(Dp[i+1][sum_w], Dp[i][sum_w])
print(Dp[-1][-1])

Fixed submission:
n, w = map(int, input().split())
W, V = [], []
for i in range(n):
    wi, vi = map(int, input().split())
    W.append(wi)
    V.append(vi)
    
# Dp[i][sum_w] := i-1 番目までの品物から重さがsum_wを超えないように選んだときの、価値の総和の最大値
Dp = [[0] * (w + 1) for _ in range(n+1)]

for i in range(n):
    for sum_w in range(w+1):
        # i番目の商品を選ぶ場合
        if sum_w - W[i] >= 0:
            Dp[i+1][sum_w] = max(Dp[i+1][sum_w], Dp[i][sum_w - W[i]] + V[i])
        # i番目の商品を選ばない場合
        Dp[i+1][sum_w] = max(Dp[i+1][sum_w], Dp[i][sum_w])
print(Dp[-1][-1])
Buggy python submission (verdict: Time Limit Exceeded):
n, w = map(int, input().split())
W, V = [], []
for i in range(n):
    wi, vi = map(int, input().split())
    W.append(wi)
    V.append(vi)

max_sumv = sum(V) 
# Dp[i][sum_v] := i-1 番目までの品物から価値がsum_v以上を達成するように選んだときの、重さの総和の最小値小値
dp = [[10 ** 9] * (max_sumv + 1) for _ in range(n+1)]

dp[0][0] = 0

for i in range(n):
    for sum_v in range(max_sumv + 1):
        # i番目の商品を選ぶ場合
        if sum_v - V[i] >= 0:
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v - V[i]] + W[i])
        # i番目の商品を選ばない場合
        dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])
ans = 0
for i in range(max_sumv + 1):
    if dp[n][i] <= w:
        ans = i
print(ans)

Fixed submission:
n, w = map(int, input().split())
W, V = [], []
for i in range(n):
    wi, vi = map(int, input().split())
    W.append(wi)
    V.append(vi)

max_sumv = sum(V) 
# Dp[i][sum_v] := i-1 番目までの品物から価値がsum_v以上を達成するように選んだときの、重さの総和の最小値小値
dp = [[10 ** 9] * (max_sumv + 1) for _ in range(n+1)]

dp[0][0] = 0

for i in range(n):
    for sum_v in range(max_sumv + 1):
        # i番目の商品を選ぶ場合
        if sum_v - V[i] >= 0:
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v - V[i]] + W[i])
        # i番目の商品を選ばない場合
        dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])
ans = 0
for i in range(max_sumv + 1):
    if dp[n][i] <= w:
        ans = i
print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
S = input()
if S[0] != 'A' or :
    print('WA')
    sys.exit()
    
n = len(S)
ct = 0
for i in range(1, n):
    if S[i].islower():
        if i == 1 or i == n - 1 or S[i] != 'C':
            print('WA')
            sys.exit()
        ct += 1
if ct == 1:
    print('AC')
else:
    print('WA')

Fixed submission:
import sys
S = input()
if S[0] != 'A':
    print('WA')
    sys.exit()
    
n = len(S)
ct = 0
for i in range(1, n):
    if S[i].islower() == False:
        if i == 1 or i == n - 1 or S[i] != 'C':
            print('WA')
            sys.exit()
        ct += 1
if ct == 1:
    print('AC')
else:
    print('WA')
Buggy python submission (verdict: Time Limit Exceeded):
q = int(input())

L = [True] * (10**5 + 1)

L[0], L[1] = False, False

for i in range(2, int((10**5) ** 0.5) + 1):
    if not L[i]:
        continue
    j = 2
    while i * j <= 10**5:
        L[i * j] = False
        j += 1

for i in range(q):
    l, r = map(int, input().split())
    ans = 0
    for j in range(l, r+1):
        if L[j] and L[(j + 1) // 2]:
            ans += 1
    print(ans)

Fixed submission:
q = int(input())

L = [True] * (10**5 + 1)

L[0], L[1] = False, False

for i in range(2, int((10**5) ** 0.5) + 1):
    if not L[i]:
        continue
    j = 2
    while i * j <= 10**5:
        L[i * j] = False
        j += 1

A = [0] * (10**5 + 1)
for i in range(1, 10**5 + 1):
    if L[i] and L[(i+1)//2]:
        A[i] = A[i-1] + 1
    else:
        A[i] = A[i-1]

for i in range(q):
    l, r = map(int, input().split())
    if l == r:
        if L[l] and L[(l+1)//2]:
            print(1)
        else:
            print(0)
    else:
        if L[l] and L[(l+1)//2]:
            print(A[r] - A[l-1])
        else:
            print(A[r] - A[l])
Buggy python submission (verdict: Time Limit Exceeded):
import bisect

n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort()
B.sort()
C.sort()
ct = 0
for i in C:
    b_max = bisect.bisect_left(B, i)
    for j in B[: b_max]:
        ct += bisect.bisect_left(A, j)
print(ct)

Fixed submission:
import bisect

n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort()
C.sort()
ct = 0
for j in B:
    a_max = bisect.bisect_left(A, j)
    c_min = bisect.bisect_right(C, j)
    ct += a_max * (n - c_min)
print(ct)
Buggy python submission (verdict: Time Limit Exceeded):
k, s = map(int, input().split())
ans = 0
for x in range(k+1):
  for y in range(k+1):
    for z in range(k+1):
      if x+y+z == s:
        ans += 1
print(ans)

Fixed submission:
k, s = map(int, input().split())
ct = 0
for x in range(0, k + 1):
    for y in range(0, k + 1):
        z = s - x - y 
        if z >= 0 and z <= k:
            ct += 1
print(ct)