Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import sys
input=sys.stdin.readline


def solve():
    N = int(input())
    d = {i:-1 for i in range(1, N+1)}
    *l, = map(int, input().split())

    MOD = 10**9+7
    n = N+1
    fac = [1]*(n+1)
    rev = [1]*(n+1)
    
    for i in range(1,n+1):
    fac[i] = i*fac[i-1]%MOD
    rev[i] = pow(fac[i], MOD-2, MOD)
    
    comb = lambda a,b:(fac[a]*rev[a-b]*rev[b])%MOD if a>=b else 0

    for i, j in enumerate(l):
        if d[j] != -1:
            break
        d[j] = i

    v = d[j]+N-i
    for i in range(1, N+2):
        print((comb(N+1, i)-comb(v, i-1))%MOD)


if __name__ == "__main__":
    solve()


Fixed submission:
N = int(input())
d = {i:-1 for i in range(1, N+1)}
*l, = map(int, input().split())

MOD = 10**9+7
n = N+1
fac = [1]*(n+1)
rev = [1]*(n+1)
 
for i in range(1,n+1):
  fac[i] = i*fac[i-1]%MOD
  rev[i] = pow(fac[i], MOD-2, MOD)
 
comb = lambda a,b:(fac[a]*rev[a-b]*rev[b])%MOD if a>=b else 0

for i, j in enumerate(l):
    if d[j] != -1:
        break
    d[j] = i

a = d[j]
b = N-i
for i in range(1, N+2):
    print((comb(N+1, i)-comb(a+b, i-1))%MOD)

Buggy python submission (verdict: Runtime Error):
N = int(input())
d = {i:-1 for i in range(1, N+1)}
*l, = map(int, input().split())

MOD = 10**9+7
n = N+1
fac = [1]*(n+1)
rev = [1]*(n+1)
 
for i in range(1,n+1):
  fac[i] = i*fac[i-1]%MOD
  rev[i] = pow(fac[i], MOD-2, MOD)
 
comb = lambda a,b:(fac[a]*rev[a-b]*rev[b])%MOD if a>=b else 0

for i, j in enumerate(l):
    if d[j] != -1:
        break
    d[j] = i

for i in range(1, N+2):
    print((comb(N+1, i)-comb(d[j]+N-1, i-1))%MOD)


Fixed submission:
N = int(input())
d = {i:-1 for i in range(1, N+1)}
*l, = map(int, input().split())

MOD = 10**9+7
n = N+1
fac = [1]*(n+1)
rev = [1]*(n+1)
 
for i in range(1,n+1):
  fac[i] = i*fac[i-1]%MOD
  rev[i] = pow(fac[i], MOD-2, MOD)
 
comb = lambda a,b:(fac[a]*rev[a-b]*rev[b])%MOD if a>=b else 0

for i, j in enumerate(l):
    if d[j] != -1:
        break
    d[j] = i

a = d[j]
b = N-i
for i in range(1, N+2):
    print((comb(N+1, i)-comb(a+b, i-1))%MOD)

Buggy python submission (verdict: Runtime Error):
N = int(input())
d = {i:-1 for i in range(1, N+1)}
*l, = map(int, input().split())

MOD = 10**9+7
n = N+1
fac = [1]*(n+1)
rev = [1]*(n+1)
 
for i in range(1,n+1):
  fac[i] = i*fac[i-1]%MOD
  rev[i] = pow(fac[i], MOD-2, MOD)
 
comb = lambda a,b:(fac[a]*rev[a-b]*rev[b])%MOD if a>=b else 0

for i, j in enumerate(l):
    if d[j] != -1:
        break
    d[j] = i

for i in range(1, N+2):
    print((comb(N+1, i)-comb(d[j]+N-1, i-1))%MOD)



Fixed submission:
N = int(input())
d = {i:-1 for i in range(1, N+1)}
*l, = map(int, input().split())

MOD = 10**9+7
n = N+1
fac = [1]*(n+1)
rev = [1]*(n+1)
 
