Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
s=input()
l=len(s)
ans=0
for i in range(l):
  for j in range(1,l):
    t=s[i:i+j]
    for k in range(j):
      if t[k] not in ['A','C','G','T']:
        break
    else:
      ans=max(ans,j-i+1)
print(ans)

Fixed submission:
s=str(input())
count=0
tmp=0
for i in range(len(s)):
  if s[i]=='A' or s[i]=='T' or s[i]=='G' or s[i]=='C':
    count += 1
  else:
    count=0
  if count>tmp:
    tmp=count
print(tmp)
Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
s=input()
for i in range(m):
  a,b=map(int,input().split())
  count=0
  tmp=s[a-1:b]
  for j in range(len(tmp)-1):
    if tmp[j]=='A' and tmp[j+1]=='C':
      count+=1
  print(count)
  count=0

Fixed submission:
n,m=map(int,input().split())
s=input()
ans=[0]*n
count=0
for i in range(n-1):
  ans[i]=count
  if s[i]=='A' and s[i+1]=='C':
    count+=1
ans[n-1]=count
for i in range(m):
  a,b=map(int,input().split())
  print(ans[b-1]-ans[a-1])
Buggy python submission (verdict: Runtime Error):
n=int(input())
ans=[]
if n%2==0:
  for i in range((n-1)//2):
    for j in range(i+1,n-i):
      if i==0:
        ans.aopend(((n-i),j))
      else:
        ans.append((i,j))
        ans.append(((n-i),j))
if n2%==1:
  for i in range(1,n//2):
    for j in range(i+1,n-i):
      ans.append((i,j))
      ans.append(((n-i),j))
print(len(ans))
for u,v in ans:
  print(u,v)

Fixed submission:
n=int(input())
ans=[]
if n%2==1:
  for i in range((n-1)//2):
    for j in range(i+1,n-i):
      if i==0:
        ans.append(((n-i),j))
      else:
        ans.append((i,j))
        ans.append(((n-i),j))
elif n%2==0:
  for i in range(1,n//2):
    for j in range(i+1,n-i+1):
      ans.append((i,j))
      ans.append(((n-i+1),j))
print(len(ans))
for u,v in ans:
  print(u,v)
Buggy python submission (verdict: Runtime Error):
a,b=map(int,input().split())
if b-a<=3:
  ans=a
  for i in range(a+1,b+1):
    ans=ans^i
  print(ans)
else:
  if a%4!=0:
    ans=a
    for i in range(a+1,(a//4)*4+2):
      ans=ans^i
  ans2=b
  for i in range(b+1,(b//4)*4+1):
    ans2=ans2^i
  print(ans^ans2)

Fixed submission:
a,b=map(int,input().split())
if b-a<=3:
  ans=0
  for i in range(a,b+1):
    ans=ans^i
  print(ans)
else:
  ans=0
  if a%4!=0:
    for i in range(a,(1+a//4)*4):
      ans=ans^i
  ans2=0
  for i in range((b//4)*4,b+1):
    ans2=ans2^i
  print(ans^ans2)
Buggy python submission (verdict: Runtime Error):
a,b,k=map(int,input().split())
count=0
ans=0
for i in range(200):
  if a%i==0 and b%i==0:
    count+=1
  if count==k:
    ans=i
print(ans)

Fixed submission:
a,b,k=map(int,input().split())
ans=[]
for i in range(1,200):
  if a%i==0 and b%i==0:
    ans.append(i)
print(ans[-k])
Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
count=[0]*m
ans=0
list=[]
for i in range(n):
  list.append(list(map(int,input().split())))
  for j in range(1,list[i][0]+1):
    count[list[i][j]-1]+=1
for i in range(m):
  if count[i]==n:
    ans+=1
print(ans)

Fixed submission:
n,m=map(int,input().split())
count=[0]*m
ans=0
arr=[]
for i in range(n):
  arr.append(list(map(int,input().split())))
  for j in range(1,arr[i][0]+1):
    count[arr[i][j]-1]+=1
for i in range(m):
  if count[i]==n:
    ans+=1
print(ans)

Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
count=[0]*m
ans=0
list=[]
for i in range(n):
  list.append(list(map(int,input().split())))
  for j in range(1,list[i][0]+1):
    count[list[i][j]]+=1
for i in range(m):
  if count[i]==n:
    ans+=1
print(ans)

Fixed submission:
n,m=map(int,input().split())
count=[0]*m
ans=0
arr=[]
for i in range(n):
  arr.append(list(map(int,input().split())))
  for j in range(1,arr[i][0]+1):
    count[arr[i][j]-1]+=1
for i in range(m):
  if count[i]==n:
    ans+=1
print(ans)

Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
count=[0]*m
ans=0
list=[]
for i in range(n):
  list.append(list(map(int,input().split())))
  for j in range(1,list[i][0]+1):
    count[j]+=1
for i in range(m):
  if count[i]==n:
    ans+=1
print(ans)

Fixed submission:
n,m=map(int,input().split())
count=[0]*m
ans=0
arr=[]
for i in range(n):
  arr.append(list(map(int,input().split())))
  for j in range(1,arr[i][0]+1):
    count[arr[i][j]-1]+=1
for i in range(m):
  if count[i]==n:
    ans+=1
print(ans)

Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
count=[0]*m
ans=0
list=[]
for i in range(n):
  list.append(list(map(int,input().split())))
  for j in range(1,list[1][0]+1):
    count[j]+=1
for i in range(m):
  if count[i]==n:
    ans+=1
print(ans)


Fixed submission:
n,m=map(int,input().split())
count=[0]*m
ans=0
arr=[]
for i in range(n):
  arr.append(list(map(int,input().split())))
  for j in range(1,arr[i][0]+1):
    count[arr[i][j]-1]+=1
for i in range(m):
  if count[i]==n:
    ans+=1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)

def multigcd(n,arr):
  a,b=max(n,arr[0]),min(n,arr[0])
  while b!=0:
    a,b=b,a%b
  if len(arr)==1:
    return a
  else:
    return multigcd(a,arr[1:])

n=int(input())
arr=list(map(int,input().split()))
print(multigcd(arr[0],arr[1:]))

Fixed submission:
def gcd(a,b):
  a,b=max(a,b),min(a,b)
  if b==0:
    return a
  else:
    return gcd(b,a%b)
 
n=int(input())
arr=list(map(int,input().split()))
tmp=gcd(arr[0],arr[1])
for i in range(1,n):
  tmp=gcd(tmp,arr[i])
print(tmp)

Buggy python submission (verdict: Runtime Error):
def multigcd(n,arr):
  a,b=max(n,arr[0]),min(n,arr[0])
  while b!=0:
    a,b=b,a%b
  if len(arr)==1:
    return a
  else:
    return multigcd(a,arr[1:])

n=int(input())
arr=list(map(int,input().split()))
print(multigcd(arr[0],arr[1:]))

Fixed submission:
def gcd(a,b):
  a,b=max(a,b),min(a,b)
  if b==0:
    return a
  else:
    return gcd(b,a%b)
 
n=int(input())
arr=list(map(int,input().split()))
tmp=gcd(arr[0],arr[1])
for i in range(1,n):
  tmp=gcd(tmp,arr[i])
print(tmp)

Buggy python submission (verdict: Runtime Error):
def gcd(a,b):
  a,b=max(a,b),min(a,b)
  if b==0:
    return a
  else:
    return gcd(b,a%b)
 
n=int(input())
arr=list(map(int,input()))
tmp=gcd(arr[0],arr[1])
for i in range(1,n):
  tmp=gcd(tmp,arr[i])
print(tmp)

Fixed submission:
def gcd(a,b):
  a,b=max(a,b),min(a,b)
  if b==0:
    return a
  else:
    return gcd(b,a%b)
 
n=int(input())
arr=list(map(int,input().split()))
tmp=gcd(arr[0],arr[1])
for i in range(1,n):
  tmp=gcd(tmp,arr[i])
print(tmp)

Buggy python submission (verdict: Runtime Error):
def gcd(a,b):
  a,b=max(a,b),min(a,b)
  if b==0:
    return a
  else:
    return gcd(b,a%b)

n=int(input())
arr=list(map(int,input()))
for i in range(n-1):
  tmp=gcd(arr[i],arr[i+1])
print(tmp)

Fixed submission:
def gcd(a,b):
  a,b=max(a,b),min(a,b)
  if b==0:
    return a
  else:
    return gcd(b,a%b)
 
n=int(input())
arr=list(map(int,input().split()))
tmp=gcd(arr[0],arr[1])
for i in range(1,n):
  tmp=gcd(tmp,arr[i])
print(tmp)
Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
arr=list(map(int,input().split()))
arr=sorted(arr,reverse=True)
dic={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
dp=[0]*(n+1)
for i in range(n+1):
  for val in arr:
    if i-dic[val]<0:
      continue
    else:
      dp[i]=max(dp[i],dp[i-dic[val]]+1)
ans=''
tmp=n
while tmp>0:
  for val in arr:
    if tmp-dic[val]<0:
      continue
    if dp[tmp]==dp[tmp-dic[val]]+1:
      ans+=str(val)
      tmp-=dic[val]
      break
  else:
    break
last=dic[int(ans[-1])]
cand=[]
for val in arr:
  if dic[val]-last==tmp:
    cand.append(val)
cand=sorted(cand,reverse=True)
ans=ans[:-1]+str(cand[0])
print(ans)

Fixed submission:
n,m=map(int,input().split())
arr=list(map(int,input().split()))
arr=sorted(arr,reverse=True)
dic={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
dp=[-1]*(n+1)
dp[0]=0
for i in range(n+1):
  for val in arr:
    if i-dic[val]<0:
      continue
    else:
      dp[i]=max(dp[i],dp[i-dic[val]]+1)
ans=''
tmp=n
while tmp>0:
  for val in arr:
    if tmp-dic[val]<0:
      continue
    if dp[tmp]==dp[tmp-dic[val]]+1 and dp[tmp-dic[val]]!=-1:
      ans+=str(val)
      tmp-=dic[val]
      break
print(ans)
Buggy python submission (verdict: Runtime Error):
import(math)

a,b=map(int,input().split())
if math.ceil(a/2)>=b:
  print('YES')
else:
  print('NO')

Fixed submission:
import math
 
a,b=map(int,input().split())
if math.ceil(a/2)>=b:
  print('YES')
else:
  print('NO')
Buggy python submission (verdict: Runtime Error):
n=int(input())
arr=[int(input()) for _ in range(n)]
arr=sorted(arr)
total=sum(arr[:-1])
if arr[-1]<total:
  print('Yes')
else:
  print('No')

Fixed submission:
n=int(input())
arr=list(map(int,input().split()))
arr=sorted(arr)
total=sum(arr[:-1])
if arr[-1]<total:
  print('Yes')
else:
  print('No')
Buggy python submission (verdict: Time Limit Exceeded):
def calc():
  n,k=map(int,input().split())
  arr=list(map(int,input().split()))
  flag=format(k,'b')[::-1]
  l=len(flag)
  xor1=0
  cnt=0
  for i in range(l-2,-1,-1):
    for j in arr:
      if j&(2**i)!=0:
        cnt+=1
    if cnt<=n//2:
      xor1+=2**i
    cnt=0
  ans1=0
  for i in arr:
    ans1+=i^xor1
  xor2=0
  cnt=0
  check=False
  for i in range(l-1,-1,-1):
    if check==False and flag[i]=='0':
      continue
    for j in arr:
      if j&(2**i)!=0:
        cnt+=1
    if cnt<=n//2:
      if check==True or flag[i]=='1':
        xor2+=2**i
    else:
      if flag[i]=='1':
        check=True
    cnt=0
  ans2=0
  for i in arr:
    ans2+=i^xor2
  print(max(ans1,ans2))

calc()

Fixed submission:
n,k=map(int,input().split())
arr=list(map(int,input().split()))
flag=format(k,'b')[::-1]
l=len(flag)
xor1=0
cnt=0
for i in range(l-2,-1,-1):
  for j in arr:
    if j&(2**i)!=0:
      cnt+=1
  if cnt<=n//2:
    xor1+=2**i
  cnt=0
ans1=0
for i in arr:
  ans1+=i^xor1
xor2=0
cnt=0
check=False
for i in range(l-1,-1,-1):
  if check==False and flag[i]=='0':
    continue
  for j in arr:
    if j&(2**i)!=0:
      cnt+=1
  if cnt<=n//2:
    if check==True or flag[i]=='1':
      xor2+=2**i
  else:
    if flag[i]=='1':
      check=True
  cnt=0
ans2=0
for i in arr:
  ans2+=i^xor2
print(max(ans1,ans2))

Buggy python submission (verdict: Runtime Error):
n,k=map(int,input().split())
arr=list(map(int,input().split()))
flag=format(k,'b')[::-1]
l=len(flag)
if k==0:
  print(sum(arr))
elif k==1:
  ans1=sum(arr)
  ans2=0
  for j in arr:
    ans2+=j^1
  print(max(ans1,ans2)
else:
  xor1=0
  cnt=0
  for i in range(l-2,-1,-1):
    for j in arr:
      if j&(2**i)!=0:
        cnt+=1
    if cnt<=n//2:
      xor1+=2**i
  ans1=0
  for i in arr:
    ans1+=i^xor1
  xor2=0
  cnt=0
  for i in range(l-1,-1,-1):
    if flag[i]=='0':
      continue
    for j in arr:
      if j&(2**i)!=0:
        cnt+=1
    if cnt<=n//2:
      xor2+=2**i
    cnt=0
  ans2=0
  for i in arr:
    ans2+=i^xor2
  print(max(ans1,ans2))

Fixed submission:
n,k=map(int,input().split())
arr=list(map(int,input().split()))
flag=format(k,'b')[::-1]
l=len(flag)
xor1=0
cnt=0
for i in range(l-2,-1,-1):
  for j in arr:
    if j&(2**i)!=0:
      cnt+=1
  if cnt<=n//2:
    xor1+=2**i
  cnt=0
ans1=0
for i in arr:
  ans1+=i^xor1
xor2=0
cnt=0
check=False
for i in range(l-1,-1,-1):
  if check==False and flag[i]=='0':
    continue
  for j in arr:
    if j&(2**i)!=0:
      cnt+=1
  if cnt<=n//2:
    if check==True or flag[i]=='1':
      xor2+=2**i
  else:
    if flag[i]=='1':
      check=True
  cnt=0
ans2=0
for i in arr:
  ans2+=i^xor2
print(max(ans1,ans2))
Buggy python submission (verdict: Runtime Error):
arr=[j for j in input().split()]
arr=sorted(arr)
print(int(arr[0]*arr[1]/2))

Fixed submission:
a,b,c=map(int,input().split())
arr=[a,b,c]
arr=sorted(arr)
print(int(arr[0]*arr[1]/2))

Buggy python submission (verdict: Runtime Error):
arr=[j for j in input().split()]
arr=sorted(arr)
print(int(arr[0]*arr[1]/2)

Fixed submission:
a,b,c=map(int,input().split())
arr=[a,b,c]
arr=sorted(arr)
print(int(arr[0]*arr[1]/2))
Buggy python submission (verdict: Runtime Error):
s=int(input())
arr=[s]
tmp=0
for i in range(m):
  if arr[i]%2==0:
    tmp=int(arr[i]/2)
  else:
    tmp=arr[i]*3+1
  if tmp in arr:
    print(i+1)
    break
  arr.append(tmp)
  

Fixed submission:
s=int(input())
arr=[s]
tmp=0
for i in range(10**6+1):
  if arr[i]%2==0:
    tmp=int(arr[i]/2)
  else:
    tmp=arr[i]*3+1
  if tmp in arr:
    print(i+2)
    break
  arr.append(tmp)
Buggy python submission (verdict: Runtime Error):
a,b,c,d=map(int,input().split())
arr[a,b,c,d]
if arr.count('1')==1 and arr.count('9')==1 and arr.count('7')==1 and arr.count('4')==1:
  print('YES')
else:
  print('NO')

Fixed submission:
a,b,c,d=map(int,input().split())
arr=[a,b,c,d]
if (arr.count(1)==1 and arr.count(9)==1) and (arr.count(7)==1 and arr.count(4)==1):
  print('YES')
else:
  print('NO')
Buggy python submission (verdict: Runtime Error):
s=input()
pos=0
cnt=0
flag=False
check='keyence'
for i in range(len(s)):
  if s[i]==check[pos]:
    pos+=1
    flag=True
  else:
    if flag==True:
      cnt+=1
      flag=False
if pos==7 and cnt<=1:
  print('YES')
else:
  print('NO')


Fixed submission:
s=input()
flag=1
if s=='keyence':
  flag=0
for i in range(len(s)):
  for j in range(1,len(s)-i+1):
    if (s[:i]+s[i+j:])=='keyence':
      flag*=0
if flag==0:
  print('YES')
else:
  print('NO')

Buggy python submission (verdict: Runtime Error):
s=input()
pos=0
cnt=0
flag=False
check='keyence'
for i in range(len(s)):
  if s[i]==check[pos]:
    pos+=1
    flag=True
  else:
    if flag==True:
      cnt+=1
      flag=False
if pos==7 and flag<=1ju:
  print('YES')
else:
  print('NO')

Fixed submission:
s=input()
flag=1
if s=='keyence':
  flag=0
for i in range(len(s)):
  for j in range(1,len(s)-i+1):
    if (s[:i]+s[i+j:])=='keyence':
      flag*=0
if flag==0:
  print('YES')
else:
  print('NO')
Buggy python submission (verdict: Runtime Error):
n=int(input())
arr=(list(map(int,input().split())))
dp=[0]*n
dp[0]=0
dp[1]=abs(arr[1]-arr[0])
for i in range(2,n):
     dp[i]=min(dp[i-2]+abs(arr[i]-arr[i-2]),dp[i-1]+abs(arr[i]-arr[i-1]))
print(dp[n])

Fixed submission:
n=int(input())
arr=(list(map(int,input().split())))
dp=[0]*n
dp[0]=0
dp[1]=abs(arr[1]-arr[0])
for i in range(2,n):
     dp[i]=min(dp[i-2]+abs(arr[i]-arr[i-2]),dp[i-1]+abs(arr[i]-arr[i-1]))
print(dp[n-1])
Buggy python submission (verdict: Runtime Error):
n=int(input())
dp=[[0 for i in range(n+1)] for j in range(3)]
for i in range(1,n+1):
  a,b,c=map(int,input().split())
  for j in range(3):
    if j==0:
      dp[i][j]=max(dp[i-1][1]+a,dp[i-1][2]+a)
    elif j==1:
      dp[i][j]=max(dp[i-1][0]+b,dp[i-1][2]+b)
    else:
      dp[i][j]=max(dp[i-1][0]+c,dp[i-1][1]+c)
print(max(dp[n][0],dp[n][1],dp[n][2]))

Fixed submission:
n=int(input())
dp=[[0 for i in range(n+1)] for j in range(3)]
for i in range(1,n+1):
  a,b,c=map(int,input().split())
  dp[0][i]=max(dp[1][i-1]+a,dp[2][i-1]+a)
  dp[1][i]=max(dp[0][i-1]+b,dp[2][i-1]+b)
  dp[2][i]=max(dp[0][i-1]+c,dp[1][i-1]+c)
print(max(dp[0][n],dp[1][n],dp[2][n]))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=sys.stdin.readline
 
n,w=map(int,input().split())
dp=[{} for _ in range(n)]
c,p=map(int,input().split())
dp[0][c]=p
 
def ans(n,w):
  for i in range(1,n):
    c,p=map(int,input().split())
    for j in dp[i-1].keys():
      dp[i][j]=dp[i-1][j]
    for j in dp[i-1].keys():
      tmp=dp[i-1][j]+p
      if j+c <= w:
        if j+c in dp[i-1]:
          dp[i][j+c]=max(dp[i-1][j+c],tmp)
        else:
          dp[i][j+c]=tmp
    if c in dp[i-1]:
      dp[i][c]=max(dp[i-1][c],p)
    else:
      dp[i][c]=p
  return max([dp[n-1][i] for i in dp[n-1].keys()])
print(ans(n,w))

Fixed submission:
n,w=map(int,input().split())
dp=[0]*(n*10**3+1)
c,p=map(int,input().split())
dp[p]=c
mpos=p
for _ in range(n-1):
  c,p=map(int,input().split())
  for i in range(mpos+p,0,-1):
    if dp[i-p]!=0:
      if dp[i]==0:
        dp[i]=dp[i-p]+c
      else:
        dp[i]=min(dp[i-p]+c,dp[i])
  if dp[p]==0:
    dp[p]=c
  else:
    dp[p]=min(dp[p],c)
  mpos=mpos+p
ans=0
for i in range(len(dp)):
  if dp[i]<=w and dp[i]!=0:
    ans=i
print(ans)

Buggy python submission (verdict: Runtime Error):
import sys
input=sys.stdin.readline
 
n,w=map(int,input().split())
dp=[0]*(w+1)
 
def ans(n,w):
  for _ in range(n):
    c,p=map(int,input().split())
    for j in range(w,c-1,-1):
      tmp=dp[j-c]+p
      if dp[j]<tmp:
        dp[j]=tmp
  return max(dp)
print(ans(n,w))

Fixed submission:
n,w=map(int,input().split())
dp=[0]*(n*10**3+1)
c,p=map(int,input().split())
dp[p]=c
mpos=p
for _ in range(n-1):
  c,p=map(int,input().split())
  for i in range(mpos+p,0,-1):
    if dp[i-p]!=0:
      if dp[i]==0:
        dp[i]=dp[i-p]+c
      else:
        dp[i]=min(dp[i-p]+c,dp[i])
  if dp[p]==0:
    dp[p]=c
  else:
    dp[p]=min(dp[p],c)
  mpos=mpos+p
ans=0
for i in range(len(dp)):
  if dp[i]<=w and dp[i]!=0:
    ans=i
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def func(num,arr):
  dp=[1]*(n+1)
  dp[0]=(1-arr[0])
  dp[1]=arr[0]
  for i in range(1,n):
    dp[i+1]=dp[i]*arr[i]
    for j in range(1,i+1):
      dp[i+1-j]=dp[i-j]*arr[i]+dp[i+1-j]*(1-arr[i])
    dp[0]=dp[0]*(1-arr[i])
  return dp

n=int(input())
arr=list(map(float,input().split()))
dp=func(n,arr)
ans=0
for i in range(int(n/2)+1,n+1):
  ans+=dp[i]
print(ans)

Fixed submission:
n=int(input())
arr=list(map(float,input().split()))
dp=[1]*(n+1)
dp[0]=(1-arr[0])
dp[1]=arr[0]
for i in range(1,n):
  for j in range(i+2):
    if j==0:
      dp[i+1-j]=dp[i-j]*arr[i]
    elif j==i+1:
      dp[i+1-j]=dp[i+1-j]*(1-arr[i])
    else:
      dp[i+1-j]=dp[i-j]*arr[i]+dp[i+1-j]*(1-arr[i])
ans=0
for i in range(int(n/2)+1,n+1):
  ans+=dp[i]
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
arr=list(map(float,input().split()))
dp=[1]*(n+1)
dp[0]=(1-arr[0])
dp[1]=arr[0]
for i in range(1,n):
  dp[i+1]=dp[i]*arr[i]
  for j in range(1,i+1):
    dp[i+1-j]=dp[i-j]*arr[i]+dp[i+1-j]*(1-arr[i])
  dp[0]=dp[0]*(1-arr[i])
ans=0
for i in range(int(n/2)+1,n+1):
  ans+=dp[i]
print(ans)

Fixed submission:
n=int(input())
arr=list(map(float,input().split()))
dp=[1]*(n+1)
dp[0]=(1-arr[0])
dp[1]=arr[0]
for i in range(1,n):
  for j in range(i+2):
    if j==0:
      dp[i+1-j]=dp[i-j]*arr[i]
    elif j==i+1:
      dp[i+1-j]=dp[i+1-j]*(1-arr[i])
    else:
      dp[i+1-j]=dp[i-j]*arr[i]+dp[i+1-j]*(1-arr[i])
ans=0
for i in range(int(n/2)+1,n+1):
  ans+=dp[i]
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
arr=list(map(float,input().split()))
dp=[1]*(n+1)
dp[0]=(1-arr[0])
dp[1]=arr[0]
for i in range(1,n):
  for j in range(i+2):
    if j==0:
      dp[i+1-j]=dp[i-j]*arr[i]
    elif j==i+1:
      dp[i+1-j]=dp[i+1-j]*(1-arr[i])
    else:
      dp[i+1-j]=dp[i-j]*arr[i]+dp[i+1-j]*(1-arr[i])
ans=0
for i in range(int(n/2)+1,n+1):
  ans+=dp[i]
print(ans)

Fixed submission:
n=int(input())
arr=list(map(float,input().split()))
dp=[1]*(n+1)
dp[0]=(1-arr[0])
dp[1]=arr[0]
for i in range(1,n):
  for j in range(i+2):
    if j==0:
      dp[i+1-j]=dp[i-j]*arr[i]
    elif j==i+1:
      dp[i+1-j]=dp[i+1-j]*(1-arr[i])
    else:
      dp[i+1-j]=dp[i-j]*arr[i]+dp[i+1-j]*(1-arr[i])
ans=0
for i in range(int(n/2)+1,n+1):
  ans+=dp[i]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
arr=list(map(int,input().split()))
dp=[[0]*n for _ in range(n)]
for i in range(n):
  if n%2==0:
    dp[i][i]=-arr[i]
  else:
    dp[i][i]=arr[i]
for i in range(1,n):
  for j in range(n-i):
    if (n-i)%2==0:
      dp[j][j+i]=min(dp[j][j+i-1]-arr[j+i],dp[j+1][j+i]-arr[j])
    else:
      dp[j][j+i]=max(dp[j][j+i-1]+arr[j+i],dp[j+1][j+i]+arr[j])
print(dp[0][n-1])

Fixed submission:
n=int(input())
arr=list(map(int,input().split()))
dp=[[0]*n for _ in range(n)]
for i in range(n):
  if n%2==0:
    dp[i][i]=-arr[i]
  else:
    dp[i][i]=arr[i]
for i in range(1,n):
  for j in range(n-i):
    if (n-i)%2==0:
      dp[j][j+i]=min(dp[j][j+i-1]-arr[j+i],dp[j+1][j+i]-arr[j])
    else:
      dp[j][j+i]=max(dp[j][j+i-1]+arr[j+i],dp[j+1][j+i]+arr[j])
print(dp[0][n-1])
Buggy python submission (verdict: Runtime Error):
mod=10**9+7
def dfs(v):
  if checked[v]==1:
    return
  checked[v]=1
  dp[v][0]=1
  dp[v][1]=1
  for u in g[v]:
    if checked[u]==0:
      dfs(u)
      dp[v][0]*=dp[u][0]+dp[u][1]
      dp[v][0]%=mod
      dp[v][1]*=dp[u][0]
      dp[v][1]%=mod      

n=int(input())
g=[[] for _ in range(n+1)]
for _ in range(n-1):
  a,b=map(int,input().split())
  g[a].append(b)
  g[b].append(a)
dp=[[0,0] for _ in range(n+1)]
checked=[0]*(n+1)
dfs(1)
print((dp[1][0]+dp[1][1])%mod)

Fixed submission:
import sys
sys.setrecursionlimit(10**6)

mod=10**9+7
def dfs(v):
  if checked[v]==1:
    return
  checked[v]=1
  dp[v][0]=1
  dp[v][1]=1
  for u in g[v]:
    if checked[u]==0:
      dfs(u)
      dp[v][0]=(dp[v][0]*(dp[u][0]+dp[u][1]))%mod
      dp[v][1]=(dp[v][1]*dp[u][0])%mod

n=int(input())
g=[[] for _ in range(n+1)]
for _ in range(n-1):
  a,b=map(int,input().split())
  g[a].append(b)
  g[b].append(a)
dp=[[0,0] for _ in range(n+1)]
checked=[0]*(n+1)
dfs(1)
print((dp[1][0]+dp[1][1])%mod)

Buggy python submission (verdict: Runtime Error):
mod=10**9+7
def dfs(v):
  if checked[v]==1:
    return
  checked[v]=1
  dp[v][0]=1
  dp[v][1]=1
  for u in g[v]:
    if checked[u]==0:
      dfs(u)
      dp[v][0]*=dp[u][0]+dp[u][1]
      dp[v][0]%=mod
      dp[v][1]*=dp[u][0]
      dp[v][1]%=mod      

n=int(input())
g=[[] for _ in range(n+1)]
for _ in range(n-1):
  a,b=map(int,input().split())
  g[a].append(b)
  g[b].append(a)
dp=[[0,0] for _ in range(n+1)]
checked=[0]*(n+1)
dfs(1)
print(dp[1][0]+dp[1][1])

Fixed submission:
import sys
sys.setrecursionlimit(10**6)

mod=10**9+7
def dfs(v):
  if checked[v]==1:
    return
  checked[v]=1
  dp[v][0]=1
  dp[v][1]=1
  for u in g[v]:
    if checked[u]==0:
      dfs(u)
      dp[v][0]=(dp[v][0]*(dp[u][0]+dp[u][1]))%mod
      dp[v][1]=(dp[v][1]*dp[u][0])%mod

n=int(input())
g=[[] for _ in range(n+1)]
for _ in range(n-1):
  a,b=map(int,input().split())
  g[a].append(b)
  g[b].append(a)
dp=[[0,0] for _ in range(n+1)]
checked=[0]*(n+1)
dfs(1)
print((dp[1][0]+dp[1][1])%mod)
Buggy python submission (verdict: Time Limit Exceeded):
class SegmentTreeMax():
  def __init__(self,n,init):
    self.offset=2**((n-1).bit_length())
    self.tree=[init]*(2*self.offset)
    self.init=init
  def update(self,pos,val):
    pos+=self.offset
    self.tree[pos]=val
    while pos>1:
      pos=pos//2
      self.tree[pos]=max(self.tree[2*pos],self.tree[2*pos+1])
  def query(self,l,r):
    l+=self.offset
    r+=self.offset
    ret=self.init
    while l<=r:
      ret=max(ret,self.tree[r])
      r=(r-1)//2
      ret=max(ret,self.tree[l])
      l=(l+1)//2
    return ret

n=int(input())
h=list(map(int,input().split()))
a=list(map(int,input().split()))
st=SegmentTreeMax(max(h)+1,0)
for i in range(n):
  val=a[i]+st.query(0,h[i]-1)
  st.update(h[i],val)
print(max(st.tree))

Fixed submission:
class SegmentTreeMax():
  def __init__(self,n,init):
    self.offset=2**((n-1).bit_length())
    self.tree=[init]*(2*self.offset)
    self.init=init
  def update(self,pos,val):
    pos+=self.offset
    self.tree[pos]=val
    while pos>1:
      pos=pos//2
      self.tree[pos]=max(self.tree[2*pos],self.tree[2*pos+1])
  def query(self,l,r):
    l+=self.offset
    r+=self.offset
    ret=self.init
    while l<=r:
      ret=max(ret,self.tree[r])
      r=(r-1)//2
      ret=max(ret,self.tree[l])
      l=(l+1)//2
    return ret

n=int(input())
h=list(map(int,input().split()))
a=list(map(int,input().split()))
st=SegmentTreeMax(max(h)+1,0)
for i in range(n):
  val=a[i]+st.query(0,h[i]-1)
  st.update(h[i],val)
print(max(st.tree))