Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):

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

l=[0]*(N+1)
l[0]=1

for i in range(N):
    c=l[i]%1000000007
    if i<=N-2:
        if i not in a:
            l[i+1]+=c
    elif i not in a:
        l[i+1]+=c
        l[i+2]+=c

print(l[N]%1000000007)


Fixed submission:
N,M=map(int,input().split())
a={int(input()) for _ in range(M)}

l=[0]*(N+1)
l[0]=1

for i in range(N):
    c=l[i]%1000000007
    if i>N-2:
        if i not in a:
            l[i+1]+=c
    elif i not in a:
        l[i+1]+=c
        l[i+2]+=c

print(l[N]%1000000007)

Buggy python submission (verdict: Time Limit Exceeded):


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

l=[0]*(N+1)
l[0]=1

for i in range(N):
    c=l[i]%1000000007
    if i>N-2:
        if i not in a:
            l[i+1]+=c
    elif i not in a:
        l[i+1]+=c
        l[i+2]+=c

print(l[N]%1000000007)

Fixed submission:
N,M=map(int,input().split())
a={int(input()) for _ in range(M)}

l=[0]*(N+1)
l[0]=1

for i in range(N):
    c=l[i]%1000000007
    if i>N-2:
        if i not in a:
            l[i+1]+=c
    elif i not in a:
        l[i+1]+=c
        l[i+2]+=c

print(l[N]%1000000007)

Buggy python submission (verdict: Runtime Error):


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

l=[0]*(N+1)
l[0]=1

for i in range(N):
    c=l[i]%1000000007
    if i<=N-2:
        if i not in a:
            l[i+1]+=c
    elif i not in a:
        l[i+1]+=c
        l[i+2]+=c

print(l[N]%1000000007)

Fixed submission:
N,M=map(int,input().split())
a={int(input()) for _ in range(M)}

l=[0]*(N+1)
l[0]=1

for i in range(N):
    c=l[i]%1000000007
    if i>N-2:
        if i not in a:
            l[i+1]+=c
    elif i not in a:
        l[i+1]+=c
        l[i+2]+=c

print(l[N]%1000000007)

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

l=[0]*(N+1)
l[0]=1
# print(l)

for i in range(N):
    c=l[i]
    # print(c)
    if i not in a:
        if i+1 not in a:
            l[i+1]+=c
        if i<=N-2 and i+2 not in a:
            l[i+2]+=c

print(l[N]%1000000007)

Fixed submission:
N,M=map(int,input().split())
a={int(input()) for _ in range(M)}

l=[0]*(N+1)
l[0]=1

for i in range(N):
    c=l[i]%1000000007
    if i>N-2:
        if i not in a:
            l[i+1]+=c
    elif i not in a:
        l[i+1]+=c
        l[i+2]+=c

print(l[N]%1000000007)
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())

lst = []
for i in range(N):
    ks = list(map(int,input().split()))
    lst.append(ks[1:])

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

c = 0

for j in range(2**N):
    for k, l in enumerate(p):
        msk = 0
        for b in lst[k]:
            msk += 2**(b-1)
        if bin(j&msk).count('1') % 2 != l:
            break
    else:
        c += 1

print(c)
    


Fixed submission:
N,M=map(int,input().split())
sw=[]
for _ in range(M):
    sw.append(list(map(int,input().split()))[1:])
p=[int(i) for i in input().split()]

ans=0
for i in range(1<<N):
    flg=True

    for c,s in enumerate(sw):
        s_on=0
        for bit in s:
            if ((i >> (bit-1)) & 1) == 1:
                s_on+=1
        if s_on%2!=p[c]:
            flg=False

    if flg:
        ans+=1

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

list = [1]*N

for i in range(M):
	L, R = map(int, input().split())
	list[:L-1] = [0]*len(list[:L-1])
	list[R:] = [0]*len(list[R:])

print(list.count(1))
  


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

llist = []
rlist = []

for i in range(M):
  L, R = map(int, input().split())
  llist.append(L)
  rlist.append(R)

