Harryxun/GPT-100-sft-dataset huggingface dataset:
Problem p02678 (python)

Fixed submission:
from collections import deque

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

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

def bfs(u):
    
    q = deque()
    q.append(u)
    while q:
        r = q.popleft()
        for v in R[r]:
            if S[v] == -1:
                S[v] = r
                q.append(v)

S = [-1] * N
S[0] = 0

bfs(0)

print("Yes")
for i in range(1,N):
    print(S[i]+1)

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

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

from collections import deque
def bfs(u):
    
    q = deque()
    q.append(u)
    while q:
        r = q.pop()
        for v in R[r]:
            if V[v]:
                V[v] = False
                S[v] = r
                q.append(v)

bfs(0)
print("Yes")
for i in range(1,N):
    print(S[i]+1)

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

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

S = [-1] * N
S[0] = 0
NXT = [[] for _ in range(N)]  # 最大ステップ
NXT[0] = [0]

for s in range(N):
    for k in NXT[s]:  # sステップ目で到達
        for i in R[k]:
            if S[i] == -1:  # 未更新
                S[i] = k
                NXT[s+1].append(i)

    if S.count(-1) == 0:
        break

print("Yes")
for i in range(1,N):
    print(S[i]+1)
Problem p02684 (python)

Fixed submission:
N, K = map(int, input().split())
A = [int(x) - 1 for x in input().split()]

# 最初のループを回るまで
loop = 0
city = 0
b = set([0])
while True:
    loop += 1
    if A[city] in b:
        break
    else:
        city = A[city]
        b.add(city)

loop_start = A[city]

# ループの始点にたどり着くまで
pre = 0
city = 0
while True:
    pre += 1
    if A[city] == loop_start:
        break
    else:
        city = A[city]

if loop > pre:
    loop -= pre

if K < pre:  # ループに入る前に終了の場合
    city = 0
    for i in range(K):
        city = A[city]
    print(city + 1)
    
else:  # ループに入って終了
    K -= pre
    last = K % loop
    city = loop_start
    
    for i in range(last):
        city = A[city]
    print(city + 1)

Buggy submission (verdict: Runtime Error):
N, K = map(int, input().split())
A = [int(x) - 1 for x in input().split()]

# 最初のループを回るまで
loop = 0
city = 0
b = set([0])
while True:
    loop += 1
    if A[city] in b:
        break
    else:
        city = A[city]
        b.add(city)

loop_start = A[city]

# ループの始点にたどり着くまで
pre = 0
city = 0
while True:
    pre += 1
    if A[city] == loop_start:
        break
    else:
        city = A[city]

if loop > pre:
    loop -= pre

if K < c:  # ループに入る前に終了の場合
    city = 0
    for i in range(K):
        city = A[city]
    print(city + 1)
    
else:  # ループに入って終了
    K -= pre
    last = K % loop
    city = loop_start
    
    for i in range(last):
        city = A[city]
    print(city + 1)
Problem p02686 (python)

Fixed submission:
# 入力
N = int(input())

S1 = [] # 増えるシーケンス用
S2 = [] # 減るシーケンス用

# 入力その２
for i in range(N):

    S = input()  # シーケンス
    mid, end = 0, 0    

    for s in S:
        if s == '(':
            end += 1
        else:
            end -= 1
            
        mid = min(mid, end)  # 途中経過で一番減るところを探す

    if end > 0:
        S1.append((mid, end))
    else:
        S2.append((mid-end, -end))

S1.sort(reverse=True)
# S2.sort(key = lambda x : (x[0], -x[1]))
S2.sort(reverse=True)


mid = end1 = 0  # スタート
out = False

for t in S1:
    a, b = t
    mid = end1 + a
    end1 = end1 + b
    if mid < 0 or end1 < 0:  # 途中で左カッコの数が右を上回る
        out = True
        break

mid = end2 = 0  # スタート
for t in S2:
    a, b = t
    mid = end2 + a
    end2 = end2 + b
    if mid < 0 or end2 < 0:  # 途中で左カッコの数が右を上回る
        out = True
        break
        
if (not end1 == end2) or out:  # 右、左 の数が合わない
    print('No')
