Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
n,q=map(int,input().split())
s=input()
td=[input().split()for _ in range(q)]
def check(i,x):
  for t,d in td:
    if s[i]==t:
      if d=="L":i-=1
      else:i+=1
    if i==x:return True
  return False
ok=-1
ng=n
while ok+1!=ng:
  mid=(ok+ng)//2
  if check(mid,-1):ok=mid
  else:ng=mid
ans=ng
ok=-1
ng=n
while ok+1!=ng:
  mid=(ok+ng)//2
  if check(mid,n):ng=mid
  else:ok=mid
ans+=(n-ng)
print(max(0,n-ans))

Fixed submission:
n,q=map(int,input().split())
s=input()
td=[input().split()for _ in range(q)]
def check(i,x):
  for t,d in td:
    if s[i]==t:
      if d=="L":i-=1
      else:i+=1
    if i==x:return True
    if i==-1 or i==n:return False
  return False
ok=-1
ng=n
while ok+1!=ng:
  mid=(ok+ng)//2
  if check(mid,-1):ok=mid
  else:ng=mid
ans=ng
ok=-1
ng=n
while ok+1!=ng:
  mid=(ok+ng)//2
  if check(mid,n):ng=mid
  else:ok=mid
ans+=(n-ng)
print(max(0,n-ans))

Buggy python submission (verdict: Time Limit Exceeded):
n,q=map(int,input().split());s=input();m=[[]];b=[1]*n
for i in range(n):
  if s[i] in m[0]:m[m[0].index(s[i])+1].append(i)
  else:
    m[0].append(s[i])
    m.append([i])
for i in range(q):
  t,d=input().split()
  if t in m[0]:
    w=m[0].index(t)+1
    if d=="L":
      for j in m[w]:
        if 0<j:b[j-1]+=b[j]
        b[j]=0
    else:
      for j in m[w][::-1]:
        if j<n-1:b[j+1]+=b[j]
        b[j]=0
print(sum(b))

Fixed submission:
n,q=map(int,input().split())
s=input()
td=[input().split()for _ in range(q)]
def check(i,x):
  for t,d in td:
    if s[i]==t:
      if d=="L":i-=1
      else:i+=1
    if i==x:return True
    if i==-1 or i==n:return False
  return False
ok=-1
ng=n
while ok+1!=ng:
  mid=(ok+ng)//2
  if check(mid,-1):ok=mid
  else:ng=mid
ans=ng
ok=-1
ng=n
while ok+1!=ng:
  mid=(ok+ng)//2
  if check(mid,n):ng=mid
  else:ok=mid
ans+=(n-ng)
print(max(0,n-ans))
Buggy python submission (verdict: Runtime Error):
s,a,x=input(),[],["A","C","G","T"]
b=""
for i in range(len(s)):
  if s[i] in x:b+=s[i]
  else:
    a.append(b)
    b=""
a.sort()
print(len(a[-1]))

Fixed submission:
s,x=input(),["A","C","G","T"]
a,b,c="",0,0
for i in range(len(s)):
  if s[i] in x:
    a+=s[i]
    c+=1
  else:
    a=""
    c=0
  if b<c:b=c
print(b)
Buggy python submission (verdict: Time Limit Exceeded):
n,q=map(int,input().split())
s=input()
count=[0]
for i in range(n-1):count.append(s[i:i+2]=="AC")
for i in range(q):
  a,b=map(int,input().split())
  print(sum(count[a:b]))

Fixed submission:
n,q=map(int,input().split())
s=input()
count=[0]
for i in range(n-1):count.append(count[i]+(s[i:i+2]=="AC"))
for i in range(q):
  a,b=map(int,input().split())
  print(count[b-1]-count[a-1])

Buggy python submission (verdict: Time Limit Exceeded):
n,q=map(int,input().split())
s=input()
count=[]
for i in range(n):
  if s[i:i+2]=="AC":count.append(1)
  else:count.append(0)
for i in range(q):
  a,b=map(int,input().split())
  print(count[a-1:b-1].count(1))