if min(rlist) >= max(llist):
  print(min(rlist) - max(llist) + 1)
else:
  print(0)

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

list = [1]*N

for i in range(M):
	L, R = map(int, input().split())
	list[:L-1] = [0]*len(list[:L-1])
	list[R:] = [0]*len(list[R:])

print(list.count(1))
  

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

llist = []
rlist = []

for i in range(M):
  L, R = map(int, input().split())
  llist.append(L)
  rlist.append(R)

if min(rlist) >= max(llist):
  print(min(rlist) - max(llist) + 1)
else:
  print(0)
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 = input()
 
print(S[:K-1] + S[K-1].lower() + S[K:])

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

S[N+1] = S[N+1].lower()

print(S)

Fixed submission:
N, K = map(int, input().split())
S = input()
 
print(S[:K-1] + S[K-1].lower() + S[K:])
Buggy python submission (verdict: Time Limit Exceeded):
R,G,B,N=map(int,input().split())

ans=0
for r in range(3000+1):
    if N < r*R:
        break
    for g in range(3000+1):
        if N < r*R+g*G:
            break
        if (N-r*R-g*G)%B==0:
#            print('({0}-{1}*{2}-{3}*{4})%{5}'.format(N,r,R,g,G,B))
            ans+=1
print(ans)

Fixed submission:
R,G,B,N=map(int,input().split())

ans=0
for r in range(3000+1):
    if N < r*R:
        break
    for g in range(3000+1):
        if N < r*R+g*G:
            break
        if (N-r*R-g*G)%B==0:
#            print('({0}-{1}*{2}-{3}*{4})%{5}'.format(N,r,R,g,G,B))
            ans+=1
print(ans)

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

ans=0
for r in range(3000+1):
    for g in range(3000+1):
        if (N-r*R-g*G)%B==0:
            ans+=1
print(ans)

Fixed submission:
R,G,B,N=map(int,input().split())

ans=0
for r in range(3000+1):
    if N < r*R:
        break
    for g in range(3000+1):
        if N < r*R+g*G:
            break
        if (N-r*R-g*G)%B==0:
#            print('({0}-{1}*{2}-{3}*{4})%{5}'.format(N,r,R,g,G,B))
            ans+=1
print(ans)

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

ans=0
for r in range(3000+1):
    for g in range(3000+1):
        for b in range(3000+1):
            if r*R+g*G+b*B==N:
                ans+=1
            elif r*R+g*G+b*B>N:
                b=0
                break
        if r*R+g*G>N:
            g=0
            break
    if r*R>N:
        break
print(ans)

Fixed submission:
R,G,B,N=map(int,input().split())

ans=0
for r in range(3000+1):
    if N < r*R:
        break
    for g in range(3000+1):
        if N < r*R+g*G:
            break
        if (N-r*R-g*G)%B==0:
#            print('({0}-{1}*{2}-{3}*{4})%{5}'.format(N,r,R,g,G,B))
            ans+=1
print(ans)
Buggy python submission (verdict: Runtime Error):
a, b = map(int, input().split())

if abs(a-b) <= 1:
  print(a+b)
else print(max(a, b)*2-1)

Fixed submission:
a, b = map(int, input().split())

if abs(a-b) <= 1:
  print(a+b)
else:
  print(max(a, b)*2-1)
Buggy python submission (verdict: Runtime Error):
input()
H = list(map(int, input()))

max = 0
cnt = 0

for h in H:
  if h >= max:
    cnt += 1
    max = h

print(cnt)

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

max_ = 0
cnt = 0

for h in H:
  if h >= max_:
    cnt += 1
    max_ = h

print(cnt)
Buggy python submission (verdict: Runtime Error):
import re

S = input()

print(len(max(re.findall('[ATCG]+', S))))

Fixed submission:
import re

S=input()

ans=0
for i in range(10):
  for j in range(i,10+1):
    str=S[i:j]
    if re.search(r'^[AGCT]+$' ,str):
      ans=max(ans,len(str))