else:
    print('Yes')

Buggy submission (verdict: Runtime Error):
import sys

input = lambda : sys.stdin.readline

# 入力
N = int(input())

S1 = [] # 増えるシーケンス用
S2 = [] # 減るシーケンス用

# 入力その２
for i in range(N):

    S = input()  # シーケンス
    mid, end = 0, 0    

    for s in S:
        if s == '(':
            end += 1
        else:
            end -= 1
            
        mid = min(mid, end)  # 途中経過で一番減るところを探す

    if end > 0:
        S1.append((mid, end))
    else:
        S2.append((mid-end, -end))

S1.sort(reverse=True)
# S2.sort(key = lambda x : (x[0], -x[1]))
S2.sort(reverse=True)


mid = end1 = 0  # スタート
out = False

for t in S1:
    a, b = t
    mid = end1 + a
    end1 = end1 + b
    if mid < 0 or end1 < 0:  # 途中で左カッコの数が右を上回る
        out = True
        break

mid = end2 = 0  # スタート
for t in S2:
    a, b = t
    mid = end2 + a
    end2 = end2 + b
    if mid < 0 or end2 < 0:  # 途中で左カッコの数が右を上回る
        out = True
        break
        
if (not end1 == end2) or out:  # 右、左 の数が合わない
    print('No')
else:
    print('Yes')
Problem p02690 (python)

Fixed submission:
X = int(input())
for a in range(10**4):
    for b in range(-10**4,10**4):
        if a**5 - b**5 == X:
            print(a,b)
            break
    else:
        continue
    break

Buggy submission (verdict: Runtime Error):
x = int(input())
for a in range(10**4):
    for b in range(-10**4,10**4):
        if a**5 - b**5 == X:
            print(a,b)
            break
    else:
        continue
    break

Buggy submission (verdict: Runtime Error):
x = int(input())
for a in range(100):
    for b in range(-100,100):
        if a**5 - b**5 == X:
            print(a,b)
            break
    else:
        continue
    break
Problem p02709 (python)

Fixed submission:
#  入力
N = int(input())
A = [int(x) for x in input().split()]

# 初期化
dp = [[0] * (N+1) for _ in range(N+1)]
dp[0][0] = 0

for i in range(0,N):

    # 最も嬉しさの高い子供から場所を選択していく
    a = max(A)
    id = A.index(a)
    
    for x in range(0,i+1):
        y = i - x

        d = dp[x][y]
        tmp = d + a * (id - x)
        if dp[x+1][y] < tmp:
        	dp[x+1][y] = tmp
        tmp = d + a * (((N-1)-y) - id)            
        if dp[x][y+1] < tmp:
        	dp[x][y+1] = tmp
        
    A[id] = 0

ans = 0
for i in range(N+1):
    ans = max(ans, dp[i][N-i])
print(ans)

Buggy submission (verdict: Runtime Error):
#  入力
N = int(input())
B = [int(x) for x in input().split()]

# 初期化
dp = [[0] * (N+1) for _ in range(N+1)]
dp[0][0] = 0

for i in range(0,N):

    # 最も嬉しさの高い子供から場所を選択していく
    id = A.index(max(A))
    
    for x in range(0,i+1):
        y = i - x
        
        dp[x+1][y] = max(dp[x+1][y], dp[x][y] + A[id] * (id - x))
        dp[x][y+1] = max(dp[x][y+1], dp[x][y] + A[id] * (((N-1)-y) - id))
        
    A[id] = 0

ans = 0
for i in range(N+1):
    ans = max(ans, dp[i][N-i])
print(ans)
Problem p02713 (python)

Fixed submission:
import collections

def gcd(a,b):
    if a < b:
        a, b = b, a
    q = a // b
    r = a - q * b
    if r == 0:
        return b
    else:
        return gcd(b,r)

K = int(input())

a = []

for i in range(1,K+1):
    for j in range(1, K+1):
        a.append(gcd(i,j))
        
col = collections.Counter(a)

sum = 0
for k in range(1, K+1):
    for key, value in col.items():
         sum += gcd(k, key) * value
print(sum)

Buggy submission (verdict: Runtime Error):
import collections

K = int(input())