for i in range(1,n+1):
  fac[i] = i*fac[i-1]%MOD
  rev[i] = pow(fac[i], MOD-2, MOD)
 
comb = lambda a,b:(fac[a]*rev[a-b]*rev[b])%MOD if a>=b else 0

for i, j in enumerate(l):
    if d[j] != -1:
        break
    d[j] = i

a = d[j]
b = N-i
for i in range(1, N+2):
    print((comb(N+1, i)-comb(a+b, i-1))%MOD)
Buggy python submission (verdict: Time Limit Exceeded):
class UFT(object):
  def __init__(self,N):
    self.par={i:i for i in range(1,N+1)}
    self.h={i:0 for i in range(1,N+1)}
  def find(self,n):
    if self.par[n]==n:
      return n
    else:
      self.par[n]=self.find(self.par[n])
      return self.par[n]
  def unite(self,a,b):
    a=self.find(a)
    b=self.find(b)
    if self.h[a]>self.h[b]:
      self.par[b]=a
    else:
      self.par[a]=b
      if self.h[a]==self.h[b]:
        self.h[b]+=1
  def issame(self,a,b):
    return self.find(a)==self.find(b)

N=int(input())
obj=UFT(N)
d={i:0 for i in range(1,N+1)}
for i in range(N):
  b=int(input())
  d[i+1]=b
  obj.unite(i+1,b)

if obj.issame(2,1):
  c=1
  e=d[1]
  while e!=2:
    c+=1
    e=d[e]
  print(c)
else:
  print("-1")

Fixed submission:
n=int(input())
d={i:int(input()) for i in range(1,n+1)}

f=True
s=1
for i in range(n):
  if s==2:
    print(i)
    f=False
    break
  s=d[s]
if f:
  print(-1)
Buggy python submission (verdict: Time Limit Exceeded):
class UnionFind(object):
  def __init__(self,n):
    *self.par,=range(n+1)
    self.rank=[0]*(n+1)

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

  def union(self,x,y):
    x=self.find(x)
    y=self.find(y)
    if self.rank[x]<self.rank[y]:
      self.par[x]=y
    else:
      self.par[y]=x
      if self.rank[x]==self.rank[y]:
        self.rank[x]+=1

n=int(input())
x=[[0,0] for _ in range(n)]
y=[[0,0] for _ in range(n)]

for i in range(n):
  x[i][0],y[i][0]=map(int,input().split())
  x[i][1],y[i][1]=i+1,i+1

dx,dy=[],[]
x,y=sorted(x),sorted(y)
for i in range(n-1):
  dx.extend([(abs(x[i][0]-x[i+1][0]),x[i][1],x[i+1][1])])
  dy.extend([(abs(y[i][0]-y[i+1][0]),y[i][1],y[i+1][1])])

target=sorted(dx+dy)
tree=UnionFind(n)
cnt,cost,i=0,0,0

while cnt<n-1:
  c,a,b=target[i]
  if tree.find(a)!=tree.find(b):
    cost+=c
    tree.union(a,b)
    cnt+=1
  i+=1

print(cost)


Fixed submission:
class UnionFind(object):
  def __init__(self,n):
    *self.par,=range(n+1)
    self.rank=[0]*(n+1)

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

  def union(self,x,y):
    x=self.find(x)
    y=self.find(y)
    if self.rank[x]<self.rank[y]:
      self.par[x]=y
    else:
      self.par[y]=x
      if self.rank[x]==self.rank[y]:
        self.rank[x]+=1

n=int(input())
x=[[0,0] for _ in range(n)]
y=[[0,0] for _ in range(n)]

for i in range(n):
  x[i][0],y[i][0]=map(int,input().split())
  x[i][1],y[i][1]=i+1,i+1