print(ans)

Buggy python submission (verdict: Runtime Error):
import re

S = input()

print(max(re.findall('[ATCG]+', S)))

Fixed submission:
import re

S=input()

ans=0
for i in range(10):
  for j in range(i,10+1):
    str=S[i:j]
    if re.search(r'^[AGCT]+$' ,str):
      ans=max(ans,len(str))

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N,Q=map(int,input().split())
S=input()
dict={}
for _ in range(Q):
    l,r=map(int,input().split())
    string=S[l-1:r]
    if string in dict:
        print(dict[string])
    else:
        v=string.count('AC')
        print(v)
        dict[string]=v

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

aclist=[0 for i in range(N+1)]
for i in range(2,N+1):
    aclist[i]=aclist[i-1]+(1 if S[i-2]=='A' and S[i-1]=='C' else 0)

for j in range(Q):
    l,r=map(int,input().split())
    print(aclist[r]-aclist[l])

Buggy python submission (verdict: Time Limit Exceeded):
N,Q=map(int,input().split())
S=input()
dict={}
for _ in range(Q):
    l,r=map(int,input().split())
    string=S[l-1:r]
    if string in dict:
        print(dict[string])
    else:
        v=string.count('AC')
        print(v)
        dict[string]=v

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

aclist=[0 for i in range(N+1)]
for i in range(2,N+1):
    aclist[i]=aclist[i-1]+(1 if S[i-2]=='A' and S[i-1]=='C' else 0)

for j in range(Q):
    l,r=map(int,input().split())
    print(aclist[r]-aclist[l])

Buggy python submission (verdict: Time Limit Exceeded):
N,Q=map(int,input().split())
S=input()
for _ in range(Q):
    l,r=map(int,input().split())
    string=S[l-1:r]
    print(string.count('AC'))

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

aclist=[0 for i in range(N+1)]
for i in range(2,N+1):
    aclist[i]=aclist[i-1]+(1 if S[i-2]=='A' and S[i-1]=='C' else 0)

for j in range(Q):
    l,r=map(int,input().split())
    print(aclist[r]-aclist[l])

Buggy python submission (verdict: Time Limit Exceeded):
N,Q=map(int,input().split())
S=input()
for _ in range(Q):
    l,r=map(int,input().split())
    string=S[l-1:r]
    print(string.count('AC'))

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

aclist=[0 for i in range(N+1)]
for i in range(2,N+1):
    aclist[i]=aclist[i-1]+(1 if S[i-2]=='A' and S[i-1]=='C' else 0)

for j in range(Q):
    l,r=map(int,input().split())
    print(aclist[r]-aclist[l])

Buggy python submission (verdict: Time Limit Exceeded):
N,Q=map(int,input().split())
S=input()
for _ in range(Q):
    l,r=map(int,input().split())
    string=S[l-1:r]
    print(string.count('AC'))

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

aclist=[0 for i in range(N+1)]
for i in range(2,N+1):
    aclist[i]=aclist[i-1]+(1 if S[i-2]=='A' and S[i-1]=='C' else 0)

for j in range(Q):
    l,r=map(int,input().split())
    print(aclist[r]-aclist[l])
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()
mod = 10**9 + 7

ans = 0
G = []
for s in S:
    G.append(s)
    ans += 1
    ans %= mod

    tmp = []
    for g in G:
        if s not in g:
            ans += 1
            ans %= mod
            tmp.append(g+s)
    G += tmp
print(ans)


Fixed submission:
N=int(input())
S=input()
ans=1

for s in set(S):
    ans*=S.count(s)+1

print((ans-1)%1000000007)
Buggy python submission (verdict: Runtime Error):
N = int(input())
C = [int(input()) for _ in range(N)]

L = [-1]*(10**5+10)
dp = [-1]*(10**5+10)
dp[0] = 1

for i in range(N):
    if L[C[i]] == -1:
        dp[i+1] = dp[i]
    elif C[i] == C[i-1]:
        dp[i+1] = dp[i]
    else:
        dp[i+1] = dp[i]+dp[L[C[i]]]
    L[C[i]] = i+1
