Harryxun/testdata huggingface dataset:
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):
        if x + y > S:
            break
        for z in range(K+1):
            if x + y + z > S:
                break

            if x + y + z == S:
                ans += 1

print(ans)

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

ans = 0
for x in range(K+1):
    for y in range(K+1):
        x_y = x + y
        if x_y > S:
            break
        if S - x_y <= K:
            ans += 1

print(ans)

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):
        if x + y > S:
            break
        for z in range(K+1):
            if x + y + z == S:
                ans += 1

print(ans)

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

ans = 0
for x in range(K+1):
    for y in range(K+1):
        x_y = x + y
        if x_y > S:
            break
        if S - x_y <= K:
            ans += 1

print(ans)

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())

ans = 0
for x in range(K+1):
    for y in range(K+1):
        x_y = x + y
        if x_y > S:
            break
        if S - x_y <= K:
            ans += 1

print(ans)
Buggy python submission (verdict: Runtime Error):
N,M = map(int,input())

if N>=2:
  gyu = N*(N-1)//2
else:
  gyu = 0
  
if M>=2:
  ki = M*(M-1)//2
else:
  ki = 0

print(gyu+ki)

Fixed submission:
N,M = map(int,input().split())
 
if N>=2:
  gyu = N*(N-1)//2
else:
  gyu = 0
  
if M>=2:
  ki = M*(M-1)//2
else:
  ki = 0
 
print(gyu+ki)
Buggy python submission (verdict: Runtime Error):
N=int(input())