dx,dy=[],[]
x,y=sorted(x),sorted(y)
for i in range(n-1):
  dx.extend([(abs(x[i][0]-x[i+1][0]),x[i][1],x[i+1][1])])
  dy.extend([(abs(y[i][0]-y[i+1][0]),y[i][1],y[i+1][1])])

target=sorted(dx+dy)
tree=UnionFind(n)
cnt,cost,i=0,0,0

while cnt<n-1:
  c,a,b=target[i]
  if tree.find(a)!=tree.find(b):
    cost+=c
    tree.union(a,b)
    cnt+=1
  i+=1

print(cost)
Buggy python submission (verdict: Time Limit Exceeded):
from math import ceil

N,A,B=map(int,input().split())
h=[int(input()) for _ in range(N)]

def f(k):
    g=lambda x:ceil((x-B*k)/(A-B))
    return(sum(filter(lambda x:x>0,map(g,h)))<=k)

l,r=0,ceil(max(h)/B)

while r-l>1:
    if f((l+r)//2):
        r=(l+r)//2
    else:
        l=(l+r)//2

print(r)

Fixed submission:
n,a,b=map(int,input().split())
h=[int(input()) for _ in [0]*n]
f=lambda n:lambda x:x-b*n

def calc(n):
  g=f(n)
  k=lambda x:1+x//(a-b) if x%(a-b) else x//(a-b)
  o=filter(lambda x:x>0,map(g,h))
  *p,=map(k,o)
  if not p:
    return True
  else:
    return sum(p)<=n

l,r=0,max(h)
while r-l>1:
  m=(r+l)//2
  if calc(m):
    r=m
  else:
    l=m
print(r)
Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
a,b,c=[None]*n,[None]*n,[None]*n
inf=float("inf")
d=[inf]*n
neg=[False]*n
d[0]=0

for i in range(m):
  a[i],b[i],c[i]=map(int,input().split())
  c[i]=-c[i]

for loop in range(n-1):
  for i in range(m):
    if d[a[i]-1]==inf:continue
    if d[b[i]-1]>d[a[i]-1]+c[i]:
      d[b[i]-1]=d[a[i]-1]+c[i]
ans=d[n-1]

for loop in range(n):
  for i in range(m):
    if d[a[i]-1]==inf:continue
    if d[b[i]-1]>d[a[i]-1]+c[i]:
      d[b[i]-1]=d[a[i]-1]+c[i]
      neg[b[i]-1]=True
    if neg[a[i]-1]:
      neg[b[i]-1]=True

if neg[n-1]:
  print("inf")
else:
  print(-ans)

Fixed submission:
n,m=map(int,input().split())
inf=float("inf")
l=[tuple(map(int,input().split())) for i in range(m)]
 
d=[inf]*n
d[0]=0

for i in range(n):
  for a,b,c in l:
    a,b,c=a-1,b-1,-c
    if d[a]!=inf and d[b]>d[a]+c:
      d[b]=d[a]+c
      if i==n-1 and b==n-1:
        print("inf")
        exit()
print(-d[-1])

Buggy python submission (verdict: Runtime Error):
from heapq import heappush,heappop
n,m=map(int,input().split())
a,b,c=[None]*n,[None]*n,[None]*n
inf=float("inf")
d=[inf]*n

for i in range(m):
  a[i],b[i],c[i]=map(int,input().split())
  c[i]=-c[i]

d[0]=0
for loop in range(n-1):
  for i in range(m):
    if d[a[i]-1]==inf:continue
    if d[b[i]-1]>d[a[i]-1]+c[i]:
      d[b[i]-1]=d[a[i]-1]+c[i]
      
ans=-d[n-1]
neg=[False]*n
for loop in range(n):
  for i in range(m):
    if d[a[i]-1]==inf:continue
    if d[b[i]-1]>d[a[i]-1]+c[i]:
      d[b[i]-1]=d[a[i]-1]+c[i]
      neg[b[i]-1]=True
    if neg[a[i]-1]:
      neg[b[i]-1]=True

if neg[n-1]:
  print("inf")
else:
  print(ans)

Fixed submission:
n,m=map(int,input().split())
inf=float("inf")
l=[tuple(map(int,input().split())) for i in range(m)]
 
d=[inf]*n
d[0]=0

for i in range(n):
  for a,b,c in l:
    a,b,c=a-1,b-1,-c
    if d[a]!=inf and d[b]>d[a]+c:
      d[b]=d[a]+c
      if i==n-1 and b==n-1:
        print("inf")
        exit()
print(-d[-1])
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
n,m=map(int,input().split())
l=[]
for _ in range(m):
  a,b=map(int,input().split())
  if a>b:a,b=b,a
  l.extend([(i,i+1) for i in range(a,b)])
c=Counter(l)
*v,=filter(lambda x:x%2,c.values())
if v:
  print("NO")
else:
  print("YES")

Fixed submission:
from itertools import accumulate as ac
n,m=map(int,input().split())
l=[0]*(n+1)
for _ in range(m):
  a,b=map(int,input().split())
  if a>b:a,b=b,a
  l[a]+=1
  l[b]-=1

*l,=ac(l)
*l,=filter(lambda x:x%2,l)
if l:
  print("NO")
else:
  print("YES")
Buggy python submission (verdict: Time Limit Exceeded):
N,W=map(int,input().split())
w,v=[None]*N,[None]*N
inf=float('inf')
dp=[[0 for _ in range(W+1)] for _ in range(N+1)]
for i in range(N):
  w[i],v[i]=map(int,input().split())

for i in range(N-1,-1,-1):
  for j in range(W+1):
    if j<w[i]:
      dp[i][j]=dp[i+1][j]
    else:
      dp[i][j]=max(dp[i+1][j],dp[i+1][j-w[i]]+v[i])

print(dp[0][W])

Fixed submission:
from collections import defaultdict as dd
from itertools import accumulate as ac
from itertools import product as pr

N,W=map(int,input().split())
d=dd(list)
for _ in range(N):
  w,v=map(int,input().split())
  d[w].extend([v])
d=dict(d)
for i in d.keys():
  d[i].sort(reverse=True)
  d[i]=[0]+list(ac(d[i]))

l=[]
key=list(d.keys())
for val in pr(*map(enumerate,d.values())):
  weight=sum(map(lambda x,y:x*y[0],key,val))
  value=sum(map(lambda x:x[1],val))
  if weight<=W:
    l.extend([value])

print(max(l))

Buggy python submission (verdict: Time Limit Exceeded):
N,W=map(int,input().split())
w,v=[None]*N,[None]*N
inf=float('inf')
dp=[[0 for _ in range(W+1)] for _ in range(N+1)]
for i in range(N):
  w[i],v[i]=map(int,input().split())

for i in range(N-1,-1,-1):
  for j in range(W+1):
    if j<w[i]:
      dp[i][j]=dp[i+1][j]
    else:
      dp[i][j]=max(dp[i+1][j],dp[i+1][j-w[i]]+v[i])

print(dp[0][W])

Fixed submission:
from collections import defaultdict as dd
from itertools import accumulate as ac
from itertools import product as pr

N,W=map(int,input().split())
d=dd(list)
for _ in range(N):
  w,v=map(int,input().split())
  d[w].extend([v])
d=dict(d)
for i in d.keys():
  d[i].sort(reverse=True)
  d[i]=[0]+list(ac(d[i]))

l=[]
key=list(d.keys())
for val in pr(*map(enumerate,d.values())):
  weight=sum(map(lambda x,y:x*y[0],key,val))
  value=sum(map(lambda x:x[1],val))
  if weight<=W:
    l.extend([value])

print(max(l))
Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
*x,=map(int,input().split())
*y,=map(int,input().split())
mod=10**9+7
vx,vy=0,0
for i in range(n):
  vx+=(i*x[i]-(n-i-1)*x[i])
for j in range(m):
  vy+=(j*x[j]-(m-j-1)*x[j])
print(vx*vy%mod)

Fixed submission:
n,m=map(int,input().split())
*x,=map(int,input().split())
*y,=map(int,input().split())
mod=10**9+7
vx,vy=0,0
for i in range(n):
  vx+=(i*x[i]-(n-i-1)*x[i])
for j in range(m):
  vy+=(j*y[j]-(m-j-1)*y[j])
print(vx*vy%mod)
Buggy python submission (verdict: Runtime Error):
W,a,b=map(int,input().split())
print(min(b-a,b-a+1-w))

Fixed submission:
W,a,b=map(int,input().split())
s={i for i in range(a,a+W+1)}&{i for i in range(b,b+W+1)}
if s:
  print(0)
else:
  print(min(abs(b-a-W),abs(b+W-a)))
Buggy python submission (verdict: Runtime Error):
def f():
  n,m=map(int,input().split())
  o=[input() for _ in range(n)]
  p=[input() for _ in range(m)]
  for i in range(n-m+1):
    for j in range(n-m+1):
      for k in range(i,n-m+1):
        for l in range(j,n-m+1):
          if p[k-i][l-j]!=o[k][l]:
            return False
  return True

if f():
  print("Yes")
else:
  print("No")

Fixed submission:
def func():
  n,m=map(int,input().split())
  o=[input() for _ in range(n)]
  p=[input() for _ in range(m)]
  q=[]
  for i in range(n-m+1):
    for j in range(n-m+1):
      fl=True
      for k in range(m):
        for l in range(m):
          if p[k][l]!=o[i+k][j+l]:
            fl=False
      q.extend([fl])
  return q

a=func()
if sum(a):
  print("Yes")
else:
  print("No")

Buggy python submission (verdict: Runtime Error):
def f():
  n,m=map(int,input().split())
  o=[input() for _ in range(n)]
  p=[input() for _ in range(m)]
  for i in range(n-m+1):
    for j in range(n-m+1):
      for k in range(i,n-m+1):
        for l in range(j,n-m+1):
          if p[k-i][l-i]!=o[k][l]:
            return False
  return True

if f():
  print("Yes")
else:
  print("No")

Fixed submission:
def func():
  n,m=map(int,input().split())
  o=[input() for _ in range(n)]
  p=[input() for _ in range(m)]
  q=[]
  for i in range(n-m+1):
    for j in range(n-m+1):
      fl=True
      for k in range(m):
        for l in range(m):
          if p[k][l]!=o[i+k][j+l]:
            fl=False
      q.extend([fl])
  return q

a=func()
if sum(a):
  print("Yes")
else:
  print("No")

Buggy python submission (verdict: Runtime Error):
def f():
  n,m=map(int,input().split())
  o=[input() for _ in range(n)]
  p=[input() for _ in range(m)]
  for i in range(n-m+1):
    for j in range(n-m+1):
      for k in range(i,n-1):
        for l in range(j,n-1):
          if p[k-i][l-i]!=o[k][l]:
            return False
  return True

if f():
  print("Yes")
else:
  print("No")

Fixed submission:
def func():
  n,m=map(int,input().split())
  o=[input() for _ in range(n)]
  p=[input() for _ in range(m)]
  q=[]
  for i in range(n-m+1):
    for j in range(n-m+1):
      fl=True
      for k in range(m):
        for l in range(m):
          if p[k][l]!=o[i+k][j+l]:
            fl=False
      q.extend([fl])
  return q

a=func()
if sum(a):
  print("Yes")
else:
  print("No")
Buggy python submission (verdict: Runtime Error):
n,Ma,Mb=map(int,input().split())
inf=float("inf")
dp=[[[inf]*401 for _ in range(401)] for _ in range(n+1)]
dp[0][0][0]=0

l=[tuple(map(int,input().split())) for _ in range(n)]

for i in range(1,n+1):
    for j in range(401):
        for k in range(401):
            a,b,c=l[i-1]
            dp[i][j][k]=min(dp[i][j][k],dp[i-1][j][k])
            if j-a>=0 and k-b>=0:
                dp[i][j][k]=min(dp[i][j][k],dp[i-1][j-a][k-b]+c)

ans=inf
for i in range(1,1+max(400//Ma,400//Mb)):
    ans=min(ans,dp[n][Ma*i][Mb*i])

print(ans if ans!=inf else -1)

Fixed submission:
nmax,abmax=40,10
n,ma,mb=map(int,input().split())
a,b,c=[None]*n,[None]*n,[None]*n
inf=float("inf")
for i in range(n):
  a[i],b[i],c[i]=map(int, input().split())
dp = [[[inf for _ in range(nmax*abmax+1)] for _ in range(nmax*abmax+1)] for _ in range(nmax+1)]
dp[0][0][0]=0
for i in range(n):
  for ca in range(nmax*abmax+1):
    for cb in range(nmax*abmax+1):
      if dp[i][ca][cb]==inf:continue
      dp[i+1][ca][cb]=min(dp[i+1][ca][cb],dp[i][ca][cb])
      dp[i+1][ca+a[i]][cb+b[i]]=min(dp[i+1][ca+a[i]][cb+b[i]],dp[i][ca][cb]+c[i])

ans=inf
for ca in range(1,nmax*abmax+1):
  for cb in range(1,nmax*abmax+1):
    if ca*mb==cb*ma:ans=min(ans,dp[n][ca][cb])
if ans==inf:
  print(-1)
else:
  print(ans)
Buggy python submission (verdict: Runtime Error):
n=int(input())
*l,=map(int,input().split())
m=[0]*n
a=n*(n+1)//2
b=sum(l)

if b%a:
  print("NO")
else:
  k=b//a
  for i in range(n):
    m[i]=(l[(i+1)%n]-l[i]-k)

*o,=filter(lambda x:x<0 and x%n==0,m)
if len(o)==k:
  print("YES")
else:
  print("NO")

Fixed submission:
n=int(input())
*l,=map(int,input().split())
m=[0]*n
a=n*(n+1)//2
b=sum(l)

if b%a:
  print("NO")
else:
  k=b//a
  m=[l[(i+1)%n]-l[i]-k for i in range(n)]
  for i in range(n):
    if m[i]>0 or m[i]%n!=0:
      print("NO")
      break
  else:
    print("YES")
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from functools import lru_cache
sys.setrecursionlimit(1000000)
input=sys.stdin.readline

N = int(input())
par = {i:[] for i in range(1, N+1)}
for i in range(2, N+1):
    a = int(input())
    par[a].append(i)

@lru_cache(maxsize=None)
def dfs(s):
    depth = 1
    res = sorted(dfs(t) for t in par[s])[::-1]
    for i, j in enumerate(res, start=1):
        depth = max(depth, i+j)
    return depth

print(dfs(1)-1)

Fixed submission:
import sys
from functools import lru_cache
sys.setrecursionlimit(1000000)
input=sys.stdin.readline


N = int(input())
par = {i:[] for i in range(1, N+1)}

for i in range(2, N+1):
    a = int(input())
    par[a].append(i)

@lru_cache(maxsize=None)
def dfs(s):
    depth = 1
    res = []
    for t in par[s]:
        res.append(dfs(t))
    res.sort(reverse=True)
    for i, j in enumerate(res, start=1):
        depth = max(depth, i+j)
    return depth

print(dfs(1)-1)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from functools import lru_cache
sys.setrecursionlimit(1000000)
input=sys.stdin.readline


N = int(input())
par = {i:[] for i in range(1, N+1)}

for i in range(2, N+1):
    a = int(input())
    par[a].append(i)

@lru_cache(maxsize=None)
def dfs(s):
    depth = 1
    res = []
    for t in par[s]:
        res.append(dfs(t))
    res.sort(reverse=True)
    for i, j in enumerate(res, start=1):
        depth = max(depth, i+j)
    return depth

print(dfs(1)-1)

Fixed submission:
import sys
from functools import lru_cache
sys.setrecursionlimit(1000000)
input=sys.stdin.readline


N = int(input())
par = {i:[] for i in range(1, N+1)}

for i in range(2, N+1):
    a = int(input())
    par[a].append(i)

@lru_cache(maxsize=None)
def dfs(s):
    depth = 1
    res = []
    for t in par[s]:
        res.append(dfs(t))
    res.sort(reverse=True)
    for i, j in enumerate(res, start=1):
        depth = max(depth, i+j)
    return depth

print(dfs(1)-1)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(1000000)
input=sys.stdin.readline

N = int(input())
par = {i:[] for i in range(1, N+1)}

for i in range(2, N+1):
    a = int(input())
    par[a].append(i)

def dfs(s):
    depth = 1
    res = []
    for t in par[s]:
        res.append(dfs(t))
    res.sort(reverse=True)
    for i, j in enumerate(res, start=1):
        depth = max(depth, i+j)
    return depth

print(dfs(1)-1)

Fixed submission:
import sys
from functools import lru_cache
sys.setrecursionlimit(1000000)
input=sys.stdin.readline


N = int(input())
par = {i:[] for i in range(1, N+1)}

for i in range(2, N+1):
    a = int(input())
    par[a].append(i)

@lru_cache(maxsize=None)
def dfs(s):
    depth = 1
    res = []
    for t in par[s]:
        res.append(dfs(t))
    res.sort(reverse=True)
    for i, j in enumerate(res, start=1):
        depth = max(depth, i+j)
    return depth

print(dfs(1)-1)
Buggy python submission (verdict: Runtime Error):
from collections import Counter
from functools import reduce
n=int(input())
l=[]

for j in range(2,n+1):
  n=j
  for i in range(2,j+1):
    while not n%i:
      l.extend([i])
      n//=i
o=Counter(l)
p=int(1e9+7)
v=reduce(lambda x,y:x*y,map(lambda x:x+1,o.values()))%p
print(v)

Fixed submission:
from collections import Counter
from functools import reduce
n=int(input())
l=[]

for j in range(2,n+1):
  b=j
  for i in range(2,j+1):
    while not b%i:
      l.extend([i])
      b//=i
o=Counter(l)
p=int(1e9+7)
if n!=1:
  v=reduce(lambda x,y:x*y,map(lambda x:x+1,o.values()))%p
else:
  v=1
print(v)
Buggy python submission (verdict: Time Limit Exceeded):
from functools import lru_cache
n,a,b,c,d=map(int,input().split())

mod=10**9+7
fac=[1]*(n+3)
finv=[1]*(n+3)

t=1
for i in range(1,n+3):
    t*=i
    t%=mod
    fac[i]=t

t=1
for i in range(1,n+3):
    t*=pow(i,mod-2,mod)
    t%=mod
    finv[i]=t

@lru_cache()
def comb(a,b):
    if a<b:return 0
    return fac[a]*(finv[a-b]*finv[b]%mod)%mod

dp=[[0 if i else 1 for i in range(n+2)] for _ in range(n+2)]

for i in range(a,b+1):
    for j in range(n+1):
        if not dp[i][j]:continue
        if j:dp[i+1][j]=(dp[i+1][j]+dp[i][j])%mod
        p=1
        for k in range(1,1+(n-j)//i):
            if not k<=d:break
            p=((p*comb(n-j-i*(k-1),i)%mod)*pow(k,mod-2,mod))%mod

            if k>=c:
                dp[i+1][j+i*k]+=(dp[i][j]*p%mod)
                dp[i+1][j+i*k]%=mod

print(dp[b+1][n]%mod)


Fixed submission:
from functools import lru_cache
n,a,b,c,d=map(int,input().split())

mod=10**9+7
fac=[1]*(n+3)
finv=[1]*(n+3)

t=1
for i in range(1,n+1):
    t*=i
    t%=mod
    fac[i]=t
t=1
for i in range(1,n+1):
    t*=pow(i,mod-2,mod)
    t%=mod
    finv[i]=t

finvp = [finv]
for i in range(n-1):
    p=finvp[-1]
    q=[p[i]*finv[i]%mod for i in range(n+1)]
    finvp.append(q)

dp = [[0 for _ in range(n+1)] for _ in range(b+1)]
dp[a-1][0] = 1

for i in range(a-1,b):
    for j in range(n+1):
        dp[i+1][j]=dp[i][j]
        for k in range(c,1+min(d,j//(i+1))):
            x=j-k*(i+1)
            dp[i+1][j]+=fac[j]*finv[x]*finvp[k-1][i+1]*finv[k]*dp[i][x]%mod
        dp[i+1][j]%=mod
print(dp[b][n])

Buggy python submission (verdict: Time Limit Exceeded):
n,a,b,c,d=map(int,input().split())

mod=10**9+7
fac=[1]*(n+3)
finv=[1]*(n+3)

t=1
for i in range(1,n+3):
    t*=i
    t%=mod
    fac[i]=t

t=1
for i in range(1,n+3):
    t*=pow(i,mod-2,mod)
    t%=mod
    finv[i]=t

def comb(a,b):
    if a<b:return 0
    return fac[a]*(finv[a-b]*finv[b]%mod)%mod

dp=[[0 if i else 1 for i in range(n+2)] for _ in range(n+2)]

for i in range(a,b+1):
    for j in range(n+1):
        if not dp[i][j]:continue
        if j:dp[i+1][j]=(dp[i+1][j]+dp[i][j])%mod
        p=1
        for k in range(1,1+(n-j)//i):
            if not k<=d:break
            p=((p*comb(n-j-i*(k-1),i)%mod)*pow(k,mod-2,mod))%mod

            if k>=c:
                dp[i+1][j+i*k]+=(dp[i][j]*p%mod)
                dp[i+1][j+i*k]%=mod

print(dp[b+1][n]%mod)


Fixed submission:
from functools import lru_cache
n,a,b,c,d=map(int,input().split())

mod=10**9+7
fac=[1]*(n+3)
finv=[1]*(n+3)

t=1
for i in range(1,n+1):
    t*=i
    t%=mod
    fac[i]=t
t=1
for i in range(1,n+1):
    t*=pow(i,mod-2,mod)
    t%=mod
    finv[i]=t

finvp = [finv]
for i in range(n-1):
    p=finvp[-1]
    q=[p[i]*finv[i]%mod for i in range(n+1)]
    finvp.append(q)

dp = [[0 for _ in range(n+1)] for _ in range(b+1)]
dp[a-1][0] = 1

for i in range(a-1,b):
    for j in range(n+1):
        dp[i+1][j]=dp[i][j]
        for k in range(c,1+min(d,j//(i+1))):
            x=j-k*(i+1)
            dp[i+1][j]+=fac[j]*finv[x]*finvp[k-1][i+1]*finv[k]*dp[i][x]%mod
        dp[i+1][j]%=mod
print(dp[b][n])
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import accumulate as ac
n,k=map(int,input().split())
*l,=map(int,input().split())
*m,=map(lambda x:max(x,0),l)
*acc,=ac([0]+l)
v=0
for i in range(n-k+1):
  v=max(v,max(0,acc[i+k]-acc[i])+sum(m[i+k:])+sum(m[:i]))
print(v)

Fixed submission:
from itertools import accumulate as ac
n,k=map(int,input().split())
*l,=map(int,input().split())
*m,=map(lambda x:max(x,0),l)
*acc,=ac([0]+l)
*acm,=ac([0]+m)
v=0
for i in range(n-k+1):
  v=max(v,max(0,acc[i+k]-acc[i])+acm[n]-acm[i+k]+acm[i])
print(v)