print(dp[N])


Fixed submission:
from collections import defaultdict

N=int(input())
C=[int(input()) for _ in range(N)]

d = defaultdict(int)

ans=1
for i,c in enumerate(C):
    if i>=1 and C[i-1]==C[i]:
        continue
    else:
        ans+=d[c]
        d[c]=ans
        
        ans%=10**9+7
        d[c]%=10**9+7
print(ans)
Buggy python submission (verdict: Runtime Error):
H, W = map(int, input())
h, w = map(int, input())

print((W-w) * (H-h))


Fixed submission:
H, W = map(int, input().split())
h, w = map(int, input().split())

print((W-w) * (H-h))

Buggy python submission (verdict: Runtime Error):
H, W = map(int, input())
h, w = map(int, input())

print((H-h) * (H-h))


Fixed submission:
H, W = map(int, input().split())
h, w = map(int, input().split())

print((W-w) * (H-h))
Buggy python submission (verdict: Runtime Error):
import bisect
A, B, Q = map(int, input().split())
S = [int(input()) for _ in range(A)]
T = [int(input()) for _ in range(B)]
X = [int(input()) for _ in range(Q)]

A = []
for x in X:
    SL, SR, TL, TR = 10**20, 10**20, 10**20, 10**20
    i = bisect.bisect_left(S, x)
    if i != 0:
        SL = x-S[i-1]
    if i != A:
        SR = S[i]-x

    j = bisect.bisect_left(T, x)
    if j != 0:
        TL = x-T[j-1]
    if j != B:
        TR = T[j]-x

    ans = min(max(SL, TL), min(2*SL+TR, SL+2*TR),
              min(2*TL+SR, TL+2*SR), max(SR, TR))
    A.append(ans)
print(*A, sep='\n')


Fixed submission:
import bisect
A, B, Q = map(int, input().split())
S = [int(input()) for _ in range(A)]
T = [int(input()) for _ in range(B)]
X = [int(input()) for _ in range(Q)]

for x in X:
    p0, p1, p2, p3 = (10**12 for _ in range(4))
    si = bisect.bisect_left(S, x)
    ti = bisect.bisect_left(T, x)

    if si != 0 and ti != 0:
        p0 = max(x-S[si-1], x-T[ti-1])
    if si != 0 and ti != B:
        p1 = min(x-S[si-1], T[ti]-x)*2+max(x-S[si-1], T[ti]-x)
    if si != A and ti != 0:
        p2 = min(S[si]-x, x-T[ti-1])*2+max(S[si]-x, x-T[ti-1])
    if si != A and ti != B:
        p3 = max(S[si]-x, T[ti]-x)
    print(min(p0, p1, p2, p3))

Buggy python submission (verdict: Time Limit Exceeded):
import bisect
A, B, Q = map(int, input().split())
S = [int(input()) for _ in range(A)]
T = [int(input()) for _ in range(B)]
X = [int(input()) for _ in range(Q)]

for x in X:
    SL, SR, TL, TR = 10**20, 10**20, 10**20, 10**20
    i = bisect.bisect_left(S, x)
    if i != 0:
        SL = x-S[i-1]
    if i != A:
        SR = S[i]-x

    j = bisect.bisect_left(T, x)
    if j != 0:
        TL = x-T[j-1]
    if j != B:
        TR = T[j]-x

    ans = min(max(SL, TL), min(2*SL+TR, SL+2*TR),
              min(2*TL+SR, TL+2*SR), max(SR, TR))
    print(ans)


Fixed submission:
import bisect
A, B, Q = map(int, input().split())
S = [int(input()) for _ in range(A)]
T = [int(input()) for _ in range(B)]
X = [int(input()) for _ in range(Q)]