a = []
for i in range(1,K+1):
    for j in range(1, K+1):
        a.append(gcd(i,j))
        
col = collections.Counter(a)

sum = 0
for k in range(1, K+1):
    for key, value in col.items():
         sum += gcd(k, key) * value
print(sum)
Problem p02714 (python)

Fixed submission:
from collections import Counter

N = int(input())
S = input()

r = S.count('R')
g = S.count('G')
b = S.count('B')

sum = r*g*b

for i in range(N):
    for j in range(i+1, N):
        k = 2 * j - i
        if k > N - 1:
            break
        if not S[i] == S[j] and not S[j] == S[k] and not S[k] == S[i]:
            sum -= 1
print(sum)

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

N = int(input())
S = input()

r = S.count('R')
g = S.count('G')
b = S.count('B')

sum = r*g*b

for i in range(N):
    for j in range(i+1, N):
        k = 2 * j - i
        if not S[i] == S[j] and not S[j] == S[k] and not S[k] == S[i]:
            sum -= 1
print(sum)

Buggy submission (verdict: Runtime Error):
N = int(input())
S = input()

sum = 0
for i in range(N):
    for j in range(i+1, N):
        if S[i] == S[j]:
            continue

        RGB = ['R','G','B']
            RGB.remove(S[j])
            RGB.remove(S[i])
            sum += S[(j+1):].count(RGB[0])

            # S[k]
            k = 2 * j - i
            if k < len(S):
                if S[k] == RGB[0]:
                    sum -= 1
print(sum)
Problem p02716 (python)

Fixed submission:
N = int(input())
A = [int(x) for x in input().split()]

dp = [[0]*3]*N

dp[0][0] = 0  # ((i+1)-1)/2
dp[0][1] = 0 # (i+1)/2
dp[0][2] = A[0]  # ((i+1)+1)/2

for i in range(1, N):
    
    if i % 2 == 0:
        dp[i][0] = dp[i-1][0] + A[i]
        dp[i][1] = max(dp[i-1][1], dp[i-1][2])
        dp[i][2] = dp[i-1][2] + A[i]
    else:
        dp[i][0] = max(dp[i-1][0], dp[i-1][1])
        dp[i][1] = dp[i-1][1] + A[i]
        dp[i][2] = dp[i-1][2]

if N % 2 == 0:
    print(max(dp[N-1][1],dp[N-1][2]))
else:
    print(max(dp[N-1][0],dp[N-1][1]))

Buggy submission (verdict: Runtime Error):
N = int(input())
A = [int(x) for x in input().split()]

m = -10**9

if N % 2 == 0:
    a = sum(A)
    m = max(sum(A[0::2]), sum(A[1::2]))
else:
    for i in range(N):
        B = A.copy()
        del B[i]
        print(B[:i],B[i:])
        tmp1 = max(sum(B[0:i:2]),sum(B[1:i:2]))
        tmp2 = max(sum(B[i::2]),sum(B[i+1::2]))
        
        tmp = tmp1 + tmp2
        m = max(m,tmp)
        
print(m)
Problem p02721 (python)

Fixed submission:
N, K, C = map(int, input().split())
S = input()

Sr = "".join(list(reversed(S)))

wd = []
wdl = []

pw = 0
pwl = 0

for d in range(K):

    # 先詰めを探す
    while True:
        if S[pw] == ('o'):
            wd.append(pw)
            break
        pw += 1
    pw += C + 1
    
    # 後詰めを探す
    while True:
        if Sr[pwl] == ('o'):
            wdl.append((N-1) - pwl)
            break
        pwl += 1
    pwl += C + 1

wdl.sort()
    
for i in range(K):
    if wd[i] == wdl[i]:
        print(wd[i] + 1)

Buggy submission (verdict: Runtime Error):
N, K, C = map(int, input().split())
S = input()

Sr = "".join(list(reversed(S)))

wd = []
wdl = []

pw = 0
pwl = 0

for d in range(K):

    # 先詰めを探す
    while True:
        if S[pw] == ('o'):
            wd.append(pw)
            break
        pw += 1
    pw += C + 1
    
    # 後詰めを探す
    while True:
        if Sr[pwl] == ('o'):
            wdl.append(pwl)
            break
        pwl += 1
    pwl += C + 1

