Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
A=list(map(int,input().split()))

dp=[[-10**12]*(n+1) for i in range(n+1)]
#dp[i][j]:=A[j:j+i+1]
if n%2==0:
  for i in range(n):
    dp[0][i]=-1*A[i]
  for i in range(1,n+1):
    for j in range(n-i):
      if i%2==1:
        if j+i==n:
          dp[i][j]=dp[i-1][j+1]+A[j]
        else:
          dp[i][j]=max(dp[i-1][j]+A[j+i],dp[i-1][j+1]+A[j])
      else:
        if j+i==n:
          dp[i][j]=dp[i-1][j+1]-A[j]
        else:
          dp[i][j]=min(dp[i-1][j]-A[j+i],dp[i-1][j+1]-A[j])
else:
  for i in range(n):
    dp[0][i]=A[i]
  for i in range(1,n+1):
    for j in range(n-i):
      if i%2==0:
        if j+i==n:
          dp[i][j]=dp[i-1][j+1]+A[j]
        else:
          dp[i][j]=max(dp[i-1][j]+A[j+i],dp[i-1][j+1]+A[j])
      else:
        if j+i==n:
          dp[i][j]=dp[i-1][j+1]-A[j]
        else:
          dp[i][j]=min(dp[i-1][j]-A[j+i],dp[i-1][j+1]-A[j])
print(dp[n-1][0])

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

dp=[[-10**12]*(n+1) for i in range(n+1)]
#dp[i][j]:=A[j:j+i+1]
if n%2==0:
  for i in range(n):
    dp[0][i]=-1*A[i]
  for i in range(1,n+1):
    for j in range(n-i):
      if i%2==1:
        if j+i==n:
          dp[i][j]=dp[i-1][j+1]+A[j]
        else:
          dp[i][j]=max(dp[i-1][j]+A[j+i],dp[i-1][j+1]+A[j])
      else:
        if j+i==n:
          dp[i][j]=dp[i-1][j+1]-A[j]
        else:
          dp[i][j]=min(dp[i-1][j]-A[j+i],dp[i-1][j+1]-A[j])
else:
  for i in range(n):
    dp[0][i]=A[i]
  for i in range(1,n+1):
    for j in range(n-i):
      if i%2==0:
        if j+i==n:
          dp[i][j]=dp[i-1][j+1]+A[j]
        else:
          dp[i][j]=max(dp[i-1][j]+A[j+i],dp[i-1][j+1]+A[j])
      else:
        if j+i==n:
          dp[i][j]=dp[i-1][j+1]-A[j]
        else:
          dp[i][j]=min(dp[i-1][j]-A[j+i],dp[i-1][j+1]-A[j])
print(dp[n-1][0])
Buggy python submission (verdict: Runtime Error):
h,w,k=map(int,input().split())
mod=10**9+7
fib=[1,1]
for i in range(6):
  fib.append(fib[-2]+fib[-1])
print(fib)
dp=[[0]*w for i in range(h+1)]
dp[0][0]=1
for i in range(h):
  for j in range(w):
    if j==0:
      dp[i+1][j]=(dp[i][j]*fib[j]*fib[w-j-1]+dp[i][j+1]*fib[j]*fib[w-j-2])%(mod)
    elif j==w-1:
      dp[i+1][j]=(dp[i][j-1]*fib[j-1]*fib[w-j-1]+dp[i][j]*fib[j]*fib[w-j-1])%(mod)
    else:
      dp[i+1][j]=(dp[i][j-1]*fib[j-1]*fib[w-j-1]+dp[i][j]*fib[j]*fib[w-j-1]+dp[i][j+1]*fib[j]*fib[w-j-2])%(mod)
print(dp[h][k-1])

Fixed submission:
h,w,k=map(int,input().split())
mod=10**9+7
fib=[1,1]
for i in range(6):
  fib.append(fib[-2]+fib[-1])