Fixed submission:
n,q=map(int,input().split())
s=input()
count=[0]
for i in range(n-1):count.append(count[i]+(s[i:i+2]=="AC"))
for i in range(q):
  a,b=map(int,input().split())
  print(count[b-1]-count[a-1])

Buggy python submission (verdict: Time Limit Exceeded):
def count_AC(s):
  ans=0
  for i in range(len(s)):
    if s[i:i+2]=="AC":ans+=1
  return ans
n,q=map(int,input().split())
s=input()
for i in range(q):
  a,b=map(int,input().split())
  print(count_AC(s[a-1:b]))

Fixed submission:
n,q=map(int,input().split())
s=input()
count=[0]
for i in range(n-1):count.append(count[i]+(s[i:i+2]=="AC"))
for i in range(q):
  a,b=map(int,input().split())
  print(count[b-1]-count[a-1])
Buggy python submission (verdict: Runtime Error):
n,a,b=int(input()),[],[]
for i in range(1,n+1):
  for j in range(i,n+1):
    if i!=j and i+j!=n:
      a.append(i)
      b.append(j)
print(len(a))
for i,j in a,b:print(i,j)

Fixed submission:
n,a,b=int(input()),[],[]
m=n+(n%2==0)
for i in range(1,n):
  for j in range(i+1,n+1):
    if i+j!=m:a.append(i);b.append(j)
l=len(a)
print(l)
for i in range(l):print(a[i],b[i])
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=input()
ans=0
def nanka(m,c):
  global a,n,ans
  b=c
  for i in range(n-m):
    if not a[i+m] in b:
      ans+=1
      b.append(a[i+m])
      if n>i+m+1:nanka(m+i+1,b)
      del b[len(b)-1]
nanka(0,[])
print(ans)

Fixed submission:
from collections import Counter
n,s=int(input()),input();c=[s[i]for i in range(n)];a=Counter(c);ans=1
for i in a:ans*=a[i]+1
print((ans-1)%(10**9+7))
Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split());a,b=[],[]
for i in range(n):
  aa,bb=map(int,input().split())
  a.append(aa);b.append(bb)
#---c.sorted(a)---
c=a[:]
def swap(ab,ba,X):
  abc=X[ab]
  X[ab]=X[ba]
  X[ba]=abc
h=n
while 1:
  hh=c[:]
  if h>1:h=round(h//1.3)
  for i in range(n-h):
    if c[i]>c[i+h]:swap(i,i+h,c)
  if hh==c and h==1:break
#---------
s,ans=0,0
for i in c:
  j=a.index(i)
  k=min(b[j],m-s)
  s+=k
  ans+=a[j]*k
  a[j]=-1
  if m==s:break
print(ans)

Fixed submission:
n,m=map(int,input().split());d,ans=[],0
for i in range(n):d.append(list(map(int,input().split())))
d.sort()
for i in range(n):
  if d[i][1]<=m:
    ans+=d[i][0]*d[i][1]
    m-=d[i][1]
  else:
    ans+=d[i][0]*m
    m=0
  if m<=0:break
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split());a,b=[],[]
for i in range(n):
  aa,bb=map(int,input().split())
  a.append(aa);b.append(bb)
c=sorted(a)
s,ans=0,0
for i in c:
  j=a.index(i)
  k=min(b[j],m-s)
  s+=k
  ans+=a[j]*k
  a[j]=-1
  if m==s:break
print(ans)

Fixed submission:
n,m=map(int,input().split());d,ans=[],0
for i in range(n):d.append(list(map(int,input().split())))
d.sort()
for i in range(n):
  if d[i][1]<=m:
    ans+=d[i][0]*d[i][1]
    m-=d[i][1]
  else:
    ans+=d[i][0]*m
    m=0
  if m<=0:break
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N,M=map(int,input().split())
A=[]
B=[]
money=0
maxa=0
maxb=0
for i in range(N):
  x,y=map(int,input().split())
  if maxa<x:
    maxa=x
    maxb=i
  A.append(x)
  B.append(y)
for i in range(N):
  lowest=maxb
  low=maxa
  for j in range(N):
    if (low>A[j] and A[j]!=0):
      lowest=j
      low=A[j]
  if B[lowest]>M:
    money+=M*A[lowest]
    M-=B[lowest]
    break
  else:
    money+=B[lowest]*A[lowest]
    M-=B[lowest]
  A[lowest]=0