en = time.time()

wdl.sort()
    
for i in range(K):
    if wd[i] == wdl[i]:
        print(wd[i] + 1)
Problem p02722 (python)

Fixed submission:
import math

N = int(input())

# 割れるだけ割る
KMAX = math.floor(math.sqrt(N)) + 1

Kn = [N]  # N の約数であるような K
Kn1 = [N-1]  # N - 1 の約数であるような K

# N の約数であるような K (Kn)を求める
for K in range(2,KMAX):
    
    if N % K == 0:
        Kn.append(K)
        tmp = N//K
        if tmp == K:
            continue
        Kn.append(N//K)
        
Knn = []

# Kn のうち、割れるだけ割った(tN)あと、tN mod Kn == 1 であるような Kn
for K in Kn:
    tN = N
    while tN % K == 0:
        tN = tN // K  # K で割れなくなるまで割る
    
    if (tN - 1) % K == 0:
        Knn.append(K)
        
# N-1 の約数であるような K を求める
for K in range(2,KMAX):

    if (N - 1) % K == 0:
        Kn1.append(K)
        tmp = (N-1) // K
        if tmp == K:
            continue
        Kn1.append(tmp)

Knn.extend(Kn1)
if 1 in Knn:
    Knn.remove(1)
print(len(Knn))

Buggy submission (verdict: Runtime Error):
import math

N = int(input())

# 割れるだけ割る
KMAX = math.floor(math.sqrt(N)) + 1

Kn = [N]  # N の約数であるような K
Kn1 = [N-1]  # N - 1 の約数であるような K

# N の約数であるような K (Kn)を求める
for K in range(2,KMAX):
    
    if N % K == 0:
        Kn.append(K)
        tmp = N//K
        if tmp == K:
            continue
        Kn.append(N//K)
        
Knn = []

# Kn のうち、割れるだけ割った(tN)あと、tN mod Kn == 1 であるような Kn
for K in Kn:
    tN = N
    while tN % K == 0:
        tN = tN // K  # K で割れなくなるまで割る
    
    if (tN - 1) % K == 0:
        Knn.append(K)
        
# N-1 の約数であるような K を求める
for K in range(2,KMAX):

    if (N - 1) % K == 0:
        Kn1.append(K)
        tmp = (N-1) // K
        if tmp == K:
            continue
        Kn1.append(tmp)

Knn.extend(Kn1)
Knn.remove(1)
print(len(Knn))

Buggy submission (verdict: Runtime Error):
N = int(input())

KMAX = math.floor(math.sqrt(N)) + 1
# KMAX = 1000

Kn = [N]  # N の約数であるような K
Kn1 = [N-1]  # N - 1 の約数であるような K

# N の約数であるような K (Kn)を求める
for K in range(2,KMAX):
    
    if N % K == 0:
        Kn.append(K)
        tmp = N//K
        if tmp == K:
            continue
        Kn.append(N//K)
        
Knn = []

# Kn のうち、割れるだけ割った(tN)あと、tN mod Kn == 1 であるような Kn
for K in Kn:
    tN = N
    while tN % K == 0:
        tN = tN // K  # K で割れなくなるまで割る
    
    if (tN - 1) % K == 0:
        Knn.append(K)
        
# N-1 の約数であるような K を求める
for K in range(2,KMAX):

    if (N - 1) % K == 0:
        Kn1.append(K)
        tmp = (N-1) // K
        if tmp == K:
            continue
        Kn1.append(tmp)

Knn.extend(Kn1)
print(len(Knn))
# print(sorted(Knn))
Problem p02727 (python)

Fixed submission:
X, Y, A, B, C = map(int, input().split())

p = [int(x) for x in input().split()]
q = [int(x) for x in input().split()]
r = [int(x) for x in input().split()]

p.sort(reverse=True)
q.sort(reverse=True)
r.sort(reverse=True)

apples = []
apples.extend(p[:X])
apples.extend(q[:Y])

apples.sort(reverse=True)
apples.extend(r)

apples.sort(reverse=True)
print(sum(apples[:(X+Y)]))

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**6)

# 組み合わせ
mod = 10 ** 9 + 7
N = 2* 10 ** 5  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)

def cmb(n, r):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % mod
  
# 深さ優先探索
def dfs(v, p=-1):

    # print(v, p, [x + 1 for x in E[v]])
    
    dp_l = 1  # 自分自身しかない場合
    size_l = 1 # 自分自身のサイズを含める

    # 子の情報をあわせて数え上げる
    for u in E[v]:
        
        # 親へのルートは辿らない
        if u == p:
            continue

        d, s = dfs(u, v)
        d %= mod
        size_l += s
        dp_l = dp_l * d * cmb(size_l-1, s) % mod

    dp[v] = dp_l
    size[v] = size_l
        
    return (int(dp_l), size_l)
  
def bfs(v, p=-1):
    
    for u in E[v]:
        if u == p:
            continue
        
        # u がなくなった場合の dp[v] 値、 size を求める
        # 一旦、uを切り離す

        partial_v = int(dp[v] / dp[u] / cmb(N - 1, size[u]))
        
        # u に v 側の部分木が接続された場合の値を求める
        # u に v を根とする部分木をつける

        dp_l = dp[u] * partial_v * cmb(N-1, size[u]-1)
        
        dp[u] = dp_l
    
        bfs(u,v)

# 入力処理
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)
      