print(N//2+(if N%2!=0))

Fixed submission:
N=int(input())
 
print(N//2+(N%2!=0))
Buggy python submission (verdict: Runtime Error):
N,R = map(int,input().split())

if N<10:
  print(100*(10-K))
else:
  print(R)

Fixed submission:
N,R = map(int,input().split())
 
if N<10:
  print(R+100*(10-N))
else:
  print(R)
Buggy python submission (verdict: Runtime Error):
N,M = map(int,input())

print("Yes") if N==M else print("No")

Fixed submission:
N,M = map(int,input().split())
 
print("Yes") if N==M else print("No")
Buggy python submission (verdict: Runtime Error):
C = input()

print(char(ord(C)+1))

Fixed submission:
C = input()
 
print(chr(ord(C)+1))
Buggy python submission (verdict: Runtime Error):
from collections import Counter as C

S = input()

c = C(S)
if len(c.keys())==2:
  if c.values[0]==2:
    print("Yes")
  else:
    print("No")
else:
  print("No")

Fixed submission:
from collections import Counter as C
 
S = input()
 
c = C(S)
if len(c.keys())==2:
  if list(c.values())[0]==2:
    print("Yes")
  else:
    print("No")
else:
  print("No")
Buggy python submission (verdict: Runtime Error):
N,K = map(int,input().split())
S = input()

S[K-1]=S[k-1].lower()
print(S)

Fixed submission:
N,K = map(int,input().split())
S = list(input())
 
S[K-1]=S[K-1].lower()
print("".join(S))
Buggy python submission (verdict: Runtime Error):
antena = []
for i in range(5):
  antena[i] = int(input())
  
k = int(input())

for i in range(len(antena)):
  if antena[-1]-antena[i]>k:
    print(":(")
else:
  print("Yay!")

Fixed submission:
antena = [0]*5
for i in range(5):
  antena[i] = int(input())
  
k = int(input())
 
for i in range(len(antena)):
  if antena[-1]-antena[i]>k:
    print(":(")
    break
else:
  print("Yay!")
Buggy python submission (verdict: Runtime Error):
T,X = map(int,input())

print(T/X)

Fixed submission:
T,X = map(int,input().split())

print(T/X)
Buggy python submission (verdict: Runtime Error):
K = int(input())

ev = K//2
odd = k//2 + K%2
print(ev*odd)

Fixed submission:
K = int(input())
 
ev = K//2
odd = K//2 + K%2
print(ev*odd)
Buggy python submission (verdict: Runtime Error):
def calculate(s,t):
  count = 0
  for i in t:
    if i != s[j]:
      count += 1
    j += 1
  return count  


s = raw_input()
t = raw_input()
print(calculate(s,t))

Fixed submission:
def calculate(s,t):
    count = 0
    j = 0
    for i in s:
        if i != t[j]:
            count += 1
        j += 1
    return count
    
s = input()
t = input()
print(calculate(s,t))
Buggy python submission (verdict: Time Limit Exceeded):
import math
def main():
    A,B,N = map(int, input().split())

    max1 = 0
    k1 = math.ceil(B/A)
    k2 = B+1 if B<N else N+1
    for x in range(k1,k2):
        tmp = int(A*x/B) - A*int(x/B)
        max1 = max(max1,tmp)
    print(max1)

main()


Fixed submission:
def main():
    A,B,N = map(int, input().split())

    x = min(B-1,N)
    max1 = int(A*x/B) - A*int(x/B)
    print(max1)

main()

Buggy python submission (verdict: Time Limit Exceeded):
import math
def main():
    A,B,N = map(int, input().split())

    max1 = 0
    k = math.ceil(B/A)
    for x in range(k,N+1):
        tmp = int(A*x/B) - A*int(x/B)
        max1 = max(max1,tmp)
    print(max1)

main()


Fixed submission:
def main():
    A,B,N = map(int, input().split())

    x = min(B-1,N)
    max1 = int(A*x/B) - A*int(x/B)
    print(max1)

main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    A,B,N = map(int, input().split())

    max1 = 0
    for x in range(1,N+1):
        tmp = int(A*x/B) - A*int(x/B)
        max1 = max(max1,tmp)
    print(max1)

main()


Fixed submission:
def main():
    A,B,N = map(int, input().split())

    x = min(B-1,N)
    max1 = int(A*x/B) - A*int(x/B)
    print(max1)

main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    S = input()
    # 全探索
    count = 0
    for i in range(len(S)-3):
        for j in range(i+4,len(S)+1,1):
            if int(S[i:j])%2019==0: count+=1
    print(count)

main()


Fixed submission:
def main():
    S = input()
    n = len(S)
    p = 2019 # 法p
    # (1) a≡b,c≡dならばa+c≡b+d
    # (2) aと法pが互いに素である時、ab≡acならばb≡c
    # ex).S=1817181712114(idxは最下位が0とする), n=len(S)
    # 4≡4%p <- modp[0]
    # 14=10+4≡10%p+modp[0] <- modp[1]
    # 114=100+14≡100%p+modp[1] <- modp[2]
    # 2114=2000+114≡2000%p+modp[2] <- modp[3]
    # ...
    # 1817181712114≡100000000000%p+modp[n-2] <- modp[n-1]
    # したがって、S[1:4]=21%pについては
    # 2100=2114-14≡modp[3]-modp[1]
    # ここでaとpが互いに素なので(a=100,p=7)
    # 2100≡21 が言える
    # よって21≡modp[3]-modp[1]
    # 一般化すると、
    # S[i:j+1]≡modp[j]-modp[i]
    # すなわちmodp[j]==modp[i]となるi,jを選んだ時、S[i:j+1]はpで割り切れるという事になる

    # Sをreverseする
    S = [S[i] for i in range(n-1,-1,-1)]
    # modpを作成
    modp_counter = [0] * p
    modp = 0
    modp_counter[0] = 1 # 割り切れるやつが入る場所の初期値を1にしておかないと、1つ割り切れるやつがきたときにpair_count+=0となってしまう(pair_count+=1になるべきなのに)
    pair_count = 0
    d = 1
    for s in S:
        modp = (int(s)*d%p+modp)%p
        pair_count += modp_counter[modp]
        modp_counter[modp] += 1
        d *= 10
        d %= p # 計算量削減
    print(pair_count)


main()
Buggy python submission (verdict: Runtime Error):
import decimal
def main():
    L = int(input())
    decimal.getcontext().prec = 6
    print('{:.010f}'.format(decimal.Decimal(L*L*L/27)))

main()


Fixed submission:
def main():
    L = int(input())
    ans = '{:.010f}'.format(L*L*L/27)
    print(ans)

main()

Buggy python submission (verdict: Runtime Error):
import decimal
def main():
    L = int(input())
    decimal.getcontext().prec = 6
    print('{:.020f}'.format(decimal.Decimal(L*L*L/27)))

main()


Fixed submission:
def main():
    L = int(input())
    ans = '{:.010f}'.format(L*L*L/27)
    print(ans)

main()
Buggy python submission (verdict: Runtime Error):
def main():
    N,M = map(int, input().split())
    x = ["0"]*N
    for _ in range(M):
        s,c = input().split()
        # 左からsけた目がc
        x[int(s)-1] = c
        if s==1 and c==0:
            hfixed=True
    if N==1:
        print("".join(x))
    else:
        if x[0]=="0":
            if hfixed:
                print("-1")
            else:
                x[0] = "0"
                print("".join(x))
        else:
            print("".join(x))

main()


Fixed submission:
def main():
    N,M = map(int, input().split())
    x = ["0"]*N
    hfixed = [False]*N
    flag = False
    for _ in range(M):
        s,c = input().split()
        # 左からsけた目がc
        idx = int(s)-1
        if hfixed[idx] and x[idx]!=c:
            flag = True
            break
        else:
            hfixed[idx] = True
            x[idx] = c

    if flag:
        print("-1")
    else:
        if N==1:
            print("".join(x))
        else:
            if x[0]=="0":
                if hfixed[0]:
                    print("-1")
                else:
                    x[0] = "1"
                    print("".join(x))
            else:
                print("".join(x))

main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N = int(input())
    A = list(map(int, input().split()))
    MOD = 10**9+7
    # Aの中でd桁目が0,1であるものの個数を求める(p,qとする)
    # 全部のd桁目についてループして、ans+=(2**d)*(p*q)
    ans = 0
    for d in range(60):
        p,q = 0,0
        for i in range(N):
            if A[i]%2==0: p+=1
            else: q+=1
            A[i] //= 2
        ans += ((2**d)*p*q)%MOD
        ans %= MOD
    print(ans)

main()


Fixed submission:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    MOD = 10**9+7
    # Aの中でd桁目が0,1であるものの個数を求める(p,qとする)
    # 全部のd桁目についてループして、ans+=(2**d)*(p*q)
    ans = 0
    for d in range(60):
        p,q = 0,0
        for i in range(N):
            if A[i]%2==0: p+=1
            else: q+=1
            A[i] //= 2
        ans += ((2**d)*p*q)%MOD
        ans %= MOD
    print(ans)

main()
Buggy python submission (verdict: Runtime Error):
def main():
    N,W = map(int, input().split())
    w,v = [0]*N,[0]*N
    for i in range(N):
        w[i],v[i] = map(int, input().split())
    # dp[i][w] := 容量をwとして荷物0~iの中から荷物を選んだ時の価値の最大値
    # 初期値dp[0][W] = 0の価値(もし0の重さがMAXを超えるなら選べない)
    dp = [[0]*(W+1) for i in range(N)]
    for x in range(W+1):
        dp[0][x] = 0 if w[0]>x else v[0]
    for i in range(N-1):
        for j in range(W+1):
            if w[i+1]<=j:
                # i+1番目を選ぶ
                dp[i+1][j] = max(dp[i+1][j], (dp[i][j-w[i+1]])+v[i+1])
            # i+1番目を選ばない
            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
    print(dp[-1][W])

main()


Fixed submission:
def chmin(a,b):
    if a>b: return b
    else: return a

def chmax(a,b):
    if a>b: return a
    else: return b

def main():
    N = int(input())
    h = list(map(int, input().split()))
    # 初期化
    # 初期条件
    # ループ
    # テーブルから解を得る
    INF = float('inf')
    dp = [INF] * N
    dp[0] = 0
    dp[1] = abs(h[1]-h[0])
    for i in range(N-2):
        dp[i+2] = chmin(dp[i]+abs(h[i+2]-h[i]), dp[i+1]+abs(h[i+2]-h[i+1]))
    print(dp[-1])

main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N,K = map(int, input().split())
    h = list(map(int, input().split()))
    # 初期化
    # 初期条件
    # ループ
    # テーブルから解を得る
    INF = float('inf')
    dp = [INF] * N
    dp[0] = 0
    for i in range(N-1):
        t = min(K+1, N-i)
        for j in range(1, t):
            dp[i+j] = min(dp[i+j], dp[i]+abs(h[i+j]-h[i]))
    print(dp[-1])

main()


Fixed submission:
def main():
    N,K = map(int, input().split())
    h = list(map(int, input().split()))
    # 初期化
    # 初期条件
    # ループ
    # テーブルから解を得る
    INF = float('inf')
    dp = [INF] * N
    dp[0] = 0
    for i in range(N-1):
        for j in range(1, min(K+1, N-i)):
            dp[i+j] = min(dp[i+j], dp[i]+abs(h[i+j]-h[i]))
    print(dp[-1])

main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N,K = map(int, input().split())
    h = list(map(int, input().split()))
    # 初期化
    # 初期条件
    # ループ
    # テーブルから解を得る
    INF = float('inf')
    dp = [INF] * N
    dp[0] = 0
    for i in range(N-1):
        for j in range(1, min(K+1, N-i)):
            dp[i+j] = min(dp[i+j], dp[i]+abs(h[i+j]-h[i]))
    print(dp[-1])

main()


Fixed submission:
def main():
    N,K = map(int, input().split())
    h = list(map(int, input().split()))
    # 初期化
    # 初期条件
    # ループ
    # テーブルから解を得る
    INF = float('inf')
    dp = [INF] * N
    dp[0] = 0
    for i in range(N-1):
        for j in range(1, min(K+1, N-i)):
            dp[i+j] = min(dp[i+j], dp[i]+abs(h[i+j]-h[i]))
    print(dp[-1])

main()

Buggy python submission (verdict: Time Limit Exceeded):
def chmin(a,b):
    if a>b: return b
    else: return a

def chmax(a,b):
    if a>b: return a
    else: return b

def main():
    N,K = map(int, input().split())
    h = list(map(int, input().split()))
    # 初期化
    # 初期条件
    # ループ
    # テーブルから解を得る
    INF = float('inf')
    dp = [INF] * N
    dp[0] = 0
    for i in range(N-1):
        for j in range(1, min(K+1, N-i)):
            dp[i+j] = chmin(dp[i+j], dp[i]+abs(h[i+j]-h[i]))
    print(dp[-1])

main()


Fixed submission:
def main():
    N,K = map(int, input().split())
    h = list(map(int, input().split()))
    # 初期化
    # 初期条件
    # ループ
    # テーブルから解を得る
    INF = float('inf')
    dp = [INF] * N
    dp[0] = 0
    for i in range(N-1):
        for j in range(1, min(K+1, N-i)):
            dp[i+j] = min(dp[i+j], dp[i]+abs(h[i+j]-h[i]))
    print(dp[-1])

main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N,W = map(int, input().split())
    w,v = [0]*N,[0]*N
    for i in range(N):
        w[i],v[i] = map(int, input().split())
    # dp[i][w] := 容量をwとして荷物0~iの中から荷物を選んだ時の価値の最大値
    # 初期値dp[0][W] = 0の価値(もし0の重さがMAXを超えるなら選べない)
    dp = [[0]*(W+1) for i in range(N)]
    for x in range(W+1):
        dp[0][x] = 0 if w[0]>x else v[0]
    for i in range(N-1):
        for j in range(W+1):
            if w[i+1]<=j:
                # i+1番目を選ぶ
                dp[i+1][j] = max(dp[i+1][j], (dp[i][j-w[i+1]])+v[i+1])
            # i+1番目を選ばない
            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
    print(dp[-1][W])

main()


Fixed submission:
def main():
    N,W = map(int, input().split())
    w,v = [0]*N,[0]*N
    for i in range(N):
        w[i],v[i] = map(int, input().split())
    # dp[i][w] := 容量をwとして荷物0~iの中から荷物を選んだ時の価値の最大値
    # 初期値dp[0][W] = 0の価値(もし0の重さがMAXを超えるなら選べない)
    dp = [[0]*(W+1) for i in range(N)]
    for x in range(W+1):
        dp[0][x] = 0 if w[0]>x else v[0]
    for i in range(N-1):
        for j in range(W+1):
            if w[i+1]<=j:
                # i+1番目を選ぶ
                dp[i+1][j] = max(dp[i+1][j], (dp[i][j-w[i+1]])+v[i+1])
            # i+1番目を選ばない
            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
    print(dp[-1][W])

main()
Buggy python submission (verdict: Time Limit Exceeded):
import math
n=int(input())
for i in range(1,n+1):
  s=0
  p=math.floor(math.sqrt(i))
  for x in range(1,p):
    for y in range(1,x+1):
      for z in range(1,y+1):
        if x**2+y**2+z**2+x*y+y*z+z*x==i:
          if x==y==z: s+=1
          elif x==y or y==z: s+=3
          else: s+=6          
  print(s)

Fixed submission:
n=int(input())
dic={i:0 for i in range(1,n+1)}
for x in range(1,100):
  for y in range(1,x+1):
    for z in range(1,y+1):
      k=x**2+y**2+z**2+x*y+y*z+z*x
      if k<=n:
        if x==y==z: dic[k]+=1
        elif x==y or y==z: dic[k]+=3
        else: dic[k]+=6
for l in range(n):
  print(dic[l+1])
Buggy python submission (verdict: Runtime Error):
a,v=map(int,input().split())
b,w==map(int,input().split())
t=int(input())
d=abs(a-b)
if d<=(v-w)*t:
  print('Yes')
else:
  print('No')

Fixed submission:
a,v=map(int,input().split())
b,w=map(int,input().split())
t=int(input())
d=abs(a-b)
if d<=(v-w)*t:
  print('YES')
else:
  print('NO')
Buggy python submission (verdict: Runtime Error):
t=input(str())
t=list(t)
for i in range(1,len(t)-1):
    if t[i]=='?':
        if t[i+1]=='D' :
            t[i]='P'
        elif t[i + 1] == '?':
            if t[i-1]=='P':
                t[i]='D'
            else:
                t[i]='P'
        else:
            t[i]='D'
    if t[0]=='?'
        t[1]='P'
    if t[-1]=='?':
        t[-1]='D'
print(''.join(t))

Fixed submission:
t=input(str())
t=list(t)
for i in range(len(t)):
    if t[i]=='?':
      t[i]='D'
print(''.join(t))
Buggy python submission (verdict: Runtime Error):
from collections import deque
def search(l,dic1,dic2):
    if not l:
        return(dic2)
    else:
        x=l.pop()
        for y in dic1[x]:
            if dic2[y]==0:
                l.appendleft(y)
                dic2[y]=x
        return search(l,dic1,dic2)

n,m=map(int,input().split())
l=[i+1 for i in range(n)]
dic1={i:[] for i in l}
dic2={i:0 for i in l}
for _ in range(m):
    a, b = map(int, input().split())
    dic1[a].append(b)
    dic1[b].append(a)
l=deque(dic1[1])
for z in l:
    dic2[z]=1

d=search(l,dic1,dic2)
print('Yes')
for k in range(2,n+1):
    print(dic2[k])

Fixed submission:
from collections import deque
import sys
sys.setrecursionlimit(10**7)
def search(l,dic1,dic2):
    if not l:
        return(dic2)
    else:
        x=l.pop()
        for y in dic1[x]:
            if dic2[y]==0:
                l.appendleft(y)
                dic2[y]=x
        return search(l,dic1,dic2)

n,m=map(int,input().split())
l=[i+1 for i in range(n)]
dic1={i:[] for i in l}
dic2={i:0 for i in l}
for _ in range(m):
    a, b = map(int, input().split())
    dic1[a].append(b)
    dic1[b].append(a)
l=deque(dic1[1])
for z in l:
    dic2[z]=1

d=search(l,dic1,dic2)
print('Yes')
for k in range(2,n+1):
    print(dic2[k])
Buggy python submission (verdict: Runtime Error):
N,K=map(int,input().split())
a=set([])
for i in range(K):
    d=int(input())
    for i in range(d):
        L=list(map(int,input().split()))
        for x in L:
            a.add(x)
print(N-len(a))

Fixed submission:
N,K=map(int,input().split())
a=set([])
for i in range(K):
    d=int(input())
    L=list(map(int,input().split()))
    for x in L:
        a.add(x)
print(N-len(a))
Buggy python submission (verdict: Runtime Error):
N,M,Q=map(int,input().split())
v=[[] for _ in range(Q)]
o=0
for i in range(Q):
    v[i]=list(map(int,input().split()))
l=list(itertools.combinations(range(M+N), N))
for x in l:
    s=0
    a=[]
    for i in range(N):
        a.append(x[i]-i)
    for i in range(Q):
        if a[l[i][2]]-a[l[i][1]]-l[i][3]==0:
            s+=l[i][4]
    if s>o:
        o=s
print(o)

Fixed submission:
import itertools
N,M,Q=map(int,input().split())
v=[[] for _ in range(Q)]
o=0
for i in range(Q):
    v[i]=list(map(int,input().split()))
l=list(itertools.combinations(range(M-1+N), N))
for x in l:
    s=0
    a=[]
    for i in range(N):
        a.append(x[i]-i+1)
    for i in range(Q):
        if a[v[i][1]-1]-a[v[i][0]-1]-v[i][2]==0:
            s+=v[i][3]
    if s>o:
        o=s
print(o)

Buggy python submission (verdict: Runtime Error):
import itertools
N,M,Q=map(int,input().split())
a=[]
b=[]
c=[]
d=[]
s=0
o=0
for i in range(Q):
    u,v,x,y=map(int,input().split())
    a.append(u)
    b.append(v)
    c.append(x)
    d.append(y)
for k in range(M):
    l=list(itertools.combinations(range(k+N), N))
    for x in l:
        s=0
        h=[]
        for i in range(N):
            h.append(x[i]-i)
        for i in range(Q):
            if h[a[i]]-h[b[i]]==c[i]:
                s+=d[i]
    if o<s:
        o=s
print(o)


Fixed submission:
import itertools
N,M,Q=map(int,input().split())
v=[[] for _ in range(Q)]
o=0
for i in range(Q):
    v[i]=list(map(int,input().split()))
l=list(itertools.combinations(range(M-1+N), N))
for x in l:
    s=0
    a=[]
    for i in range(N):
        a.append(x[i]-i+1)
    for i in range(Q):
        if a[v[i][1]-1]-a[v[i][0]-1]-v[i][2]==0:
            s+=v[i][3]
    if s>o:
        o=s
print(o)
Buggy python submission (verdict: Runtime Error):
N,K=map(int,input().split())
S=0
l=[0 for _ in range(K)]
for i in range(K):
    j=K-i
    v=(K//j)**N-l[j-1]
    for w in range(j//2):
        if j%(w+1)==0:
            l[w]+=v
    S+=j*v
print(S%(10**9+7))

Fixed submission:
s=str(input())
if '7' in s:
    print('Yes')
else:
    print('No')
Buggy python submission (verdict: Runtime Error):
n,a,b=map(int(input()))
if (b-a)%2==0:
  print((b-a)/2)
else:
  l=[n-a,b]
  print(min(l))

Fixed submission:
n,a,b=map(int,input().split())
if (b-a)%2==0:
  print((b-a)//2)
else:
  x=(a+b-1)//2
  l=[x,n-x]
  print(min(l))
Buggy python submission (verdict: Time Limit Exceeded):
H, N = map(int, input().split())
A, B = [], []
for _ in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

dp = [float('inf')] * (H + 10 ** 4)

dp[0] = 0
for j in range(H + 10 ** 4):
    for i in range(N):
        dp[j] = min(dp[j], dp[max(0, j - A[i])] + B[i])
print(min(dp[H:]))


Fixed submission:
H, N = map(int, input().split())
A, B = [], []
for _ in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

dp = [float('inf')] * (H + 10 ** 4)

dp[0] = 0
for j in range(H + 10 ** 4):
    for i in range(N):
        dp[j] = min(dp[j], dp[max(0, j - A[i])] + B[i])
print(min(dp[H:]))

Buggy python submission (verdict: Time Limit Exceeded):
H, N = map(int, input().split())
A, B = [], []
for _ in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

dp = [float('inf')] * (H + 10 ** 4)

dp[0] = 0
for j in range(H + 10 ** 4):
    for i in range(N):
        if j - A[i] < 0:
            continue
        dp[j] = min(dp[j], dp[j - A[i]] + B[i])
print(min(dp[H:]))

Fixed submission:
H, N = map(int, input().split())
A, B = [], []
for _ in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

dp = [float('inf')] * (H + 10 ** 4)

dp[0] = 0
for j in range(H + 10 ** 4):
    for i in range(N):
        dp[j] = min(dp[j], dp[max(0, j - A[i])] + B[i])
print(min(dp[H:]))
Buggy python submission (verdict: Time Limit Exceeded):
from fractions import gcd


def lcm(x, y):
    return x // gcd(x, y) * y


N = int(input())
A = list(map(int, input().split()))
_lcm = 1
for a in A:
    _lcm = lcm(_lcm, a)
ans = 0
for a in A:
    ans += _lcm // a
    ans %= 1000000007
print(ans)

Fixed submission:
from fractions import gcd


def lcm(x, y):
    return x // gcd(x, y) * y


def extgcd(a, b):
    if b == 0:
        return [1, 0, a]
    x, y, g = extgcd(b, a % b)
    return [y, x - a//b * y, g]


def mod_inverse(a, m):
    x, y, _ = extgcd(a, m)
    return (m + x % m) % m


N = int(input())
A = list(map(int, input().split()))
_lcm = 1
for a in A:
    _lcm = lcm(_lcm, a)
ans = 0
for a in A:
    ans += _lcm * mod_inverse(a, 1000000007)
print(ans % 1000000007)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())

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

cand = []
for i in range(1, N):
    diff = abs(sum(A[:i]) - sum(A[i:]))
    cand.append(diff)
print(min(cand))

Fixed submission:
N = int(input())

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

cand = []
left = 0
right = sum(A)
for i in range(N-1):
    left += A[i]
    right -= A[i]
    diff = abs(left - right)
    cand.append(diff)
print(min(cand))