for x in X:
    p0, p1, p2, p3 = (10**12 for _ in range(4))
    si = bisect.bisect_left(S, x)
    ti = bisect.bisect_left(T, x)

    if si != 0 and ti != 0:
        p0 = max(x-S[si-1], x-T[ti-1])
    if si != 0 and ti != B:
        p1 = min(x-S[si-1], T[ti]-x)*2+max(x-S[si-1], T[ti]-x)
    if si != A and ti != 0:
        p2 = min(S[si]-x, x-T[ti-1])*2+max(S[si]-x, x-T[ti-1])
    if si != A and ti != B:
        p3 = max(S[si]-x, T[ti]-x)
    print(min(p0, p1, p2, p3))
Buggy python submission (verdict: Runtime Error):
import heapq

N, K = map(int, input().split())
sushi = []

for _ in range(N):
    t, d = map(int, input().split())
    sushi.append((t, d))
sushi = sorted(sushi, key=lambda x: -x[1])

d_sushi = []  # 捨てる候補の寿司
heapq.heapify(d_sushi)  # リストaのheap化

fp = 0
tp = set()

for i in range(K):
    fp += sushi[i][1]
    if sushi[i][0] in tp:
        heapq.heappush(d_sushi, sushi[i][1])
    else:
        tp.add(sushi[i][0])
ans = fp+len(tp)**2

j = K
while d_sushi and len(tp) <= N:
    while sushi[j][0] in tp:
        j += 1
        if j == N:
            print(ans)
            exit()
    fp = fp-heapq.heappop(d_sushi)+sushi[j][1]
    tp.add(sushi[j][0])
    ans = max(ans, fp+len(tp)**2)

print(ans)


Fixed submission:
import heapq

N, K = map(int, input().split())
sushi = []

for _ in range(N):
    t, d = map(int, input().split())
    sushi.append((t, d))
sushi = sorted(sushi, key=lambda x: -x[1])

d_sushi = []  # 捨てる候補の寿司
heapq.heapify(d_sushi)  # リストaのheap化

fp = 0
tp = set()

for i in range(K):
    fp += sushi[i][1]
    if sushi[i][0] in tp:
        heapq.heappush(d_sushi, sushi[i][1])
    else:
        tp.add(sushi[i][0])
ans = fp+len(tp)**2

if N == K:
    print(ans)
    exit()

j = K
while d_sushi and len(tp) <= N:
    while sushi[j][0] in tp:
        j += 1
        if j == N:
            print(ans)
            exit()
    fp = fp-heapq.heappop(d_sushi)+sushi[j][1]
    tp.add(sushi[j][0])
    ans = max(ans, fp+len(tp)**2)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
H = [int(x) for x in input().split()]

dp = [10**20] * N  # dp[i]: 足場i+1に到達するための最小コスト
dp[0] = 0
for i in range(N-1):
    for j in range(1, K+1):
        if i+j <= N-1:
            dp[i+j] = min(dp[i+j], dp[i]+abs(H[i+j]-H[i]))

answer = dp[-1]
print(answer)


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

ans=[10**20 for i in range(N+K)]
ans[0]=0

for i in range(N):
    for j in range(1,K+1):
        ans[i+j]=min(ans[i+j],ans[i]+abs(h[i]-h[i+j]))

print(ans[N-1])

Buggy python submission (verdict: Runtime Error):
N,K=map(int,input().split())
h=[int(i) for i in input().split()]

ans=[10**20 for i in range(N+K)]
ans[0]=0

for i in range(N):
    for j in range(1,K+1):
        ans[i+j]=min(ans[i+j],ans[i]+abs(h[i]-h[i+j]))

print(ans[N-1])


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

ans=[10**20 for i in range(N+K)]
ans[0]=0

for i in range(N):
    for j in range(1,K+1):
        ans[i+j]=min(ans[i+j],ans[i]+abs(h[i]-h[i+j]))

print(ans[N-1])

Buggy python submission (verdict: Time Limit Exceeded):
N,K=map(int,input().split())
h=[int(i) for i in input().split()] + [0 for i in range(K)]

ans=[10**20 for i in range(N+K)]
ans[0]=0