dp = [1] * N
size = [1] * N


dfs(0)

bfs(0)

for i in range(N):
    print(dp[i])
Problem p02732 (python)

Fixed submission:
import collections as c

# 入力
N = int(input())
An = [int(x) for x in input().split()]
 
# 各数字の個数を求める
Cn = c.Counter(An)
 
# 全部の組み合わせ
s = 0
for v in Cn.values():
    s += int(v*(v-1) / 2)

for i in range(0,N):
    print(s - (Cn[An[i]] - 1))

Buggy submission (verdict: Runtime Error):
from scipy.special import comb

N = int(input())
An = [int(x) for x in input().split()]  
Cn = [An.count(i) for i in range(1,N+1)]  # どの数字が何個あるか？

# ボールを全部使えるときの合計を求める
s = 0
for i in range(N):
    if Cn[i] > 1:
        s += int(comb(Cn[i],2))

for k in range(N):
    print(s - (Cn[An[k]-1]-1))

Buggy submission (verdict: Runtime Error):
import math

N = int(input())
An = [int(x) for x in input().split()]
 
L = [0,0]
for i in range(N):
    if i > 1:
        L.append(int(math.factorial(i) / (math.factorial(i-2) * 2)))

Cn = [An.count(i) for i in range(1,N+1)]
s = sum([L[Cn[i]] for i in range(N)])

for k in range(N):
    print(sum(Dn) - (Cn[An[k]-1]-1))

Buggy submission (verdict: Runtime Error):
N = int(input())
An = [int(x) for x in input().split()]
 
L = [0,0]
for i in range(N):
    if i > 1:
        L.append(int(math.factorial(i) / (math.factorial(i-2) * 2)))

Cn = [An.count(i) for i in range(1,N+1)]
s = sum([L[Cn[i]] for i in range(N)])

for k in range(N):
    print(sum(Dn) - (Cn[An[k]-1]-1))

Buggy submission (verdict: Runtime Error):
N = int(input())
An = [int(x) for x in input().split()]

L = [0,0]
for i in range(N):
    if i > 1:
        L.append(int(math.factorial(i) / (math.factorial(i-2) * 2)))

for k in range(N):
    Bn = [An[i] for i in range(N) if not i == k]
    Cn = [Bn.count(i) for i in range(N)]
    Dn = [Cn.count(i)*L[i] for i in range(N)] 
    
    print(sum(Dn))

Buggy submission (verdict: Runtime Error):
import copy

N = int(input())
An = [int(x) for x in input().split()]

for i in range(N):
    tmp = copy.copy(An)
    tmp.pop(i)
    
    c = 0
    for i in range(N):
        k = tmp.count(i)
        if k>1:
            c += int(math.factorial(k) / (math.factorial(k-2) * 2))
    print(c)
Problem p02755 (python)

Fixed submission:
import math

A, B = map(int, input().split())