print(money)

Fixed submission:
n,m=map(int,input().split());d,ans=[],0
for i in range(n):d.append(list(map(int,input().split())))
d.sort()
for i in range(n):
  if d[i][1]<=m:
    ans+=d[i][0]*d[i][1]
    m-=d[i][1]
  else:
    ans+=d[i][0]*m
    m=0
  if m<=0:break
print(ans)
Buggy python submission (verdict: Runtime Error):
if 7/0>1:print(1)

Fixed submission:
A,B,K=map(int,input().split())
for i in range(100):
  if A%(100-i)==0 and B%(100-i)==0:
    K-=1
    if K==0:
      print(100-i)
      break
Buggy python submission (verdict: Runtime Error):
n=int(input())
ans=0
b=380000
for i in range(n):
  x,u=input().split()
  if u=="JPY":
    ans+=int(x)
  else:
    ans+=int(x)*b
print(ans)

Fixed submission:
n,ans=int(input()),0
for i in range(n):
  a,b=input().split();a=float(a)
  if b=="JPY":ans+=a
  else:ans+=a*380000
print(ans)

Buggy python submission (verdict: Runtime Error):
n,ans=int(input()),0
for i in range(n):
  a,b=input().split();a=int(a)
  if b=="JPY":ans+=a
  else:ans+=a*380000
print(ans)

Fixed submission:
n,ans=int(input()),0
for i in range(n):
  a,b=input().split();a=float(a)
  if b=="JPY":ans+=a
  else:ans+=a*380000
print(ans)

Buggy python submission (verdict: Runtime Error):
n,ans=int(input()),0
for i in range(n):
  a,b=map(int,input().split())
  if b=="JPY":ans+=a
  else:ans+=a*380000
print(ans)

Fixed submission:
n,ans=int(input()),0
for i in range(n):
  a,b=input().split();a=float(a)
  if b=="JPY":ans+=a
  else:ans+=a*380000
print(ans)
Buggy python submission (verdict: Runtime Error):
n,ans,l=int(input()),"Yes",list(map(int,input()))
for i in l:
  if sum(l)<i*2:ans="No"
print(ans)