for i in range(N):
    for j in range(1,K+1):
        ans[i+j]=min(ans[i+j],ans[i]+abs(h[i]-h[i+j]))

print(ans[N-1])


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

ans=[10**20 for i in range(N+K)]
ans[0]=0

for i in range(N):
    for j in range(1,K+1):
        ans[i+j]=min(ans[i+j],ans[i]+abs(h[i]-h[i+j]))

print(ans[N-1])
Buggy python submission (verdict: Time Limit Exceeded):
# dp[i][w_sum]: i-1番目までの品物で重さがw_sumを超えないように選んだときの、価値の総和の最大値

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

dp = [[0 for w_sum in range(W+100)] for i in range(N+100)]

for i in range(N):
    for w_sum in range(W+1):

        # i-1番目の品物を選ぶ場合
        # 重量的に入れられるなら入れてみる
        if w_sum-items[i][0] >= 0:
            dp[i+1][w_sum] = max(dp[i+1][w_sum],
                                 dp[i][w_sum-items[i][0]]+items[i][1])

        # i-1番目の品物を選ばない場合
        dp[i+1][w_sum] = max(dp[i+1][w_sum], dp[i][w_sum])

print(dp[N][W])


Fixed submission:
# dp[i][w_sum]: i番目までの品物で重さがw_sumを超えないように選んだときの、価値の総和の最大値

N,W=map(int,input().split())
items=[tuple(map(int,input().split())) for i in range(N)]
items.insert(0, (0,0))

dp=[[0 for _ in range(W+1)] for _ in range(N+1)]

for i in range(1,N+1):
    for j in range(W+1):
        # take item
        if j-items[i][0]>=0:
            dp[i][j]=dp[i-1][j-items[i][0]]+items[i][1]
        
        dp[i][j]=max(dp[i][j],dp[i-1][j])

print(dp[N][W])

Buggy python submission (verdict: Runtime Error):
# dp[i][w_sum]: i-1番目までの品物で重さがw_sumを超えないように選んだときの、価値の総和の最大値

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

dp = [[0 for w_sum in range(W)] for i in range(N)]

for i in range(N):
    for w_sum in range(W):

        # i-1番目の品物を選ぶ場合
        # 重量的に入れられるなら入れてみる
        if w_sum-items[i][0] >= 0:
            dp[i+1][w_sum] = max(dp[i+1][w_sum],
                                 dp[i][w_sum-items[i][0]]+items[i][1])

        # i-1番目の品物を選ばない場合
        dp[i+1][w_sum] = max(dp[i+1][w_sum], dp[i][w_sum])

print(dp[N][W])


Fixed submission:
# dp[i][w_sum]: i番目までの品物で重さがw_sumを超えないように選んだときの、価値の総和の最大値

N,W=map(int,input().split())
items=[tuple(map(int,input().split())) for i in range(N)]
items.insert(0, (0,0))

dp=[[0 for _ in range(W+1)] for _ in range(N+1)]

for i in range(1,N+1):
    for j in range(W+1):
        # take item
        if j-items[i][0]>=0:
            dp[i][j]=dp[i-1][j-items[i][0]]+items[i][1]
        
        dp[i][j]=max(dp[i][j],dp[i-1][j])

print(dp[N][W])

Buggy python submission (verdict: Time Limit Exceeded):
# dp[i][w_sum]: i番目までの品物で重さがw_sumを超えないように選んだときの、価値の総和の最大値

N,W=map(int,input().split())
items=[tuple(map(int,input().split())) for i in range(N)]
items.insert(0, (0,0))

dp=[[0 for _ in range(W+1)] for _ in range(N+1)]

for i in range(1,N+1):
    for j in range(W+1):
        # take item
        if j-items[i][0]>=0:
            dp[i][j]=dp[i-1][j-items[i][0]]+items[i][1]
        
        dp[i][j]=max(dp[i][j],dp[i-1][j])

print(dp[N][W])



Fixed submission:
# dp[i][w_sum]: i番目までの品物で重さがw_sumを超えないように選んだときの、価値の総和の最大値