priceA1 = math.ceil(A / 0.08)
priceA2 = (A+1) / 0.08
priceB1 = math.ceil(B / 0.10)
priceB2 = (B+1) / 0.10

if math.floor(priceA2) < priceA2:
    priceA2 = math.floor(priceA2)
else:
    priceA2 = math.floor(priceA2) - 1


if math.floor(priceB2) < priceB2:
    priceB2 = math.floor(priceB2)
else:
    priceB2 = math.floor(priceB2) - 1

if priceA1 <= priceB1 <= priceA2:
    print(math.ceil(priceB1))
elif math.ceil(priceB1) < math.ceil(priceA1) < priceB2:
    print(math.ceil(priceA1))
elif math.ceil(priceA1) == math.ceil(priceB1):
    print(math.ceil(priceA1))
else:
    print(-1)

Buggy submission (verdict: Runtime Error):
import math

A, B = map(int, input().split())
 
priceA1 = A / 0.08
priceA2 = (A+1) / 0.08
priceB1 = B / 0.10
priceB2 = (B+1) / 0.10

if priceA1 <= math.ceil(priceB1) <= math.floor(priceA2):
    print(math.ceil(priceB1,0))
elif priceB1 <= math.ceil(priceA1) <= math.floor(priceB2):
    print(math.ceil(priceA1))
else:
    print(-1)

Buggy submission (verdict: Runtime Error):
import math

A, B = map(int, input().split())
 
priceA1 = A / 0.08
priceA2 = (A+1) / 0.08
priceB1 = B / 0.10
priceB2 = (B+1) / 0.10

if priceA1 < math.ceil(priceB1) <= math.floor(priceA2):
    print(math.floor(priceB1,0))
elif priceB1 <= math.ceil(priceA1) <= math.floor(priceB2):
    print(int(priceA1))
else:
    print(-1)

Buggy submission (verdict: Runtime Error):
A, B = map(int, input().split())
 
priceA1 = A / 0.08
priceA2 = (A+1) / 0.08
priceB1 = B / 0.10
priceB2 = (B+1) / 0.10

if priceA1 <= priceB1 < priceA2:
    print(int(priceB))
elif priceB1 <= priceA1 < priceB2:
    print(int(priceA))
else:
    print(-1)
Problem p02756 (python)

Fixed submission:
S = input()
Q = int(input())

jun = True
head = ""

for _ in range(Q):
    T = input().split()
    if T[0] == "1":
        jun = not jun
    
    else:

        if (T[1] == "1" and jun) or (T[1] == "2" and not jun):
            head += T[2]
            continue

        else:
            S += T[2]

if jun:
    print(head[::-1] + S)
else:
    print(S[::-1] + head)

Buggy submission (verdict: Runtime Error):
S = input()
Q = int(input())

jun = True

for _ in range(Q):
    T = input().split()
    if T[0] == "1":
        jun = not jun
    
    else:

        if (T[1] == "1" and jun) or (T[1] == "2" and not jun):
            S = T[2] + S
            continue

        else:
            (T[1] == "2" and jun) or (T[1] == "1" and not jun):
            S = S + T[2]

if jun:
    print(S)
else:
    print(S[::-1])
Problem p02787 (python)

Fixed submission:
import sys

H, N = map(int, input().split())
A = [0] * N
B = [0] * N

for i in range(N):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    A[i] = a
    B[i] = b

max_A = max(A)
INF = 10**18
dp = [INF] * (H + max_A)
dp[0] = 0

for i in range(H):
    for j in range(N):
        dp[i + A[j]] = min(dp[i] + B[j], dp[i + A[j]])

print(min(dp[H:H + max_A]))

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

h, n = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
np_ab = np.array(ab)

max_a = max(np_ab[:, 0])
dp = [0] * (h + max_a)

for i in range(1, h + max_a):
    dp[i] = min(dp[i - a] + b for a, b in ab)

print(dp[h])
Problem p02821 (python)

Fixed submission:
import sys
import numpy as np

# 価値 x 以上の握手を全て行うとする
# 握手回数が決まる。左手ごとに集計できる。