dp=[[0]*w for i in range(h+1)]
dp[0][0]=1
for i in range(h):
  for j in range(w):
    if w==1:
      dp[i+1][j]=dp[i][j]
    elif j==0:
      dp[i+1][j]=(dp[i][j]*fib[j]*fib[w-j-1]+dp[i][j+1]*fib[j]*fib[w-j-2])%(mod)
    elif j==w-1:
      dp[i+1][j]=(dp[i][j-1]*fib[j-1]*fib[w-j-1]+dp[i][j]*fib[j]*fib[w-j-1])%(mod)
    else:
      dp[i+1][j]=(dp[i][j-1]*fib[j-1]*fib[w-j-1]+dp[i][j]*fib[j]*fib[w-j-1]+dp[i][j+1]*fib[j]*fib[w-j-2])%(mod)
print(dp[h][k-1])
Buggy python submission (verdict: Runtime Error):
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 2*10**5+5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


n,m=map(int,input().split())
A=factorization(m)
if m==1:
  print(1)
else:
  ans=1
  for i in range(len(A)):
    ans=ans*cmb(n+A[i][1]-1,A[i][1],mod)
print(ans%(10**9+7))

Fixed submission:
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 2*10**5+5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


n,m=map(int,input().split())
A=factorization(m)
ans=1
if m==1:
  print(ans)
else:
  for i in range(len(A)):
    ans=ans*cmb(n+A[i][1]-1,A[i][1],mod)
  print(ans%(10**9+7))
Buggy python submission (verdict: Runtime Error):
def cmb(n,r):
  if n<=0:
    return 0
  elif r<0:
    return 0
  elif r>n:
    return 0
  elif r==0:
    return 1
  elif r==n:
    return 1
  else:
    return A[n]*B[r]*B[n-r]%mod
mod=998244353
A=[1,1]
B=[1,1]
for i in range(2,4005):
  A.append(A[-1]*i%mod)
  B.append(B[-1]*pow(i,mod-2,mod))
