Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
N,M=map(int,input().split())
G=[[] for i in range(N)]
for i in range(M):
  a,b=map(int,input().split())
  G[a-1].append(b-1)
  G[b-1].append(a-1)
Q=int(input())
Colors=[0]*N
dp=[[False]*11 for i in range(N)]
def BFS(v,d,c):
  global dp
  for i in range(d+1):
    dp[v][i]=True
  stack=deque([(v,d)])
  global Colors
  while stack:
    n,m=stack.popleft()
    if m<0:
      break
    if Colors[n]==0:
      Colors[n]=c
    for u in G[n]:
      if not dp[u][m]:
        stack.append((u,m-1))
        for i in range(m):
          dp[u][i]=True
q=[list(map(int,input().split())) for i in range(Q)]
for i in q[::-1]:
  v,d,c=i
  BFS(v-1,d,c)
for c in Colors:
  print(c)


Fixed submission:
N,M=map(int,input().split())
E=[]
for i in range(M):
  a,b=map(int,input().split())
  E.append((a-1,b-1))
Q=int(input())
dp=[[-1]*11 for i in range(N)]
C=[]
for i in range(Q):
  v,d,c=map(int,input().split())
  dp[v-1][d]=i
  C.append(c)
for d in range(1,11)[::-1]:
  for n in range(N):
    dp[n][d-1]=max(dp[n][d],dp[n][d-1])
  for a,b in E:
    dp[a][d-1]=max(dp[a][d-1],dp[b][d])
    dp[b][d-1]=max(dp[b][d-1],dp[a][d])
for i in range(N):
  if dp[i][0]>=0:
    print(C[dp[i][0]])
  else:
    print(0)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
N,M=map(int,input().split())
G=[[] for i in range(N)]
for i in range(M):
  a,b=map(int,input().split())
  G[a-1].append(b-1)
  G[b-1].append(a-1)
Q=int(input())
Colors=[0]*N

def BFS(v,d,c):
  visited=[False]*N
  visited[v]==True
  stack=deque([(v,0)])
  global Colors
  while stack:
    n,m=stack.popleft()
    if m>d:
      break
    Colors[n]=c
    for s in G[n]:
      if not visited[s]:
        stack.append((s,m+1))
        visited[s]=True
        
for i in range(Q):
  v,d,c=map(int,input().split())
  BFS(v-1,d,c)
for c in Colors:
  print(c)


Fixed submission:
N,M=map(int,input().split())
E=[]
for i in range(M):
  a,b=map(int,input().split())
  E.append((a-1,b-1))
Q=int(input())
dp=[[-1]*11 for i in range(N)]
C=[]
for i in range(Q):
  v,d,c=map(int,input().split())
  dp[v-1][d]=i
  C.append(c)
for d in range(1,11)[::-1]:
  for n in range(N):
    dp[n][d-1]=max(dp[n][d],dp[n][d-1])
  for a,b in E:
    dp[a][d-1]=max(dp[a][d-1],dp[b][d])
    dp[b][d-1]=max(dp[b][d-1],dp[a][d])
for i in range(N):
  if dp[i][0]>=0:
    print(C[dp[i][0]])
  else:
    print(0)
Buggy python submission (verdict: Time Limit Exceeded):
N,Ma,Mb=map(int,input().split())
dp=[[[10**9]*401 for i in range(401)] for i in range(N)]
for i in range(N):
  a,b,c=map(int,input().split())
  if i==0:
    dp[0][a][b]=c
    dp[0][0][0]=0
  else:
    for p in range(401):
      for q in range(401):
        if p>=a and q>=b:
          dp[i][p][q]=min(dp[i-1][p][q],dp[i-1][p-a][q-b]+c)
        else:
          dp[i][p][q]=dp[i-1][p][q]