N,W=map(int,input().split())
items=[tuple(map(int,input().split())) for i in range(N)]
items.insert(0, (0,0))

dp=[[0 for _ in range(W+1)] for _ in range(N+1)]

for i in range(1,N+1):
    for j in range(W+1):
        # take item
        if j-items[i][0]>=0:
            dp[i][j]=dp[i-1][j-items[i][0]]+items[i][1]
        
        dp[i][j]=max(dp[i][j],dp[i-1][j])

print(dp[N][W])
Buggy python submission (verdict: Time Limit Exceeded):
N, W = map(int, input().split())
items = [tuple(map(int, input().split())) for i in range(N)]

dp = [[10**15 for sum_v in range(10**5+100)] for i in range(N+100)]

for i in range(N):
    for sum_v in range(10**5+50):

        dp[0][0] = 0

        # i-1番目の品物を選ぶ場合
        if sum_v-items[i][1] >= 0:
            dp[i+1][sum_v] = min(dp[i+1][sum_v],
                                 dp[i][sum_v-items[i][1]]+items[i][0])

        # i-1番目の品物を選ばない場合
        dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])

ans = 0
for i in range(10**5+50):
    if dp[N][i] <= W:
        ans = i
print(ans)


Fixed submission:
N,W=map(int,input().split())
items=[tuple(map(int,input().split())) for i in range(N)]
items.insert(0, (0,0))

v_max=sum([x[1] for x in items])

dp=[[10**13 for _ in range(v_max+1)] for _ in range(N+1)]
dp[0][0] = 0

for i in range(1,N+1):
    for j in range(v_max+1):
        # print(i,j)
        # take item
        if j-items[i][1]>=0:
            dp[i][j]=dp[i-1][j-items[i][1]]+items[i][0]
        
        dp[i][j]=min(dp[i][j],dp[i-1][j])

# print(dp[N])

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

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
t = input()

# DPテーブルを初期化
dp = [[0 for j in range(len(t)+1)] for i in range(len(s)+1)]


# ループを回す
for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + 1)
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j])
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j+1])

# 答えを復元
ans = ''
i = len(s)
j = len(t)
while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ans = s[i-1]+ans
        i -= 1
        j -= 1
print(ans)


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

# DPテーブルを初期化
dp = [[0 for j in range(len(t)+1)] for i in range(len(s)+1)]


# ループを回す
for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + 1)
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j])
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j+1])

# 答えを復元
ans = ''
i = len(s)
j = len(t)
while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ans = s[i-1]+ans
        i -= 1
        j -= 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# 入力
N = int(input())
p = [float(x) for x in input().split()]

# DPテーブルを初期化
dp = [[0 for x in range(N+1)] for n in range(N+1)]
dp[0][0] = 1

# ループを回す
for i in range(N):
    for x in range(N):
        dp[i+1][x+1] += dp[i][x]*p[i]
        dp[i+1][x] += dp[i][x]*(1-p[i])

# 答えを得て出力
print(sum(dp[N][N//2+1:]))


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

# DPテーブルを初期化
dp = [[0 for x in range(N+1)] for n in range(N+1)]
dp[0][0] = 1

# ループを回す
for i in range(N):
    for x in range(N):
        dp[i+1][x+1] += dp[i][x]*p[i]
        dp[i+1][x] += dp[i][x]*(1-p[i])

# 答えを得て出力
print(sum(dp[N][N//2+1:]))
Buggy python submission (verdict: Runtime Error):

n=input()
a=[int(input()) for _ in range(n)]
if any(x%2==1 for x in a):
    print('first')
else:
    print('second')

Fixed submission:
n=int(input())
a=[int(input()) for _ in range(n)]
if any(x%2==1 for x in a):
    print('first')
else:
    print('second')
Buggy python submission (verdict: Runtime Error):
X, Y = map(int, input())
print(X + Y/2)

Fixed submission:
X, Y = map(int, input().split())
print(int(X + Y/2))