k,n=map(int,input().split())
ans=[0]*(2*k+1)
for i in range(2,k+3):#i,i+1(i%2=0,i<k(くらい))で同じとか自明か？？？？？
  if i%2==0:
    i=i+1
    for j in range(min(n+1,i//2+1)):
      ans[i-1]=ans[i-1]+cmb(n+k-i,k-i+j)*cmb(i//2,j)*pow(2,j,mod)
  else:
    for j in range(min(n+1,i//2+1)):
      ans[i]=ans[i]+cmb(n+k-i,k-i+j)*cmb(i//2,j)*pow(2,j,mod)

for i in range(k+2,2*k+1):
  ans[i]=ans[2*k+2-i]
for i in range(2,2*k+1):
  print(ans[i])

Fixed submission:
def cmb(n,r):
  if n<0:
    return 0
  if n==0:
    if r!=0:
      return 0
    else:
      return 1
  elif r<0:
    return 0
  elif r>n:
    return 0
  elif r==0:
    return 1
  elif r==n:
    return 1
  else:
    return A[n]*B[r]*B[n-r]%mod
mod=998244353
A=[1,1]
B=[1,1]
for i in range(2,4005):
  A.append(A[-1]*i%mod)
  B.append(B[-1]*pow(i,mod-2,mod)%mod)
k,n=map(int,input().split())
if k==1:
  print(0)
  exit()
ans=[0]*(2*k+1)
for i in range(2,k+3):#i,i+1(i%2=0,i<k(くらい))で同じとか自明か？？？？？
  if i%2==0:
    i=i+1
    for j in range(min(n+1,i//2+1)):
      ans[i-1]=(ans[i-1]+cmb(n+k-i,k-i+j)*cmb(i//2,j)*pow(2,j,mod))%mod
  else:
    ans[i]=ans[i-1]
for i in range(k+2,2*k+1):
  ans[i]=ans[2*k+2-i]
for i in range(2,2*k+1):
  print(ans[i])

Buggy python submission (verdict: Runtime Error):
def cmb(n,r):
  if n<=0:
    return 0
  elif r<0:
    return 0
  elif r>n:
    return 0
  elif r==0:
    return 1
  elif r==n:
    return 1
  else:
    return A[n]*B[r]*B[n-r]%mod
mod=998244353
A=[1,1]
B=[1,1]
for i in range(2,4005):
  A.append(A[-1]*i%mod)
  B.append(B[-1]*pow(i,mod-2,mod))
k,n=map(int,input().split())
ans=[0]*(2*k+1)
for i in range(2,k+3):#i,i+1(i%2=0,i<k(くらい))で同じとか自明か？？？？？
  if i%2==0:
    i=i+1
    for j in range(min(n+1,i//2+1)):
      ans[i-1]=ans[i-1]+cmb(n+k-i,k-i+j)*cmb(i//2,j)*pow(2,j,mod)
  else:
    for j in range(min(n+1,i//2+1)):
      ans[i]=ans[i]+cmb(n+k-i,k-i+j)*cmb(i//2,j)*pow(2,j,mod)

for i in range(k+2,2*k+1):
  ans[i]=ans[2*k+2-i]
for i in range(2,2*k+1):
  print(ans[i])

Fixed submission:
def cmb(n,r):
  if n<0:
    return 0
  if n==0:
    if r!=0:
      return 0
    else:
      return 1
  elif r<0:
    return 0
  elif r>n:
    return 0
  elif r==0:
    return 1
  elif r==n:
    return 1
  else:
    return A[n]*B[r]*B[n-r]%mod
mod=998244353
A=[1,1]
B=[1,1]
for i in range(2,4005):
  A.append(A[-1]*i%mod)
  B.append(B[-1]*pow(i,mod-2,mod)%mod)
k,n=map(int,input().split())
if k==1:
  print(0)
  exit()
ans=[0]*(2*k+1)
for i in range(2,k+3):#i,i+1(i%2=0,i<k(くらい))で同じとか自明か？？？？？
  if i%2==0:
    i=i+1
    for j in range(min(n+1,i//2+1)):
      ans[i-1]=(ans[i-1]+cmb(n+k-i,k-i+j)*cmb(i//2,j)*pow(2,j,mod))%mod
  else:
    ans[i]=ans[i-1]
for i in range(k+2,2*k+1):
  ans[i]=ans[2*k+2-i]
for i in range(2,2*k+1):
  print(ans[i])
Buggy python submission (verdict: Runtime Error):
import bisect
n=int(input())
A=list(map(int,input().split()))
S=[A[0]]
for i in range(n-1):
  S.append(S[-1]+A[i+1])
ans=10**15
for i in range(2,n-1):
  A1=A[0:i]
  A2=A[i:n]
  if len(A1)==2:
    M1=max(A1)
    m1=min(A1)
  else:
    x=bisect.bisect_left(S,S[i-1]//2,lo=0,hi=i+1)
    M11=max(S[x-1],S[i-1]-S[x-1])
    m11=min(S[x-1],S[i-1]-S[x-1])
    M12=max(S[x],S[i-1]-S[x])
    m12=min(S[x],S[i-1]-S[x])
    M1=min(M11,M12)
    m1=max(m11,m12)
  S2=[A[i]]
  for i in range(i+1,n):
    S2.append(S2[-1]+A[i])
  if len(A2)==2:
    M2=max(A2)
    m2=min(A2)
  else:
    x=bisect.bisect_left(S2,S2[-1]//2,lo=0,hi=len(S2))
    M21=max(S2[x-1],S2[-1]-S2[x-1])
    m21=min(S2[x-1],S2[-1]-S2[x-1])
    M22=max(S2[x],S2[-1]-S2[x])
    m22=min(S2[x],S2[-1]-S2[x])
    M2=min(M21,M22)
    m2=max(m21,m22)
  a=max(M1,M2)-min(m1,m2)
  if a<ans:
    ans=a
print(ans)

Fixed submission:
n=int(input())
if n%2==0:
  print(n)
else:
  print(2*n)
Buggy python submission (verdict: Time Limit Exceeded):
s=input()
k=int(input())
ans=["zzzzzz"]*k
for i in range(len(s)):
  for j in range(i,len(s)):
    A=s[i:j+1]
    if A>ans[k-1]:
      continue
    if A in ans:
      continue
    for ii in range(k):
      if A<ans[ii]:
        break
    for jj in range(k-1,ii,-1):
      ans[jj]=ans[jj-1]
    ans[ii]=A
print(ans[-1])

Fixed submission:
s=input()
k=int(input())
ans=["zzzzzz"]*k
for i in range(len(s)):
  for j in range(i,min(i+8,len(s))):
    A=s[i:j+1]
    if A>ans[k-1]:
      continue
    if A in ans:
      continue
    for ii in range(k):
      if A<ans[ii]:
        break
    for jj in range(k-1,ii,-1):
      ans[jj]=ans[jj-1]
    ans[ii]=A
print(ans[-1])

Buggy python submission (verdict: Time Limit Exceeded):
s=input()
k=int(input())
ans=["zzzzzz"]*k
for i in range(len(s)):
  for j in range(i,len(s)):
    A=s[i:j+1]
    if A>ans[k-1]:
      continue
    if A in ans:
      continue
    for ii in range(k):
      if A<ans[ii]:
        break
    for jj in range(k-1,ii,-1):
      ans[jj]=ans[jj-1]
    ans[ii]=A
print(ans[-1])

Fixed submission:
s=input()
k=int(input())
ans=["zzzzzz"]*k
for i in range(len(s)):
  for j in range(i,min(i+8,len(s))):
    A=s[i:j+1]
    if A>ans[k-1]:
      continue
    if A in ans:
      continue
    for ii in range(k):
      if A<ans[ii]:
        break
    for jj in range(k-1,ii,-1):
      ans[jj]=ans[jj-1]
    ans[ii]=A
print(ans[-1])
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
print(0)
A=[-1]*n
S=input()
if S=="Vacant":
  exit()
elif S=="Male":
  A[0]=0
else:
  A[0]=1
l=0
r=n
while r-l!=0:
  mid=(l+r)//2
  print(mid)
  S=input()
  if S=="Vacant":
    exit()
  elif S=="Male":
    A[mid]=0
  else:
    A[mid]=1
  if (mid-l)%2==(A[l]+A[mid])%2:
    r=mid
  else:
    l=mid

Fixed submission:
n=int(input())
print(0)
A=[-1]*n
S=input()
if S=="Vacant":
  exit()
elif S=="Male":
  A[0]=0
else:
  A[0]=1
l=0
r=n
while r-l!=0:
  mid=(l+r)//2
  print(mid)
  S=input()
  if S=="Vacant":
    exit()
  elif S=="Male":
    A[mid]=0
  else:
    A[mid]=1
  if (mid-l)%2!=(A[l]+A[mid])%2:
    r=mid
  else:
    l=mid

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
print(0)
A={}
S=input()
if S=="Vacant":
  exit()
elif S=="Male":
  A.update(0=0)
else:
  A.update(0=1)
print(n-1)
S=input()
if S=="Vacant":
  exit()
elif S=="Male":
  A.update(n-1=0)
else:
  A.update(n-1=1)
l=0
r=n-1
while r-l!=0:
  mid=(l+r)//2
  print(mid)
  S=input()
  if S=="Vacant":
    exit()
  elif S=="Male":
    A.update(mid=0)
  else:
    A.update(mid=1)
  if (mid-l)%2==(A[l]+A[mid])%2:
    r=mid
  else:
    l=mid

Fixed submission:
n=int(input())
print(0)
A=[-1]*n
S=input()
if S=="Vacant":
  exit()
elif S=="Male":
  A[0]=0
else:
  A[0]=1
l=0
r=n
while r-l!=0:
  mid=(l+r)//2
  print(mid)
  S=input()
  if S=="Vacant":
    exit()
  elif S=="Male":
    A[mid]=0
  else:
    A[mid]=1
  if (mid-l)%2!=(A[l]+A[mid])%2:
    r=mid
  else:
    l=mid

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
print(0)
A={}
S=input()
if S=="Vacant":
  exit()
elif S=="Male":
  A.append({0,0})
else:
  A.append({0,1})
print(n-1)
S=input()
if S=="Vacant":
  exit()
elif S=="Male":
  A.append({n-1,0})
else:
  A.append({n-1,1})
l=0
r=n-1
while r-l!=0:
  mid=(l+r)//2
  print(mid)
  S=input()
  if S=="Vacant":
    exit()
  elif S=="Male":
    A.append({mid,0})
  else:
    A.append({mid,1})
  if (mid-l)%2==(A[l]+A[mid])%2:
    r=mid
  else:
    l=mid

Fixed submission:
n=int(input())
print(0)
A=[-1]*n
S=input()
if S=="Vacant":
  exit()
elif S=="Male":
  A[0]=0
else:
  A[0]=1
l=0
r=n
while r-l!=0:
  mid=(l+r)//2
  print(mid)
  S=input()
  if S=="Vacant":
    exit()
  elif S=="Male":
    A[mid]=0
  else:
    A[mid]=1
  if (mid-l)%2!=(A[l]+A[mid])%2:
    r=mid
  else:
    l=mid

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
print(0)
A=[-1]*n
S=input()
if S=="Vacant":
  exit()
elif S=="Male":
  A[0]=0
else:
  A[0]=1
print(n-1)
S=input()
if S=="Vacant":
  exit()
elif S=="Male":
  A[n-1]=0
else:
  A[n-1]=1
l=0
r=n-1
while r-l!=0:
  mid=(l+r)//2
  print(mid)
  S=input()
  if S=="Vacant":
    exit()
  elif S=="Male":
    A[mid]=0
  else:
    A[mid]=1
  if (mid-l)%2==(A[l]+A[mid])%2:
    r=mid
  else:
    l=mid

Fixed submission:
n=int(input())
print(0)
A=[-1]*n
S=input()
if S=="Vacant":
  exit()
elif S=="Male":
  A[0]=0
else:
  A[0]=1
l=0
r=n
while r-l!=0:
  mid=(l+r)//2
  print(mid)
  S=input()
  if S=="Vacant":
    exit()
  elif S=="Male":
    A[mid]=0
  else:
    A[mid]=1
  if (mid-l)%2!=(A[l]+A[mid])%2:
    r=mid
  else:
    l=mid
Buggy python submission (verdict: Time Limit Exceeded):
import bisect
q=int(input())
P=[2]
for i in range(3,10**5+2):
  for j in range(len(P)):
    if i%P[j]==0:
      break
    if j==len(P)-1:
      P.append(i)
p=set(P)
A=[]
for i in range(len(P)):
  if (P[i]+1)//2 in p:
    A.append(P[i])
for i in range(q):
  a,b=map(int,input().split())
  print(bisect.bisect_right(A,b+1,lo=0,hi=len(A))-bisect.bisect_right(A,a-1,lo=0,hi=len(A)))

Fixed submission:
import bisect
q=int(input())
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]
P=primes(10**5+3)
p=set(P)
A=[]
for i in range(len(P)):
  if (P[i]+1)//2 in p:
    A.append(P[i])
for i in range(q):
  a,b=map(int,input().split())
  print(bisect.bisect_right(A,b+1,lo=0,hi=len(A))-bisect.bisect_right(A,a-1,lo=0,hi=len(A)))
Buggy python submission (verdict: Time Limit Exceeded):
s=input()
x,y=map(int,input().split())
XY=[[]for i in range(2)]
a=0
b=0
for i in range(len(s)):
  if s[i]=="T":
    XY[b].append(a)
    a=0
    b=(b+1)%2
  else:
    a=a+1
XY[b].append(a)
xx=sum(XY[0])
yy=sum(XY[1])
dpx=[[0]*(2*xx+5) for i in range(len(XY[0])+1)]#x=0とj=xx+2を対応させる
dpy=[[0]*(2*yy+5) for i in range(len(XY[1])+1)]#y=0とj=yy+2を対応させる
dpx[1][xx+XY[0][0]+2]=1
for i in range(1,len(XY[0])):
  for j in range(2*xx+5):
    if dpx[i][j]==1:
      dpx[i+1][j-XY[0][i]]=1
      dpx[i+1][j+XY[0][i]]=1
dpy[0][yy+2]=1
for i in range(len(XY[1])):
  for j in range(2*yy+5):
    if dpy[i][j]==1:
      dpy[i+1][j-XY[1][i]]=1
      dpy[i+1][j+XY[1][i]]=1
if x+xx+2<0 or 2*xx+4<x+xx+2 or y+yy+2<0 or 2*yy+4<y+yy+2:
  print("No")
  exit()
if dpx[-1][x+xx+2]==1 and dpy[-1][y+yy+2]==1:
  print("Yes")
else:
  print("No")

Fixed submission:
s=input()
x,y=map(int,input().split())
XY=[[]for i in range(2)]
a=0
b=0
for i in range(len(s)):
  if s[i]=="T":
    XY[b].append(a)
    a=0
    b=(b+1)%2
  else:
    a=a+1
XY[b].append(a)
xx=sum(XY[0])
yy=sum(XY[1])
dpx=[[0]*(2*xx+5) for i in range(len(XY[0])+1)]#x=0とj=xx+2を対応させる
dpy=[[0]*(2*yy+5) for i in range(len(XY[1])+1)]#y=0とj=yy+2を対応させる
dpx[1][xx+XY[0][0]+2]=1
for i in range(1,len(XY[0])):
  for j in range(2*xx+5):
    if dpx[i][j]==1:
      dpx[i+1][j-XY[0][i]]=1
      dpx[i+1][j+XY[0][i]]=1
dpy[0][yy+2]=1
for i in range(len(XY[1])):
  for j in range(2*yy+5):
    if dpy[i][j]==1:
      dpy[i+1][j-XY[1][i]]=1
      dpy[i+1][j+XY[1][i]]=1
if x+xx+2<0 or 2*xx+4<x+xx+2 or y+yy+2<0 or 2*yy+4<y+yy+2:
  print("No")
  exit()
if dpx[-1][x+xx+2]==1 and dpy[-1][y+yy+2]==1:
  print("Yes")
else:
  print("No")
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
t=list(map(int,input().split()))
T=[-1,0]
for i in range(n):
  T.append(T[-1]+t[i])
T.append(T[-1]+1)
V=[0]+list(map(int,input().split()))+[0]
VV=[110]*(2*T[-1]+1)
for i in range(n+2):
  for j in range(2*T[-1]+1):
    if j<2*T[i]:
      a=T[i]-j/2
      VV[j]=min(VV[j],a+V[i])
    elif 2*T[i]<=j and j<=2*T[i+1]:
      VV[j]=min(VV[j],V[i])
    else:
      a=j/2-T[i+1]
      VV[j]=min(VV[j],a+V[i])
print(sum(VV)/2)

Fixed submission:
n=int(input())
t=list(map(int,input().split()))
T=[-1,0]
for i in range(n):
  T.append(T[-1]+t[i])
T.append(T[-1]+1)
V=[0]+list(map(int,input().split()))+[0]
VV=[110]*(2*T[-1]+1)
for i in range(n+2):
  for j in range(2*T[-1]+1):
    if j<2*T[i]:
      a=T[i]-j/2
      VV[j]=min(VV[j],a+V[i])
    elif 2*T[i]<=j and j<=2*T[i+1]:
      VV[j]=min(VV[j],V[i])
    else:
      a=j/2-T[i+1]
      VV[j]=min(VV[j],a+V[i])
print(sum(VV)/2)
Buggy python submission (verdict: Runtime Error):
s=list(input())
s1=[]
for i in range(len(s)):
  if s[i]!="x":
    s1.append(s[i])
s2=s1[::-1]
if s1!=s2:
  print(-1)
  exit()
A1=[0]*10**5
A2=[0]*10**5
i=0
j=0
while i<=len(s1)//2:
  if s[j]=="x":
    A1[i]+=1
    j=j+1
  else:
    i=i+1
    j=j+1
i=0
j=0
while i<=len(s1)//2:
  if s[-1-j]=="x":
    A2[i]+=1
    j=j+1
  else:
    i=i+1
    j=j+1
ans=0
for i in range(10**5):
  ans=ans+abs(A1[i]-A2[i])
print(ans)

Fixed submission:
s=list(input())
s1=[]
for i in range(len(s)):
  if s[i]!="x":
    s1.append(s[i])
s2=s1[::-1]
if s1!=s2:
  print(-1)
  exit()
if s1==[]:
  print(0)
  exit()
A1=[0]*10**5
A2=[0]*10**5
i=0
j=0
while i<=len(s1)//2:
  if s[j]=="x":
    A1[i]+=1
    j=j+1
  else:
    i=i+1
    j=j+1
i=0
j=0
while i<=len(s1)//2:
  if s[-1-j]=="x":
    A2[i]+=1
    j=j+1
  else:
    i=i+1
    j=j+1
ans=0
for i in range(10**5):
  ans=ans+abs(A1[i]-A2[i])
print(ans)
Buggy python submission (verdict: Runtime Error):
from collections import deque
n,m=map(int,input().split())
A=[[0]*2 for i in range(n)]
for i in range(m):
  A[i]=list(map(int,input().split()))
ans=0
for i in range(m):
  B=[[] for i in range(n)]
  for j in range(m):
    if j==i:
      continue
    B[A[j][0]-1].append(A[j][1]-1)
    B[A[j][1]-1].append(A[j][0]-1)
  C=[0]*n
  C[0]=1
  D=deque([0])
  while len(D)>0:
    x=D[0]
    D.popleft()
    for j in range(len(B[x])):
      if C[B[x][j]]==0:
        D.append(B[x][j])
        C[B[x][j]]=1
  if C!=[1]*n:
    ans=ans+1
print(ans)

Fixed submission:
from collections import deque
n,m=map(int,input().split())
A=[[0]*2 for i in range(m)]
for i in range(m):
  A[i]=list(map(int,input().split()))
ans=0
for i in range(m):
  B=[[] for i in range(n)]
  for j in range(m):
    if j==i:
      continue
    B[A[j][0]-1].append(A[j][1]-1)
    B[A[j][1]-1].append(A[j][0]-1)
  C=[0]*n
  C[0]=1
  D=deque([0])
  while len(D)>0:
    x=D[0]
    D.popleft()
    for j in range(len(B[x])):
      if C[B[x][j]]==0:
        D.append(B[x][j])
        C[B[x][j]]=1
  if C!=[1]*n:
    ans=ans+1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import copy
def warshall_floyd(d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
n,m,r=map(int,input().split())
R=list(map(int,input().split()))
for i in range(r):
  R[i]=R[i]-1
d=[[10**10]*n for i in range(n)] 
for i in range(m):
  a,b,c=map(int,input().split())
  a=a-1
  b=b-1
  d[a][b]=c
  d[b][a]=c
for i in range(n):
  d[i][i]=0
D=warshall_floyd(d)
s=1
S=[]
for i in range(1,r+1):
  s=s*i
  S.append(s)
ans=10**10
for i in range(s):
  RR=copy.copy(R)
  E=[]
  for j in range(r-1):
    E.append(RR[i//S[r-j-2]])
    RR.pop(i//S[r-j-2])
    i=i-S[r-j-2]*(i//S[r-j-2])
  E.append(RR[0]) 
  di=0
  for i in range(r-1):
    di=di+D[E[i]][E[i+1]]
  if di<ans:
    ans=di
print(ans)

Fixed submission:
import copy
def warshall_floyd(d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
n,m,r=map(int,input().split())
R=list(map(int,input().split()))
for i in range(r):
  R[i]=R[i]-1
d=[[10**10]*n for i in range(n)] 
for i in range(m):
  a,b,c=map(int,input().split())
  a=a-1
  b=b-1
  d[a][b]=c
  d[b][a]=c
for i in range(n):
  d[i][i]=0
D=warshall_floyd(d)
s=1
S=[]
for i in range(1,r+1):
  s=s*i
  S.append(s)
ans=10**10
for i in range(s):
  RR=copy.copy(R)
  E=[]
  for j in range(r-1):
    E.append(RR[i//S[r-j-2]])
    RR.pop(i//S[r-j-2])
    i=i-S[r-j-2]*(i//S[r-j-2])
  E.append(RR[0]) 
  di=0
  for i in range(r-1):
    di=di+D[E[i]][E[i+1]]
  if di<ans:
    ans=di
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
A=[[0]*m for i in range(n)]
for i in range(n):
  A[i]=list(map(int,input().split()))
B=[0]*m
for i in range(n):
  B[A[i][0]-1]+=1
a=0
b=0
for i in range(m):
  if B[i]>a:
    a=B[i]
    b=i
ans=a
C=[b+1]
i=0
while i<=m-2:
  B=[0]*m
  for j in range(n):
    for k in range(m):
      if A[j][k] not in C:
        B[A[j][k]-1]+=1
        break
  a=0
  b=0
  for l in range(m):
    if B[l]>a:
      a=B[l]
      b=l
  if ans>a:
    ans=a
  C.append(b+1)
  i=i+1
print(ans)

Fixed submission:
n,m=map(int,input().split())
A=[[0]*m for i in range(n)]
for i in range(n):
  A[i]=list(map(int,input().split()))
B=[0]*m
for i in range(n):
  B[A[i][0]-1]+=1
a=0
b=0
for i in range(m):
  if B[i]>a:
    a=B[i]
    b=i
ans=a
C=[b+1]
i=0
while i<=m-2:
  B=[0]*m
  for j in range(n):
    for k in range(m):
      if A[j][k] not in C:
        B[A[j][k]-1]+=1
        break
  a=0
  b=0
  for l in range(m):
    if B[l]>a:
      a=B[l]
      b=l
  if ans>a:
    ans=a
  C.append(b+1)
  i=i+1
print(ans)
Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
A=[["."]*n for i in range(n)]
B=[["."]*m for i in range(m)]
for i in range(n):
  A[i]=list(input())
for i in range(m):
  B[i]=list(input())
for i in range(n-m+1):
  for j in range(n-m+1):
    a=0
    for x in range(m):
      for y in range(m):
        if A[i+x][j+y]!=B[x][y]:
          a=1
          break
    if a==0:
      print("Yes")
      exit()
print("No")

Fixed submission:
import itertools
n,m=map(int,input().split())
G=[[0]*n for i in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  G[a-1][b-1]=1
  G[b-1][a-1]=1
S=""
for i in range(1,n):
  S=S+str(i)
ans=0
for x in itertools.permutations(S):
  a=0
  if G[0][int(x[0])]==0:
    a=1
  for i in range(n-2):
    if G[int(x[i])][int(x[i+1])]==0:
      a=1
  if a==0:
    ans=ans+1
print(ans)
Buggy python submission (verdict: Runtime Error):
n=int(input())
s=input()
a=0
b=0
for i in range(n-1):
  if s[i]=="I":
    a=a+1
    if a>b:
      b=a
  else:
    a=a-1
print(b)

Fixed submission:
a,b,c,d=map(int,input().split())
print(max(a*b,c*d))