N, M = map(int, sys.stdin.readline().rstrip().split())
A = np.array(sys.stdin.readline().rstrip().split(), np.int64)

A.sort()  # A を昇順に並び替える

# x より価値が高くなる握手の総数
#  -> a に対して、相手は x - a が必要
#   -> A = [a0, a1, a2, ...] に対して、[x-a0の開始位置, x-a1の開始位置, x-a2の開始位置,...] を探す
def shake_cnt(x):
    # x 以上の握手を全て行うとして、握手の回数を数える行わない握手を数える
    X = np.searchsorted(A, x - A)  # ソートされたリストA に対して、x - A が挿入される位置を返す
    return N * N - X.sum()  # index の和は「小さい方」を指しているので、引く


# 二分探索  握手の回数が
left = 0  # 握手の回数がM以上
right = 10 ** 6  # 握手の回数がM未満 <- まだ足りない側
while 1 < right - left:  # left と right が隣り合ったら終了
    x = (left + right) // 2
    if shake_cnt(x) >= M:
        left = x
    else:
        right = x

# M回には届かないけれど、M回に限りなく近くなる価値 x = right
X = np.searchsorted(A, right - A)  # 各a in A が握手を行わない人数のArray
shake = N * N - X.sum()  # ここまでの握手回数

Acum = np.zeros(N + 1, np.int64)  # 人数 -> 累積和
# Acum = [a0, a0+a1, a0+a1+a2, ....] を計算して、ai さんが k番目以降と握手をすれば
Acum[1:] = np.cumsum(A)  # cumsum [1,2,3,4,5,6,...] -> [1,3,6,10,15,21,...]

# 右手の幸福度は ai * ((a0+a1+...a(n-1)) - (a(k-1)+...+a(n-1))) を得られる
# 左手の幸福度は 回数だけで決まる（何人と握手とするか）
happy = (Acum[-1] - Acum[X]).sum() + (A * (N - X)).sum()

happy += (M - shake) * left  # 不足分。1回の価値は M とわかっている

print(happy)

Buggy submission (verdict: Runtime Error):
import sys

# 価値 x 以上の握手を全て行うとする
# 握手回数が決まる。左手ごとに集計できる。

import numpy as np

N, M = map(int, sys.stdin.readline().rstrip().split())
A = np.array(int(x) for x in sys.stdin.readline().rstrip().split())

A.sort()  # A を昇順に並び替える


# x より価値が高くなる握手の総数
#  -> a に対して、相手は x - a が必要
#   -> A = [a0, a1, a2, ...] に対して、[x-a0の開始位置, x-a1の開始位置, x-a2の開始位置,...] を探す
def shake_cnt(x):
    # x 以上の握手を全て行うとして、握手の回数を数える行わない握手を数える
    X = np.searchsorted(A, x - A)  # ソートされたリストA に対して、x - A が挿入される位置を返す
    return N * N - X.sum()  # index の和は「小さい方」を指しているので、引く


# 二分探索  握手の回数が
left = 0  # 握手の回数がM以上
right = 10 ** 6  # 握手の回数がM未満 <- まだ足りない側
while 1 < right - left:  # left と right が隣り合ったら終了
    x = (left + right) // 2
    if shake_cnt(x) >= M:
        left = x
    else:
        right = x

# M回には届かないけれど、M回に限りなく近くなる価値 x = right
X = np.searchsorted(A, right - A)  # 各a in A が握手を行わない人数のArray
shake = N * N - X.sum()  # ここまでの握手回数

Acum = np.zeros(N + 1, np.int64)  # 人数 -> 累積和
# Acum = [a0, a0+a1, a0+a1+a2, ....] を計算して、ai さんが k番目以降と握手をすれば
Acum[1:] = np.cumsum(A)  # cumsum [1,2,3,4,5,6,...] -> [1,3,6,10,15,21,...]

# 右手の幸福度は ai * ((a0+a1+...a(n-1)) - (a(k-1)+...+a(n-1))) を得られる
# 左手の幸福度は 回数だけで決まる（何人と握手とするか）
happy = (Acum[-1] - Acum[X]).sum() + (A * (N - X)).sum()

happy += (M - shake) * left  # 不足分。1回の価値は M とわかっている

print(happy)