ans=10**9
for a in range(1,401):
  if Mb*a/Ma<=400 and Mb*a%Ma==0:
    ans=min(ans,dp[N-1][a][Mb*a//Ma])
if ans==10**9:
  print(-1)
else:
  print(ans)

Fixed submission:
N,Ma,Mb=map(int,input().split())
dp=[[[10**9]*401 for i in range(401)] for i in range(N)]
for i in range(N):
  a,b,c=map(int,input().split())
  if i==0:
    dp[0][a][b]=c
    dp[0][0][0]=0
  else:
    for p in range(401):
      for q in range(401):
        if p>=a and q>=b:
          dp[i][p][q]=min(dp[i-1][p][q],dp[i-1][p-a][q-b]+c)
        else:
          dp[i][p][q]=dp[i-1][p][q]
ans=10**9
for a in range(1,401):
  if Mb*a/Ma<=400 and Mb*a%Ma==0:
    ans=min(ans,dp[N-1][a][Mb*a//Ma])
if ans==10**9:
  print(-1)
else:
  print(ans)
Buggy python submission (verdict: Runtime Error):
N=int(input())
a=[int(i) for i in input().split()]
k=sum(a)//(N*(N-1)//2)
D=[]
a.append(a[0])
for i in range(N):
  D.append(a[i+1]-a[i]-k)

for d in D:
  if d%N!=0:
    print("NO")
    exit()
print("YES")
    
  


Fixed submission:
N=int(input())
a=[int(i) for i in input().split()]
S=sum(a)
if S%(N*(N+1)//2)==0:
  k=S//(N*(N+1)//2)
else:
  print("NO")
  exit()
D=[]
a.append(a[0])
for i in range(N):
  D.append(a[i+1]-a[i]-k)

for d in D:
  if d>0 or d%N!=0:
    print("NO")
    exit()
    
print("YES")
Buggy python submission (verdict: Runtime Error):
N=int(input())
A=[int(i) for i in input().split()]
G=[[] for i in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  G[a-1].append(b-1)
  G[b-1].append(a-1)
Visited=[False]*N
B=[0]*N
def B_map(x):
  C=[]
  S=-1
  Visited[x]=True
  for i in G[x]:
    if not Visited[i]:
      res=B_map(i)
      if S<0:
        S=res
      else:
        S+=res
      C.append(res)
  if S<0:
    B[x]=A[x]
  else:
    M=max(max(C),sum(C)//2)
    T=2*A[x]-S
    if 0<=(S-T)//2<=M:
      B[x]=2*A[x]-S
    else:
      print("NO")
      exit()
    if x==0 and T!=0:
      print("NO")
      exit()
  return B[x]
B_map(0)
for i in range(N):
  if B[i]<0:
    print("NO")
    exit()
print("YES")

Fixed submission:
import sys
sys.setrecursionlimit(10**6)
N=int(input())
A=[int(i) for i in input().split()]
G=[[] for i in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  G[a-1].append(b-1)
  G[b-1].append(a-1)
Visited=[False]*N
B=[0]*N
def B_map(x):
  C=[]
  S=0
  Visited[x]=True
  for i in G[x]:
    if not Visited[i]:
      res=B_map(i)
      S+=res
      C.append(res)
  if len(C)==0:
    B[x]=A[x]
  elif len(C)==1:
    if A[x]==S:
      B[x]=S
    else:
      print("NO")
      exit()
  else:
    if 0<=S-A[x]<=min(S-max(C),S//2) and 2*A[x]-S>=0:
      B[x]=2*A[x]-S
    else:
      print("NO")
      exit()
  return B[x]
B_map(0)
if len(G[0])==1:
  if B[0]!=A[0]:
    print("NO")
    exit()
else:
  if B[0]!=0:
    print("NO")
    exit()
    
print("YES")

Buggy python submission (verdict: Runtime Error):
N=int(input())
A=[int(i) for i in input().split()]
G=[[] for i in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  G[a-1].append(b-1)
  G[b-1].append(a-1)
Visited=[False]*N
B=[0]*N
def B_map(x):
  res=-1
  Visited[x]=True
  for i in G[x]:
    if not Visited[i]:
      if res<0:
        res=B_map(i)
      else:
        res+=B_map(i)
  if res<0:
    B[x]=A[x]
  else:
    B[x]=2*A[x]-res
  return B[x]
B_map(0)
for i in range(N):
  if B[i]<0:
    print("NO")
    exit()
print("YES")

Fixed submission:
import sys
sys.setrecursionlimit(10**6)
N=int(input())
A=[int(i) for i in input().split()]
G=[[] for i in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  G[a-1].append(b-1)
  G[b-1].append(a-1)
Visited=[False]*N
B=[0]*N
def B_map(x):
  C=[]
  S=0
  Visited[x]=True
  for i in G[x]:
    if not Visited[i]:
      res=B_map(i)
      S+=res
      C.append(res)
  if len(C)==0:
    B[x]=A[x]
  elif len(C)==1:
    if A[x]==S:
      B[x]=S
    else:
      print("NO")
      exit()
  else:
    if 0<=S-A[x]<=min(S-max(C),S//2) and 2*A[x]-S>=0:
      B[x]=2*A[x]-S
    else:
      print("NO")
      exit()
  return B[x]
B_map(0)
if len(G[0])==1:
  if B[0]!=A[0]:
    print("NO")
    exit()
else:
  if B[0]!=0:
    print("NO")
    exit()
    
print("YES")
Buggy python submission (verdict: Runtime Error):
N,M=map(int,input().split())
section=[[] for i in range(M+1)]
for i in range(N):
  l,r=map(int,input().split())
  section[r-l+1].append((l,r))

def add(B,a,s):
    x=a
    while x<=len(B):
        B[x]+=s
        x+=x&(-x)
        
def sums(B,a):
    x=a
    S=0
    while x!=0:
        S+=B[x]
        x-=x&(-x)
    return S

Line=[0]*(M+2)
K=N
for d in range(1,M+1):
  for l,r in section[d]:
    add(Line,l,1)
    add(Line,r+1,-1)
    K-=1
  ans=K
  for s in range(M//d+1):
    ans+=sums(Line,s*d)
  print(ans)





Fixed submission:
N,M=map(int,input().split())
section=[[] for i in range(M+1)]
for i in range(N):
  l,r=map(int,input().split())
  section[r-l+1].append((l,r))

def add(B,a,s):
    x=a
    while x<=len(B)-1:
        B[x]+=s
        x+=x&(-x)
        
def sums(B,a):
    x=a
    S=0
    while x!=0:
        S+=B[x]
        x-=x&(-x)
    return S

Line=[0]*(M+2)
K=N
for d in range(1,M+1):
  for l,r in section[d]:
    add(Line,l,1)
    add(Line,r+1,-1)
    K-=1
  ans=K
  for s in range(M//d+1):
    ans+=sums(Line,s*d)
  print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from heapq import heapify,heappush,heappop
sys.setrecursionlimit(10**7)
N=int(input())
List=[[] for i in range(N)]
for i in range(1,N):
  a=int(input())
  List[a-1].append(i)

def f(x):
  if len(List[x])==0:
    return 0
  L=[]
  heapify(L)
  for a in List[x]:
    heappush(L,f(a))
  n=len(L)
  res=0
  for i in range(n):
    b=heappop(L)
    res=max(res,b+n-i)
  return res
print(f(0))
  

Fixed submission:
import sys
from heapq import heapify,heappush,heappop
sys.setrecursionlimit(10**7)
input=sys.stdin.readline
N=int(input())
List=[[] for i in range(N)]
for i in range(1,N):
  a=int(input())
  List[a-1].append(i)

def f(x):
  if len(List[x])==0:
    return 0
  L=[]
  heapify(L)
  for a in List[x]:
    heappush(L,f(a))
  n=len(L)
  res=0
  for i in range(n):
    b=heappop(L)
    res=max(res,b+n-i)
  return res
print(f(0))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**7)
N=int(input())
List=[[] for i in range(N)]
for i in range(1,N):
  a=int(input())
  List[a-1].append(i)

def f(x):
  if len(List[x])==0:
    return 0
  L=list(map(lambda a:f(a),List[x]))
  L.sort(key=lambda x:-x)
  res=0
  for i in range(len(L)):
    res=max(res,L[i]+i+1)
  return res
print(f(0))
  

Fixed submission:
import sys
from heapq import heapify,heappush,heappop
sys.setrecursionlimit(10**7)
input=sys.stdin.readline
N=int(input())
List=[[] for i in range(N)]
for i in range(1,N):
  a=int(input())
  List[a-1].append(i)

def f(x):
  if len(List[x])==0:
    return 0
  L=[]
  heapify(L)
  for a in List[x]:
    heappush(L,f(a))
  n=len(L)
  res=0
  for i in range(n):
    b=heappop(L)
    res=max(res,b+n-i)
  return res
print(f(0))

Buggy python submission (verdict: Runtime Error):
N=int(input())
List=[[] for i in range(N)]
for i in range(1,N):
  a=int(input())
  List[a-1].append(i)

def f(x):
  if len(List[x])==0:
    return 0
  L=list(map(lambda a:f(a),List[x]))
  L.sort(key=lambda x:-x)
  res=0
  for i in range(len(L)):
    res=max(res,L[i]+i+1)
  return res
print(f(0))
  

Fixed submission:
import sys
from heapq import heapify,heappush,heappop
sys.setrecursionlimit(10**7)
input=sys.stdin.readline
N=int(input())
List=[[] for i in range(N)]
for i in range(1,N):
  a=int(input())
  List[a-1].append(i)

def f(x):
  if len(List[x])==0:
    return 0
  L=[]
  heapify(L)
  for a in List[x]:
    heappush(L,f(a))
  n=len(L)
  res=0
  for i in range(n):
    b=heappop(L)
    res=max(res,b+n-i)
  return res
print(f(0))
Buggy python submission (verdict: Time Limit Exceeded):
N,A,B,C,D=map(int,input().split())
mod=10**9+7

F=[1]*(N+1)
for i in range(1,N+1):
  F[i]=F[i-1]*(i)%mod
def power(x,y):
  if y==0:
    return 1
  elif y==1:
    return x%mod
  elif y%2==0:
    return power(x,y//2)**2%mod
  else:
    return (power(x,y//2)**2)*x%mod

invF=[1]*(N+1)
invF[N]=power(F[N],mod-2)
for i in range(0,N)[::-1]:
  invF[i]=(invF[i+1]*(i+1))%mod
  
dp=[[0]*(N+1) for i in range(B-A+2)]
dp[0][0]=1
for i in range(A,B+1):
  for j in range(N+1):
    dp[i-A+1][j]=(dp[i-A][j]+sum([dp[i-A][j-k*i]*F[N-j+k*i]*invF[N-j]*power(invF[i],k)*invF[k] for k in range(C,min(D,j//i)+1)]))%mod
    
print((dp[B-A+1][N])%mod)


        
  


    
                                      

Fixed submission:
N,A,B,C,D=map(int,input().split())
mod=10**9+7

F=[1]*(N+1)
for i in range(1,N+1):
  F[i]=F[i-1]*(i)%mod
def power(x,y):
  if y==0:
    return 1
  elif y==1:
    return x%mod
  elif y%2==0:
    return power(x,y//2)**2%mod
  else:
    return (power(x,y//2)**2)*x%mod

invF=[1]*(N+1)
invF[N]=power(F[N],mod-2)
for i in range(0,N)[::-1]:
  invF[i]=(invF[i+1]*(i+1))%mod
invp=[[0]*(N+1) for i in range(N+1)]
for i in range(N+1):  
  for k in range(N+1):
    if k==0:
      invp[i][k]=1
    else:
      invp[i][k]=(invp[i][k-1]*invF[i])%mod
dp=[[0]*(N+1) for i in range(B-A+2)]
dp[0][0]=1
for i in range(A,B+1):
  for j in range(N+1):
    dp[i-A+1][j]=dp[i-A][j]
    for k in range(C,min(D,j//i)+1):
      dp[i-A+1][j]+=(dp[i-A][j-k*i]*F[N-j+k*i]*invF[N-j]*invp[i][k]*invF[k])%mod
      dp[i-A+1][j]%=mod
    
print((dp[B-A+1][N])%mod)
Buggy python submission (verdict: Time Limit Exceeded):
class Unionfind:
  def __init__(self,n):
    self.Tree=[i for i in range(n)]
    self.rank=[0]*n

  def find(self,x):
    if x==self.Tree[x]:
      return x
    else:
      root=self.find(self.Tree[x])
      self.Tree[x]=root
      return root

  def unite(self,x,y):
    s1=self.find(x)
    s2=self.find(y)
    if s1==s2:
      pass
    else:
      if self.rank[s1]>self.rank[s2]:
        self.Tree[s2]=s1
      elif self.rank[s1]<self.rank[s2]:
        self.Tree[s1]=s2
      else:
        self.Tree[s2]=s1
        self.rank[s1]+=1
N,K,L=map(int,input().split())       
uf1=Unionfind(N)
uf2=Unionfind(N)
for i in range(K):
  p,q=map(int,input().split())
  uf1.unite(p-1,q-1)
for j in range(L):
  r,s=map(int,input().split())
  uf2.unite(r-1,s-1)
ans=[1]*N
for i in range(N):
  for j in range(i):
    if uf1.find(i)==uf1.find(j) and uf2.find(i)==uf2.find(j):
      ans[i]+=1
      ans[j]+=1
ans=list(map(str,ans))
print(" ".join(ans))        

Fixed submission:
from collections import defaultdict
class Unionfind:
  def __init__(self,n):
    self.Tree=[i for i in range(n)]
    self.rank=[0]*n

  def find(self,x):
    if x==self.Tree[x]:
      return x
    else:
      root=self.find(self.Tree[x])
      self.Tree[x]=root
      return root

  def unite(self,x,y):
    s1=self.find(x)
    s2=self.find(y)
    if s1==s2:
      pass
    else:
      if self.rank[s1]>self.rank[s2]:
        self.Tree[s2]=s1
      elif self.rank[s1]<self.rank[s2]:
        self.Tree[s1]=s2
      else:
        self.Tree[s2]=s1
        self.rank[s1]+=1
N,K,L=map(int,input().split())       
uf1=Unionfind(N)
uf2=Unionfind(N)
for i in range(K):
  p,q=map(int,input().split())
  uf1.unite(p-1,q-1)
for j in range(L):
  r,s=map(int,input().split())
  uf2.unite(r-1,s-1)
d=defaultdict(int)
ans=[0]*N
for i in range(N):
  d[(uf1.find(i),uf2.find(i))]+=1
for i in range(N):
  ans[i]=d[(uf1.find(i),uf2.find(i))]
print(" ".join(map(str,ans)))
Buggy python submission (verdict: Runtime Error):
from heapq import heapify,heappop,heappush
xs,ys,xt,yt=map(int,input().split())
P=[]
inf=float("inf")
P.append((xs,ys,0))
N=int(input())
for i in range(N):
  x,y,r=map(int,input().split())
  P.append((x,y,r))
P.append((xt,yt,0))
G=[set() for i in range(N+2)]
for i in range(N+2):
  for j in range(N+2):
    if i!=j:
      x1,y1,r1,x2,y2,r2=P[i][0],P[i][1],P[i][2],P[j][0],P[j][1],P[j][2]
      d=((x1-x2)**2+(y1-y2)**2)**(1/2)
      if d<=r1+r2:
        G[i].add((0,j))
      else:
        G[i].add((d-r1-r2,j))

def dijkstra(s,n,links):
  cost=[inf]*n
  cost[s]=0
  heap=[(0,s)]
  heapify(heap)
  while heap:
    hc,hp=heappop(heap)
    for c,p in links[hp]:
      if c+hc<cost[p]:
        cost[p]=c+hc
        heappush(heap,(cost[p],p))
  return cost        

c=dijkstra(0,N+2,G)
print(c[-1])

Fixed submission:
N,x=map(int,input().split())
A=[int(i) for i in input().split()]
ans=0
if A[0]+A[1]>x:
  if A[0]>x:
    ans+=A[1]+A[0]-x
    A[1],A[0]=0,x
  else:
    ans+=A[1]-x+A[0]
    A[1]=x-A[0]
for i in range(1,N):
  if A[i-1]+A[i]>x:
    ans+=A[i-1]+A[i]-x
    A[i]=x-A[i-1]
print(ans)
Buggy python submission (verdict: Runtime Error):
N=int(input())
T=[int(i) for i in input().split()]
A=[int(i) for i in input().split()]
ans=1
mod=10**9+7
for i in range(N):
  if i==0:
    if A[i]!=A[i+1] and T[i]!=A[i]:
      print(0)
      exit()
  elif i==N-1:
    if T[i]!=T[i-1] and T[i]!=A[i]:
      print(0)
      exit()
  else:
    if T[i]==T[i-1] and A[i]==A[i+1]:
      ans=(ans*min(T[i],A[i]))%mod
    elif T[i]!=T[i-1] and A[i]<T[i]:
      print(0)
      exit()
    elif A[i]!=A[i+1] and A[i]>T[i]:
      print(0)
      exit()
print(ans)
    
      

Fixed submission:
N=int(input())
T=[int(i) for i in input().split()]
A=[int(i) for i in input().split()]
if N==1:
  if A[0]==T[0]:
    print(1)
  else:
    print(0)
  exit()
  
ans=1
mod=10**9+7
for i in range(N):
  if i==0:
    if A[i]!=A[i+1] and T[i]!=A[i]:
      print(0)
      exit()
  elif i==N-1:
    if T[i]!=T[i-1] and T[i]!=A[i]:
      print(0)
      exit()
  else:
    if T[i]==T[i-1] and A[i]==A[i+1]:
      ans=(ans*min(T[i],A[i]))%mod
    elif T[i]!=T[i-1] and A[i]<T[i]:
      print(0)
      exit()
    elif A[i]!=A[i+1] and A[i]>T[i]:
      print(0)
      exit()
print(ans)
Buggy python submission (verdict: Runtime Error):
A=sorted([int(i) for i in input().split()])
if A==[5,5,7]:
  print(“YES”)
else:
  print(“NO”)

Fixed submission:
A=sorted([int(i) for i in input().split()])
if A==[5,5,7]:
  print("YES")
else:
  print("NO")
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))

ans = 1
for a in A:
    ans *= a
if ans > 10**18:
    ans = -1
print(ans)


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

if A.count(0):
    print(0)
    import sys
    sys.exit()

ans = 1
for a in A:
    ans *= a
    if ans > 10**18:
        print(-1)
        import sys
        sys.exit()

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
a, b, c, d = list(map(int, input().split()))
turn = True
while True:
  if turn:
    c -= b
    if c <= 0:
      print("Yes")
  else:
    a -= d
    if a <= 0:
      print("No")
  turn ^= True

Fixed submission:
a, b, c, d = list(map(int, input().split()))
turn = True
while True:
  if turn:
    c -= b
    if c <= 0:
      print("Yes")
      import sys
      sys.exit()
  else:
    a -= d
    if a <= 0:
      print("No")
      import sys
      sys.exit()
  turn ^= True
Buggy python submission (verdict: Runtime Error):
n, m = list(map(int, input().split()))
A = list(map(int, input().split()))
sum = sum(A)
for a in A:
  if a * 4 * m < sum:
    cnt += 1
if cnt >= m:
  print("Yes")
else:
  print("No")
  

Fixed submission:
n, m = list(map(int, input().split()))
A = list(map(int, input().split()))
sum = sum(A)
cnt = 0
for a in A:
  if a * 4 * m >= sum:
    cnt += 1
if cnt >= m:
  print("Yes")
else:
  print("No")
Buggy python submission (verdict: Runtime Error):
s = input()
if s[2] == s[3] && 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):
from math import gcd
x = input()
print(360*gcd(x,360)//x)

Fixed submission:
from math import gcd
x = int(input())
print(360*(x//gcd(x,360))//x)
Buggy python submission (verdict: Time Limit Exceeded):
from sys import stdin
from collections import Counter
n,W = map(int,stdin.readline().split())
dp = Counter({0:0})
for _ in range(n):
    w,v = map(int,stdin.readline().split())
    r = dp.copy()
    for i in r:
        if i+w <= W:
            dp[i+w] = max(r[i+w],r[i]+v)
print(dp[max(dp,key=dp.get)])

Fixed submission:
from sys import stdin
from math import inf
n,W = map(int,stdin.readline().split())
dp = [inf]*(1000*n)
for _ in range(n):
    w,v = map(int,stdin.readline().split())
    for i in range(1000*n-v-1,-1,-1):
        if dp[i] and dp[i]+w <= W:
            dp[i+v] = min(dp[i+v],dp[i]+w)
    dp[v-1] = min(dp[v-1],w)
for i in range(len(dp)-1,-1,-1):
    if dp[i] != inf:
        print(i+1)
        break
Buggy python submission (verdict: Runtime Error):
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, a, b;
    cin >> n >> a >> b;
    int m = 1 << n;
    int d = a ^ b;
    if (__buitin_popcount(d) % 2 == 1) {
        cout << "NO" << endl;
        return 0;
    }
    cout << "YES" << endl;
    vector<int> res(m);

    for (int i = 0; i < m; i++) {
        cout << res[i] ^ a << " ";
    }
    cout << endl;
    return 0;
}

Fixed submission:
s, t = input().split()
a, b = map(int, input().split())
u = input()
if s == u:
    a -= 1
else:
    b -= 1
print(a,  b)
Buggy python submission (verdict: Runtime Error):
a, b = map(int, input().split())
print('Yes' if  is b else 'No')


Fixed submission:
a, b = map(int, input().split())
print('Yes' if a is b else 'No')
Buggy python submission (verdict: Runtime Error):
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> p(n), x(n);
    for (int i = 1; i < n; i++) {
        cin >> p[i];
        p[i]--;
    }
    for (int i = 0; i < n; i++) {
        cin >> x[i];
    }
    bool ok = false;

    if (ok) {
        puts("POSSIBLE");
    } else {
        puts("IMPOSSIBLE");
    }
    return 0;
}

Fixed submission:
n = int(input())
h = list(map(int, input().split()))
mn = 0
ans = "Yes"
for i in h:
    if i <= mn - 2:
        ans = "No"
    else:
        mn = max(mn, i)
print(ans)
Buggy python submission (verdict: Runtime Error):
import math
print(math.factorial(int(input())) % (10**9+7)))


Fixed submission:
import math
print(math.factorial(int(input())) % (10**9+7))
Buggy python submission (verdict: Time Limit Exceeded):
from fractions import Fraction
from decimal import Decimal

n, k = map(int, input().split())
p = list(map(int, input().split()))
p = list(map(lambda x: Fraction(x+1)/2, p))

cur = sum(p[:k])
res = cur

for i in range(k, n):
    cur += p[i] - p[i-k]
    res = max(res, cur)

d = Decimal(res.numerator) / Decimal(res.denominator)
print(d)

Fixed submission:
from decimal import Decimal

n, k = map(int, input().split())
p = list(map(int, input().split()))
p = list(map(lambda x: x+1, p))

cur = sum(p[:k])
res = cur

for i in range(k, n):
    cur += p[i] - p[i-k]
    res = max(res, cur)

d = Decimal(res.numerator) / Decimal(2*res.denominator)
print(d)
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int, [input() for i in range(n)]))
a.sort()
print(a[:-1]+a[-1]//2)

Fixed submission:
n = int(input())
a = list(map(int, [input() for i in range(n)]))
a.sort()
print(sum(a[:-1])+a[-1]//2)
Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
h = list(map(int, [input() for i in range(n)]))
h.sort()
res = 10**10
for i in range(k-1, n):
    res = min(res, h[i]-[i-k+1])
print(res)

Fixed submission:
n, k = map(int, input().split())
h = list(map(int, [input() for i in range(n)]))
h.sort()
res = 10**10
for i in range(k-1, n):
    res = min(res, h[i]-h[i-k+1])
print(res)
Buggy python submission (verdict: Runtime Error):
from collections import deque
n = int(input())
q = deque()
q.append('')
res = set()
while q:
    m = q.pop_front()
    for c in '357':
        if int(m+c) > n: continue
        q.append(m+c)
    for c in '357':
        if c not in m: break
    else:
        res.add(m)
print(len(res))

Fixed submission:
from collections import deque
n = int(input())
q = deque()
q.append('')
res = set()
while q:
    m = q.popleft()
    for c in '357':
        if int(m+c) > n: continue
        q.append(m+c)
    for c in '357':
        if c not in m: break
    else:
        res.add(m)
print(len(res))
Buggy python submission (verdict: Runtime Error):
N, S = (input() for i in 'NS')
res = 0
for i in range(N):
    s, t = set(S[:i]), set(S[i:])
    res = max(res, len(s.intersection(t)))
print(res)

Fixed submission:
N, S = (input() for i in 'NS')
res = 0
for i in range(int(N)):
    s, t = set(S[:i]), set(S[i:])
    res = max(res, len(s.intersection(t)))
print(res)
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

res = 0
for i in range(n):
    res = max(res, a[:i+1]+b[i:])
    
print(res)

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

res = 0
for i in range(n):
    res = max(res, sum(a[:i+1])+sum(b[i:]))
    
print(res)
Buggy python submission (verdict: Runtime Error):
x, y = map(int, raw_input().split())
print (a+b+1)/2

Fixed submission:
a, b = map(int, raw_input().split())
print (a+b+1)/2