Fixed submission:
n,ans,l=int(input()),"Yes",list(map(int,input().split()))
for i in l:
  if sum(l)<=i*2:ans="No"
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
t=[[]for _ in range(n)]
ne=(n-1)*n//2
ne_s=set()
e=[]
for i in range(n-1+m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  e.append([a,b])
  if b not in ne_s:
    ne_s.add(b)
    ne-=b
  t[a].append(b)
d=[0]*n
Q=[ne]
di=1
while Q:
  P=[]
  for i in Q:
    for j in t[i]:
      d[j]=max(d[j],di)
      P.append(j)
  di+=1
  Q=P
ans=[0]*n
for a,b in e:
  if d[a]+1!=d[b]:continue
  ans[b]=a+1
print(*ans)

Fixed submission:
n,m=map(int,input().split())
edge=[[]for _ in range(n)]
for _ in range(n+m-1):
  a,b=map(int,input().split())
  a-=1
  b-=1
  edge[a].append(b)
from collections import deque
def find_loop(n,e,flag):
  x=[0]*n
  d=deque()
  t=[]
  c=0
  for i in range(n):
    for j in e[i]:x[j]+=1
  for i in range(n):
    if x[i]==0:
      d.append(i)
      t.append(i)
      c+=1
  while d:
    i=d.popleft()
    for j in e[i]:
      x[j]-=1
      if x[j]==0:
        d.append(j)
        t.append(j)
        c+=1
  if flag==0:return c==n
  else:return t
top=find_loop(n,edge,1)
d=[0]*n
for i in range(n):
  for j in edge[top[i]]:d[j]=d[top[i]]+1
ans=[-1]*n
ans[d.index(0)]=0
for i in range(n):
  for j in edge[i]:
    if d[i]+1==d[j]:ans[j]=i+1
print(*ans)

Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
t=[[]for _ in range(n)]
ne=(n-1)*n//2
ne_s=set()
e=[]
for i in range(n-1+m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  e.append([a,b])
  if b not in ne_s:
    ne_s.add(b)
    ne-=b
  t[a].append(b)
d=[0]*n
Q=[ne]
di=1
while Q:
  P=[]
  for i in Q:
    for j in t[i]:
      d[j]=max(d[j],di)
      P.append(j)
  di+=1
  Q=P
ans=[0]*n
for a,b in e:
  if d[a]+1!=d[b]:continue
  ans[b]=a+1
print(*ans)

Fixed submission:
n,m=map(int,input().split())
edge=[[]for _ in range(n)]
for _ in range(n+m-1):
  a,b=map(int,input().split())
  a-=1
  b-=1
  edge[a].append(b)
from collections import deque
def find_loop(n,e,flag):
  x=[0]*n
  d=deque()
  t=[]
  c=0
  for i in range(n):
    for j in e[i]:x[j]+=1
  for i in range(n):
    if x[i]==0:
      d.append(i)
      t.append(i)
      c+=1
  while d:
    i=d.popleft()
    for j in e[i]:
      x[j]-=1
      if x[j]==0:
        d.append(j)
        t.append(j)
        c+=1
  if flag==0:return c==n
  else:return t
top=find_loop(n,edge,1)
d=[0]*n
for i in range(n):
  for j in edge[top[i]]:d[j]=d[top[i]]+1
ans=[-1]*n
ans[d.index(0)]=0
for i in range(n):
  for j in edge[i]:
    if d[i]+1==d[j]:ans[j]=i+1
print(*ans)
Buggy python submission (verdict: Runtime Error):
n=int(input())
h=list(map(int,input().split()))
ans=0
while h!=[0]*n:
  b=(h[0]!=0)+0
  for i in range(n):
    if b==1 and h[i]==0:ans+=1;b=0
    if h[i]!=0:h-=1;b=1
  if b==1:ans+=1
print(ans)

Fixed submission:
n=int(input())
h=list(map(int,input().split()))
ans=0
while h!=[0]*n:
  b=(h[0]!=0)+0
  for i in range(n):
    if b==1 and h[i]==0:ans+=1;b=0
    if h[i]!=0:h[i]-=1;b=1
  if b==1:ans+=1
print(ans)
Buggy python submission (verdict: Runtime Error):
n,k=map(int,input().split())
td=[list(map(int,input().split()))[::-1]for _ in range(n)]
td.sort(reverse=1)
s=set()
ss=set()
a=[]
b=[]
c=[]
for i in range(n):
  if i<k:
    d,t=td[i]
    if t in s:
      b.append(d)
    else:
      a.append(d)
      s.add(t)
      ss.add(t)
  else:
    d,t=td[i]
    if t not in ss:
      c.append(d)
      ss.add(t)
c=c[::-1]
ls=len(s)
su=sum(a)+sum(b)
ans=ls*ls+su
for i in range(len(ss)-len(s)):
  ls+=1
  su-=b.pop()
  su+=c.pop()
  ans=max(ans,ls*ls+su)
print(ans)


Fixed submission:
n,k=map(int,input().split())
a=[]
for _ in range(n):a.append(tuple(list(map(int,input().split()))[::-1]))
a.sort(reverse=1)
x,y=[],[]
s=set()
for i in range(k):
  d,t= a[i]
  if t in s:
    x.append(d)
  else:
    y.append(d)
    s.add(t)
xx,yy,v=sum(x),sum(y),len(y)
ans=xx+yy+v**2
for i in range(k,n):
    if len(x)==0:break
    d,t=a[i]
    if t in s:continue
    s.add(t)
    xx-=x.pop()
    yy+=d
    v+=1
    ans=max(ans,xx+yy+v**2)
print(ans)
Buggy python submission (verdict: Runtime Error):
h,w=map(int,input().split());b=[[0]*(w+1)]
for i in range(h):
  b.append([0])
  for j in input():
    if j==".":b[-1].append(1)
    else:b[-1].append(2)
  b[-1].append(0)
b.append([0]*(w+1));d=[[0,1],[0,-1],[1,0],[-1,0]];a=0
def s(i,j):
  global B;B[b[i][j]-1]+=1;v=b[i][j];b[i][j]=0
  for k in d:
    if v^3!=b[i+k[0]][j+k[1]]:continue
    s(i+k[0],j+k[1])
for i in range(1,h+1):
  for j in range(1,w+1):B=[0,0];s(i,j);a+=B[0]*B[1]
print(a)

Fixed submission:
import sys;sys.setrecursionlimit(10**9)
h,w=map(int,input().split())
b=[[0]*(w+1)]
for i in range(h):
  b.append([0])
  for j in input():
    if j==".":b[-1].append(1)
    else:b[-1].append(2)
  b[-1].append(0)
b.append([0]*(w+1))
d=[[0,1],[0,-1],[1,0],[-1,0]]
a=0
def bfs(i,j):
  global br,wh
  if b[i][j]==0:return
  if b[i][j]==1:wh+=1
  elif b[i][j]==2:br+=1
  v=b[i][j]
  b[i][j]=0
  for k in d:
    if v^3!=b[i+k[0]][j+k[1]]:continue
    bfs(i+k[0],j+k[1])
for i in range(1,h+1):
  for j in range(1,w+1):
    br=wh=0
    bfs(i,j)
    a+=br*wh
print(a)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=sys.stdin.readline
n,w=map(int,input().split())
dp=[[0]*w for _ in range(n)]
for i in range(n):
  a,b=map(int,input().split())
  for j in range(w):
    if i==0:
      if j>a-2:dp[i][j]=b
    elif j>a-2:
      if j==a-1:dp[i][j]=max(b,dp[i-1][j])
      else:dp[i][j]=max(dp[i-1][j-a]+b,dp[i-1][j])
    else:dp[i][j]=dp[i-1][j]
print(dp[n-1][w-1])

Fixed submission:
n,w=map(int,input().split())
dp=[[0]*w for _ in range(n)]
for i in range(n):
  a,b=map(int,input().split())
  for j in range(w):
    if i==0:
      if j>a-2:dp[i][j]=b
    elif j>a-2:
      if j==a-1:dp[i][j]=max(b,dp[i-1][j])
      else:dp[i][j]=max(dp[i-1][j-a]+b,dp[i-1][j])
    else:dp[i][j]=dp[i-1][j]
print(dp[-1][-1])

Buggy python submission (verdict: Runtime Error):
n,w=map(int,input().split())
dp=[[0]*w for _ in range(n)]
for i in range(n):
  a,b=map(int,input().split())
  for j in range(w):
    if i==0:
      if j>a-2:dp[i][j]=b
    elif j>a-2:
      if j==a-1:dp[i][j]=max(b,dp[i-1],[j])
      else:dp[i][j]=max(dp[i-1][j-a]+b,dp[i-1][j])
    else:dp[i][j]=dp[i-1][j]
print(dp[-1][-1])

Fixed submission:
n,w=map(int,input().split())
dp=[[0]*w for _ in range(n)]
for i in range(n):
  a,b=map(int,input().split())
  for j in range(w):
    if i==0:
      if j>a-2:dp[i][j]=b
    elif j>a-2:
      if j==a-1:dp[i][j]=max(b,dp[i-1][j])
      else:dp[i][j]=max(dp[i-1][j-a]+b,dp[i-1][j])
    else:dp[i][j]=dp[i-1][j]
print(dp[-1][-1])
Buggy python submission (verdict: Time Limit Exceeded):
n,w=map(int,input().split())
u,m=[list(map(int,input().split()))for _ in range(n)],0
for i in u:m+=i[1]
dp=[[0]+[10000001]*m]+[[0]*(m+1)for _ in range(n)]
h=0
for i in range(1,n+1):
  a,b=map(int,u[i-1])
  for j in range(1,m+1):
    if j>=b:dp[i][j]=min(dp[i-1][j],dp[i-1][j-b]+a)
    else:dp[i][j]=dp[i-1][j]
a=0
for i in range(m+1):
  if dp[-1][i]<=w:a=max(a,i)
print(a)

Fixed submission:
n,w=map(int,input().split())
dp=[[100000000001]*100001for _ in range(n+1)]
dp[0][0]=0
for i in range(1,n+1):
  a,b=map(int,input().split())
  for j in range(100001):
    if j>=b:dp[i][j]=min(dp[i-1][j],dp[i-1][j-b]+a)
    else:dp[i][j]=dp[i-1][j]
i=10**5
while dp[n][i]>w:i-=1
print(i)
Buggy python submission (verdict: Time Limit Exceeded):
s=input()
t=input()
n=len(s)
m=len(t)
dp=[[0]*(m+1) for _ in range(n+1)]
for i in range(1,n+1):
  for j in range(1,m+1):
    if s[i-1]==t[j-1]:
      dp[i][j]=dp[i-1][j-1]+1
    else:
      dp[i][j]=max(dp[i-1][j],dp[i][j-1])
x=dp[-1][-1]
i=n
j=m
ans=""
while x!=0:
  if dp[i][j]==dp[i][j-1]:
    j-=1
  elif dp[i][j]==dp[i-1][j]:
    i-=1
  else:
    ans+=s[i-1]
    i-=1
    j-=1
    x-=1
print(ans[::-1])


Fixed submission:
s,t=input(),input()
ls,lt=len(s),len(t)
dp=[[0]*(lt+1) for _ in range(ls+1)]
for i in range(1,ls+1):
  for j in range(1,lt+1):
    if s[i-1]==t[j-1]:dp[i][j]=dp[i-1][j-1]+1
    else:dp[i][j]=max(dp[i-1][j],dp[i][j-1])
l=dp[-1][-1]
i,j,a=ls,lt,""
while l!=0:
  if dp[i][j]==dp[i][j-1]:j-=1
  elif dp[i][j]==dp[i-1][j]:i-=1
  else:a=s[i-1]+a;i-=1;j-=1;l-=1
print(a)
Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split());a=list(map(int,input().split()));dp=[0]*(k+1)
for i in range(1,k+1):
  for j in a:dp[i]=max((i-j>=0)*(dp[i-j]==0),dp[i])
print(["Second","First"][dp[-1]])

Fixed submission:
n,k=map(int,input().split());a=list(map(int,input().split()));dp=[0]*(k+1)
for i in range(1,k+1):
  for j in a:dp[i]=max((i-j>=0)*(dp[i-j]==0),dp[i])
print(["Second","First"][dp[-1]])
Buggy python submission (verdict: Time Limit Exceeded):
n,a=int(input()),list(map(int,input().split()));dp=[[None]*n for _ in range(n)]
for i in range(n):dp[i][i]=a[i]
for j in range(1,n):
  for i in range(n-j):dp[i][j+i]=max(a[i]-dp[i+1][j+i],a[j+i]-dp[i][j+i-1])
print(dp[0][-1])

Fixed submission:
n,a=int(input()),list(map(int,input().split()));dp=[[None]*n for _ in range(n)]
for i in range(n):dp[i][i]=a[i]
for j in range(1,n):
  for i in range(n-j):dp[i][j+i]=max(a[i]-dp[i+1][j+i],a[j+i]-dp[i][j+i-1])
print(dp[0][-1])
Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
a=list(map(int,input().split()))
dp=[0]*(k+1)
dp[0]=1
mod=10**9+7
for i in range(n):
  for j in range(k,0,-1):
    if j>a[i]:dp[j]-=dp[j-a[i]-1]
  for j in range(k):dp[j+1]=(dp[j+1]+dp[j])%mod
print(dp[k])

Fixed submission:
n,k=map(int,input().split())
a=list(map(int,input().split()))
dp=[0]*(k+1)
dp[0]=1
mod=10**9+7
for i in range(n):
  for j in range(k,0,-1):
    if j>a[i]:dp[j]-=dp[j-a[i]-1]
  for j in range(k):dp[j+1]=(dp[j+1]+dp[j])%mod
print(dp[k])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(1000000000)
n=int(input())
a=list(map(int,input().split()))
b=[0]
for i in a:b.append(i+b[-1])
dp=[n*[10**15]for _ in range(n)]
def dfs(l,r):
  if dp[l][r]!=10**15:return dp[l][r]
  if l==r:return 0
  dp[l][r]=b[r+1]-b[l]+min(dfs(l,i)+dfs(i+1,r)for i in range(l,r))
  return dp[l][r]
print(dfs(0,n-1))

Fixed submission:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(1000000000)
n=int(input())
a=list(map(int,input().split()))
b=[0]
for i in a:b.append(i+b[-1])
dp=[n*[10**15]for _ in range(n)]
def dfs(l,r):
  if dp[l][r]!=10**15:return dp[l][r]
  if l==r:return 0
  dp[l][r]=b[r+1]-b[l]+min(dfs(l,i)+dfs(i+1,r)for i in range(l,r))
  return dp[l][r]
print(dfs(0,n-1))
Buggy python submission (verdict: Time Limit Exceeded):
n,p=map(int,input().split())
i,a=2,1
while pow(i,n)<=p:
  while p%pow(i,n)==0:a*=i;p//=pow(i,n)
  i+=1
print(a)

Fixed submission:
n,p=map(int,input().split())
for i in range(round(p**(1/n)),0,-1):
  if p%(i**n)==0:print(i);exit()

Buggy python submission (verdict: Time Limit Exceeded):
n,p=map(int,input().split())
i,a=2,1
while i**n<=p:
  while p%(i**n)==0:a*=i;p//=(i**n)
  i+=1
print(a)

Fixed submission:
n,p=map(int,input().split())
for i in range(round(p**(1/n)),0,-1):
  if p%(i**n)==0:print(i);exit()
Buggy python submission (verdict: Runtime Error):
a,b,s=0,input(),0
for i in range(len(s)):a+=i*(s[i]=="W");b+=1
print(a-((b*(b-1))//2))

Fixed submission:
a,s,b=0,input(),0
for i in range(len(s)):a+=i*(s[i]=="W");b+=(s[i]=="W")
print(a-((b*(b-1))//2))
Buggy python submission (verdict: Runtime Error):
s=input();min=1000
for i in range(len(s)-2):min=min(abs(int(s[i]+s[i+1]+s[i+2])-753),min)
print(min)

Fixed submission:
s=input();minn=1000
for i in range(len(s)-2):minn=min(abs(int(s[i:i+3])-753),minn)
print(minn)
Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
a=list(map(int,input().split()))
b=[]
for i in range(n):
  x=0
  for j in range(i,n):
    x+=a[j]
    b.append(x)
ans=0
l=len(b)
for i in range(40,-1,-1):
  x=0
  s=2**i
  for j in range(l):
    if b[j]&(ans+s)==ans+s:x+=1
  if x>=k:ans+=s
print(ans)

Fixed submission:
n,k=map(int,input().split())
a=list(map(int,input().split()))
b=[]
for i in range(n):
  x=0
  for j in range(i,n):
    x+=a[j]
    b.append(x)
ans=0
l=len(b)
for i in range(40,-1,-1):
  x=0
  s=2**i
  for j in range(l):
    if b[j]&(ans+s)==ans+s:x+=1
  if x>=k:ans+=s
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
a=list(map(int,input().split()))
b=[]
for i in range(n):
  x=0
  for j in range(i,n):
    x+=a[j]
    b.append(x)
ans=0
l=len(b)
for i in range(40,0,-1):
  x=0
  s=2**i
  for j in range(l):
    if b[j]&(ans+s)==ans+s:x+=1
  if x>=k:ans+=s
print(ans)

Fixed submission:
n,k=map(int,input().split())
a=list(map(int,input().split()))
b=[]
for i in range(n):
  x=0
  for j in range(i,n):
    x+=a[j]
    b.append(x)
ans=0
l=len(b)
for i in range(40,-1,-1):
  x=0
  s=2**i
  for j in range(l):
    if b[j]&(ans+s)==ans+s:x+=1
  if x>=k:ans+=s
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
a=list(map(int,input().split()))
b=[]
for i in range(n):
  x=0
  for j in range(i,n):
    x+=a[j]
    b.append(x)
ans=0
l=len(b)
for i in range(40,-1,-1):
  x=0
  s=2**i
  for j in range(l):
    if b[j]&(ans+s)==ans+s:x+=1
  if x>=k:ans+=s
print(ans)

Fixed submission:
n,k=map(int,input().split())
a=list(map(int,input().split()))
b=[]
for i in range(n):
  x=0
  for j in range(i,n):
    x+=a[j]
    b.append(x)
ans=0
l=len(b)
for i in range(40,-1,-1):
  x=0
  s=2**i
  for j in range(l):
    if b[j]&(ans+s)==ans+s:x+=1
  if x>=k:ans+=s
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def pypri(p,y):print(str(p).zfill(6)+str(y).zfill(6))
n,m=map(int,input().split())
a=[[]for _ in range(n)]
b=[]
for i in range(m):
  p,y=map(int,input().split())
  b.append(p-1)
  a[p-1].append([y,len(a[p-1])+1])
for i in range(n):
  a[i].sort()
  for j in range(len(a[i])):
    a[i][j]=[a[i][j][1],j]
    a[i].sort()
for i in b:
  pypri(i+1,a[i][0][1]+1)
  del a[i][0]


Fixed submission:
n,m = map(int,input().split())
py = []
for i in range(m):
    py.append(list(map(int,input().split())))
    py[i].append(i)
py.sort(key=lambda x:x[1])
py.sort(key=lambda x:x[0])
x = py[0][0]
j=0
for i in range(m):
    if x != py[i][0]:
        j = 1
        x = py[i][0]
    else:
        j+=1
    s = str(py[i][0]).zfill(6) + str(j).zfill(6)
    py[i].append(s)
py.sort(key=lambda x:x[2])
for i in range(m):
    print(py[i][3])

Buggy python submission (verdict: Time Limit Exceeded):
def pypri(p,y):print(str(p).zfill(6)+str(y).zfill(6))
n,m=map(int,input().split())
a=[[]for _ in range(n)]
b=[]
for i in range(m):
  p,y=map(int,input().split())
  b.append(p-1)
  a[p-1].append([y,len(a[p-1])+1])
for i in range(n):
  a[i].sort()
  for j in range(len(a[i])):
    a[i][j]=[a[i][j][1],j]
    a[i].sort()
for i in b:
  pypri(i+1,a[i][0][1]+1)
  del a[i][0]

Fixed submission:
n,m = map(int,input().split())
py = []
for i in range(m):
    py.append(list(map(int,input().split())))
    py[i].append(i)
py.sort(key=lambda x:x[1])
py.sort(key=lambda x:x[0])
x = py[0][0]
j=0
for i in range(m):
    if x != py[i][0]:
        j = 1
        x = py[i][0]
    else:
        j+=1
    s = str(py[i][0]).zfill(6) + str(j).zfill(6)
    py[i].append(s)
py.sort(key=lambda x:x[2])
for i in range(m):
    print(py[i][3])

Buggy python submission (verdict: Runtime Error):
def pypri(p,y):print(str(p).zfill(6)+str(y).zfill(6))
n,m=map(int,input().split())
a=[[]for _ in range(n)]
b=[]
for i in range(m):
  p,y=map(int,input.split())
  b.append(p-1)
  a[p-1].append([y,len(a[p-1])+1])
for i in range(n):
  a[i].sort()
  for j in range(len(a[i])):
    a[i][j]=[a[i][j][1],j]
    a.sort()
for i in b:
  pypri(i+1,a[i][0][1]+1)
  del a[i][0]

Fixed submission:
n,m = map(int,input().split())
py = []
for i in range(m):
    py.append(list(map(int,input().split())))
    py[i].append(i)
py.sort(key=lambda x:x[1])
py.sort(key=lambda x:x[0])
x = py[0][0]
j=0
for i in range(m):
    if x != py[i][0]:
        j = 1
        x = py[i][0]
    else:
        j+=1
    s = str(py[i][0]).zfill(6) + str(j).zfill(6)
    py[i].append(s)
py.sort(key=lambda x:x[2])
for i in range(m):
    print(py[i][3])
Buggy python submission (verdict: Runtime Error):
s=input()
if len(s)==2;print(s)
else:print(s[::-1])

Fixed submission:
s=input()
if len(s)==2:print(s)
else:print(s[::-1])