Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
from collections import deque

N,M,K = map(int,input().split())
Ali = list(map(int,input().split()))
Bli = list(map(int,input().split()))

q = deque()
q.append([0,0,0])#(time,a,b)
r = 0
k = 0

while len(q) > 0:
  time,a,b = q.popleft()
  
  r = max(r,a+b)
    
  
  if a<N:
    if k == [a+1,b]:
      continue
    if Ali[a] <= K-time:
      q.append([time+Ali[a],a+1,b])
    
  if b<M:
    if Bli[b] <= K-time:
      q.append([time+Bli[b],a,b+1])
    
  k = [a,b+1]
    
print(r)

Fixed submission:
def dt(n):
  table = [0] * (n + 1)
  r = 0
    
  for i in range(1, n + 1):
    for j in range(i, n + 1, i):
      table[j] += 1
    
  for i in range(1,n+1):
    r += i*table[i]
    
  return r

N = int(input())
print(dt(N))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
Ali = list(map(int,input().split()))

Ali.sort()

Alis = set(Ali)
Blis = set(Ali)

for el in Alis:
  if Ali.count(el) > 1:
    Blis.remove(el)

Alis = Blis

for i in range(N):
  Alis.difference_update(range(Ali[i]*2, Ali[-1]+1, Ali[i]))
  
print(len(Alis))

Fixed submission:
N = int(input())
Ali = list(map(int,input().split()))
Alis = set()
Blis = set()

Ali.sort()

for i in range(N):
  if Ali[i] in Alis:
    Blis.add(Ali[i])
    continue
  Alis.add(Ali[i])

Alis -= Blis

for i in range(N):
  Alis.difference_update(range(Ali[i]*2, Ali[-1]+1, Ali[i]))
  
print(len(Alis))
Buggy python submission (verdict: Runtime Error):
N = int(input())+1
ali = list(map(int,input().split()))
nli = [0]*N

maxn = 2**(N-1)
nli[-1] = ali[-1]

for i in range(1,N+1):
  nli[-i] = min(maxn,nli[-i+1] + ali[-i])
  maxn //= 2
  

ulim = 1
for i in range(N):
  nli[i] = min(nli[i],ulim)
  ulim = (ulim - ali[i])*2
  if i != N-1 and ulim <= 0:
    print(-1)
    print(nli[N+1])
    exit()
  
print(sum(nli))

Fixed submission:
N = int(input())+1
ali = list(map(int,input().split()))
nli = [0]*N

maxn = 2**(N-1)
nli[-1] = ali[-1]

for i in range(1,N+1):
  nli[-i] = min(maxn,nli[-i+1] + ali[-i])
  maxn //= 2
  

ulim = 1
for i in range(N):
  nli[i] = min(nli[i],ulim)
  ulim = (ulim - ali[i])*2
  if ulim < 0:
    print(-1)
    exit()
  
print(sum(nli))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()

rn = [0]*(N+1)
gn = [0]*(N+1)
bn = [0]*(N+1)

for i in range(N):
    rn[i+1] = rn[i]
    gn[i+1] = gn[i]
    bn[i+1] = bn[i]
    if S[i]=="R":
        rn[i+1] = rn[i]+1
    if S[i]=="G":
        gn[i+1] = gn[i]+1
    if S[i]=="B":
        bn[i+1] = bn[i]+1
   
ans = 0
for i in range(N):
    a = S[i]
    rem = "RGB".replace(a,"")
    for j in range(N-i):
        if (S[j+i] == a):
            continue
        b = S[j+i]
        rem2 = rem.replace(b,"")
        if rem2 == "R":
            ans += rn[N]-rn[j+i+1]
        if rem2 == "G":
            ans += gn[N]-gn[j+i+1]
        if rem2 == "B":
            ans += bn[N]-bn[j+i+1]
        if 0 <= j*2+i <= N-1:
          if S[j*2+i] == rem2 :
              ans -=1
            
print(ans)
        

Fixed submission:
N = int(input())
S = input()

rn = [0]*(N+1)
gn = [0]*(N+1)
bn = [0]*(N+1)

for i in range(N):
    rn[i+1] = rn[i]
    gn[i+1] = gn[i]
    bn[i+1] = bn[i]
    if S[i]=="R":
        rn[i+1] = rn[i]+1
    if S[i]=="G":
        gn[i+1] = gn[i]+1
    if S[i]=="B":
        bn[i+1] = bn[i]+1
   
ans = 0
for i in range(N):
    a = S[i]
    rem = "RGB".replace(a,"")
    for j in range(N-i):
        if (S[j+i] == a):
            continue
        b = S[j+i]
        rem2 = rem.replace(b,"")
        if rem2 == "R":
            ans += rn[N]-rn[j+i+1]
        if rem2 == "G":
            ans += gn[N]-gn[j+i+1]
        if rem2 == "B":
            ans += bn[N]-bn[j+i+1]
        if 0 <= j*2+i <= N-1:
          if S[j*2+i] == rem2 :
              ans -=1
            
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,x,y = map(int, input().split())
dp = [[100000000 for j in range(n)] for i in range(n)]
re = [0]*n
for i in range(n):
  for j in range(n):
    if i==j:
      dp[i][j] = 0
    if abs(i-j)==1:
      dp[i][j] = 1
    if i==x-1 and j==y-1:
      dp[i][j] = 1
    if i==y-1 and j==x-1:
      dp[i][j] = 1
    

for k in range(n):
  for i in range(n):
    for j in range(n):
      dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);


for i in range(n):
  for j in range(i):
    re[dp[i][j]] +=1
    
for i in range(n-1):
  print(re[i+1])

Fixed submission:
n,x,y = map(int, input().split())
p = [[100000000 for j in range(n)] for i in range(n)]
dp = [(-1,0),(1,0),(0,-1),(0,1)]
c = [[] for i in range(n)]

for i in range(n):
  for j in range(n-i):
    j += i
    if i==j:
      p[i][j] = 0
    if abs(i-j)==1:
      p[i][j] = 1
      c[1].append((i,j))
    if i==x-1 and j==y-1:
      p[i][j] = 1
      c[1].append((i,j))
    if i==y-1 and j==x-1:
      p[i][j] = 1
      c[1].append((i,j))
    
print(len(c[1]))

for i in range(n-2):
  i += 2
  for (a,b) in c[i-1]:
    for (da,db) in dp:
      aa = a + da
      bb = b + db
      if not (0 <= aa < n and 0 <= bb < n):
        continue
      if p[aa][bb] > i:
        p[aa][bb] = i
        c[i].append((aa,bb))
  print(len(c[i]))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

n,x,y = map(int, input().split())
dp = [[100000000 for j in range(n)] for i in range(n)]
re = [0]*n
for i in range(n):
  for j in range(n):
    if i==j:
      dp[i][j] = 0
    if abs(i-j)==1:
      dp[i][j] = 1
    if i==x-1 and j==y-1:
      dp[i][j] = 1
    if i==y-1 and j==x-1:
      dp[i][j] = 1
    

for k in range(n):
  for i in range(n):
    for j in range(n):
      dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);


for i in range(n):
  for j in range(i):
    re[dp[i][j]] +=1
    
for i in range(n-1):
  print(re[i+1])

Fixed submission:
n,x,y = map(int, input().split())
p = [[100000000 for j in range(n)] for i in range(n)]
dp = [(-1,0),(1,0),(0,-1),(0,1)]
c = [[] for i in range(n)]

for i in range(n):
  for j in range(n-i):
    j += i
    if i==j:
      p[i][j] = 0
    if abs(i-j)==1:
      p[i][j] = 1
      c[1].append((i,j))
    if i==x-1 and j==y-1:
      p[i][j] = 1
      c[1].append((i,j))
    if i==y-1 and j==x-1:
      p[i][j] = 1
      c[1].append((i,j))
    
print(len(c[1]))

for i in range(n-2):
  i += 2
  for (a,b) in c[i-1]:
    for (da,db) in dp:
      aa = a + da
      bb = b + db
      if not (0 <= aa < n and 0 <= bb < n):
        continue
      if p[aa][bb] > i:
        p[aa][bb] = i
        c[i].append((aa,bb))
  print(len(c[i]))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int,input().split()))
c = [0]*N
p = 0

for i in range(N):
  c[i] = A.count(i+1)

for i in range(N):
  if c[i] > 1:
    p += (c[i])*(c[i]-1)//2

for i in range(N):
  if c[A[i]-1] > 1:
    print(p-(c[A[i]-1]-1))
  else:
    print(0)


Fixed submission:
import collections

N = int(input())
A = list(map(int,input().split()))
c = [0]*N
p = 0


c = collections.Counter(A)

for i in range(N):
  p += (c[i+1])*(c[i+1]-1)//2

for i in range(N):
  print(p-c[A[i]]+1)
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
Q = int(input())
rev = 0

for _ in range(Q):
  a = list(input().split())
  if a[0] == "1":
    rev += 1
  else:
    if rev%2 == 0:
      if a[1] == "1":
        S = a[2] + S
      else:
        S = S + a[2]
    else:
      if a[1] == "2":
        S = a[2] + S
      else:
        S = S + a[2]
      
if rev%2 == 1:
  S = S[::-1]
print(S)

Fixed submission:
S = input()
Q = int(input())
rev = 0
top = []
bot = []

for _ in range(Q):
  a = list(input().split())
  if a[0] == "1":
    rev += 1
  else:
    if rev%2 == 0:
      if a[1] == "1":
        top.append(a[2])
      else:
        bot.append(a[2])
    else:
      if a[1] == "2":
        top.append(a[2])
      else:
        bot.append(a[2])
      
t = "".join(top)[::-1]
b = "".join(bot)
S = "".join([t,S,b])
if rev%2 == 1:
  S = S[::-1]
print(S)

Buggy python submission (verdict: Time Limit Exceeded):
S = input()
Q = int(input())

for _ in range(Q):
  a = list(input().split())
  if a[0] == "1":
    S = S[::-1]
  else:
    if a[1] == "1":
      S = a[2] + S
    else:
      S = S + a[2]
      
print(S)

Fixed submission:
S = input()
Q = int(input())
rev = 0
top = []
bot = []

for _ in range(Q):
  a = list(input().split())
  if a[0] == "1":
    rev += 1
  else:
    if rev%2 == 0:
      if a[1] == "1":
        top.append(a[2])
      else:
        bot.append(a[2])
    else:
      if a[1] == "2":
        top.append(a[2])
      else:
        bot.append(a[2])
      
t = "".join(top)[::-1]
b = "".join(bot)
S = "".join([t,S,b])
if rev%2 == 1:
  S = S[::-1]
print(S)
Buggy python submission (verdict: Time Limit Exceeded):
N,K = map(int,input().split())
p = list(map(int,input().split()))
r = 0

for i in range(N-K+1):
  r = max(r,sum(p[i:i+K]))
  
print((r+K)/2)

Fixed submission:
N,K = map(int,input().split())
p = list(map(int,input().split()))
s = sum(p[0:K])
r = s

for i in range(N-K):
  s = s-p[i]+p[i+K]
  r = max(r,s)
  
print((r+K)/2)
Buggy python submission (verdict: Runtime Error):
A,B,C = int(input())
if A+B+C <= 21:
  print("win")
else:
  print("bust")

Fixed submission:
A,B,C = map(int,input().split())
if A+B+C <= 21:
  print("win")
else:
  print("bust")
Buggy python submission (verdict: Runtime Error):
N = int(input())
Ali = list(map(int,input().split()))
Ali = Ali[::-1]
Bli = sorted(Ali)
C = [-1,-1,-1]

for i in range(Ali.count(0)):
  C[i] = Bli[-i-1]+1
  
if Ali.count(0) <= 2:
  r = 3
else:
  r = 1

for i in range(N):
  n = 0
  ta = 0 
  for j in range(3):
    if C[j]-1 == Ali[i]:
      n += 1
      ta = j
  r *= n
  C[ta] = Ali[i]
  
print(r%1000000007)

Fixed submission:
import itertools

N = int(input())
Ali = list(map(int,input().split()))
C = [0,0,0]

for i in range(N):
  n = 0
  for j in range(3):
    if C[j] == Ali[i]:
      C[j] += 1
      break
  
Ali = Ali[::-1]
if C[0] == C[1] == C[2]:
  r = 1
elif C[0] == C[1] or C[1] == C[2] or C[2] == C[0]:
  r = 3
else:
  r = 6

  
for i in range(N):
  n = 0
  ta = 0 
  for j in range(3):
    if C[j]-1 == Ali[i]:
      n += 1
      ta = j
  r *= n
  C[ta] = Ali[i]
  
print(r%1000000007)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**6)

def dfs(ve, add):
  global seen
  global r
  seen[ve] = True
  r[ve] = add
  a = len(ki[ve])
  for i in range(a):
    b = ki[ve][i]
    if not seen[b]:
      dfs(b, add+ook[b])

N,Q = map(int, input().split())
side = [list(map(int, input().split())) for _ in range(N-1)]
op = [list(map(int, input().split())) for _ in range(Q)]
ki = [[] for _ in range(N)]
ook = [0]*N
seen = [False]*N
r = [0]*N

for i in range(N-1):
  a = side[i][0] -1
  b = side[i][1] -1
  ki[a].append(b)
  ki[b].append(a)
  
for i in range(Q):
  ook[op[i][0] -1] += op[i][1]
  
for i in range(N):
  if seen[i]:
    continue
  dfs(i, ook[i])
    
print(" ".join(map(str,r)))

Fixed submission:
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def dfs(ve, add):
  global seen
  global r
  seen[ve] = True
  r[ve] = add
  a = len(ki[ve])
  for i in range(a):
    b = ki[ve][i]
    if not seen[b]:
      dfs(b, add+ook[b])

N,Q = map(int, input().split())
side = [list(map(int, input().split())) for _ in range(N-1)]
op = [list(map(int, input().split())) for _ in range(Q)]
ki = [[] for _ in range(N)]
ook = [0]*N
seen = [False]*N
r = [0]*N

for i in range(N-1):
  a = side[i][0] -1
  b = side[i][1] -1
  ki[a].append(b)
  ki[b].append(a)
  
for i in range(Q):
  ook[op[i][0] -1] += op[i][1]
  
for i in range(N):
  if seen[i]:
    continue
  dfs(i, ook[i])
    
print(" ".join(map(str,r)))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**6)

def dfs(ve, add):
  global seen
  global r
  seen[ve] = True
  r[ve] = add
  a = len(ki[ve])
  for i in range(a):
    b = ki[ve][i]
    if not seen[b]:
      dfs(b, add+ook[b])

N,Q = map(int, input().split())
side = [list(map(int, input().split())) for _ in range(N-1)]
op = [list(map(int, input().split())) for _ in range(Q)]
ki = [[] for _ in range(N)]
ook = [0]*N
seen = [False]*N
r = [0]*N

for i in range(N-1):
  a = side[i][0] -1
  b = side[i][1] -1
  ki[a].append(b)
  ki[b].append(a)
  
for i in range(Q):
  ook[op[i][0] -1] += op[i][1]
  
for i in range(N):
  if not seen[i]:
    dfs(i, ook[i])
    
print(" ".join(map(str,r)))

Fixed submission:
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def dfs(ve, add):
  global seen
  global r
  seen[ve] = True
  r[ve] = add
  a = len(ki[ve])
  for i in range(a):
    b = ki[ve][i]
    if not seen[b]:
      dfs(b, add+ook[b])

N,Q = map(int, input().split())
side = [list(map(int, input().split())) for _ in range(N-1)]
op = [list(map(int, input().split())) for _ in range(Q)]
ki = [[] for _ in range(N)]
ook = [0]*N
seen = [False]*N
r = [0]*N

for i in range(N-1):
  a = side[i][0] -1
  b = side[i][1] -1
  ki[a].append(b)
  ki[b].append(a)
  
for i in range(Q):
  ook[op[i][0] -1] += op[i][1]
  
for i in range(N):
  if seen[i]:
    continue
  dfs(i, ook[i])
    
print(" ".join(map(str,r)))
Buggy python submission (verdict: Time Limit Exceeded):
import bisect

N = int(input())
Ali = [int(input()) for _ in range(N)]
n = N
c = 0

while n > 0:
  dp = [Ali[0]]
  Ali2 = []
  for i in range(1,n):
    a = Ali[i]
    if a > dp[-1]:
      dp.append(a)
    else:
      b = bisect.bisect_left(dp, a)
      Ali2.append(dp[b])
      dp[b] = a
  Ali = Ali2[::1]
  n = len(Ali)
  c += 1
    
print(c)

Fixed submission:
from bisect import bisect
import heapq

N = int(input())
A = [int(input()) for _ in range(N)]
q = []
A.reverse()

for i in range(N):
  ii = bisect(q,A[i])
  if ii == len(q):
    heapq.heappush(q,A[i])
  else:
    q[ii] = A[i]
    
print(len(q))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int,input().split()))
s = sum(A)

for i in range(N):
  a = 0
  for j in range(N//2):
    a += A[(i+j*2+1)%N]
  print(s-a*2, end=" ")
  
print("")

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

n = [0]*N
n[0] = sum(A)-sum(A[1::2])*2
print(n[0], end = " ")

for i in range(N-1):
  n[i+1] = A[i]*2-n[i]
  print(n[i+1], end = " ")

print("")
Buggy python submission (verdict: Runtime Error):
N,M = map(int,input().split())
ks = []
for i in range(M):
  ks.append(list(map(int,input().split())))
p = list(map(int, input().split()))
c = 0

for i in range(2 ** N):
  sw = [0]*N
  for j in range(N):
    if ((i >> j) & 1):
      sw[j] = 1
  frg = True
  for j in range(M):
    a = ks[j][0]
    aa = 0
    for k in range(a):
      aa += sw[k+1]
    if aa%2 != p[j]:
      frg = False
  if frg:
    c += 1
    
print(c)

Fixed submission:
N,M = map(int,input().split())
ks = []
for i in range(M):
  ks.append(list(map(int,input().split())))
p = list(map(int, input().split()))
c = 0

for i in range(2 ** N):
  sw = [0]*N
  for j in range(N):
    if ((i >> j) & 1):
      sw[j] = 1
  frg = True
  for j in range(M):
    a = ks[j][0]
    aa = 0
    for k in range(1,a+1):
      aa += sw[ks[j][k]-1]
    if aa%2 != p[j]:
      frg = False
  if frg:
    c += 1
    
print(c)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

def clamp(a,b,c):
  return min(max(a,b),c)

H,W = map(int,input().split())
A = [input() for _ in range(H)]

D = [[-1]*W for _ in range(H)]
dd = [(1,0),(-1,0),(0,1),(0,-1)]
Q = deque()
res = 0

for i in range(H):
  for j in range(W):
    if A[i][j] == "#":
      D[i][j] = 0
      Q.append([i,j,0])
      
while len(Q)>0:
  x,y,n = Q.popleft()
  for dx,dy in dd:
    xx = clamp(x+dx,0,H-1)
    yy = clamp(y+dy,0,W-1)
    if D[xx][yy] == -1:
      D[xx][yy] = n+1
      Q.append([xx,yy,n+1])
      res = n+1
      
print(res)

Fixed submission:
from collections import deque

def clamp(a,b,c):
  return min(max(a,b),c)

H,W = map(int,input().split())
A = [input() for _ in range(H)]

D = [[-1]*W for _ in range(H)]
dd = [(1,0),(-1,0),(0,1),(0,-1)]
Q = deque()
res = 0

for i in range(H):
  for j in range(W):
    if A[i][j] == "#":
      D[i][j] = 0
      Q.append([i,j,0])
      
while len(Q)>0:
  x,y,n = Q.popleft()
  for dx,dy in dd:
    xx = clamp(x+dx,0,H-1)
    yy = clamp(y+dy,0,W-1)
    if D[xx][yy] == -1:
      D[xx][yy] = n+1
      Q.append([xx,yy,n+1])
      res = n+1
      
print(res)
Buggy python submission (verdict: Runtime Error):
import math
A,B,K = map(int,input().split())
r = []

g = math.gcd(A,B)
for i in range(1,g+1):
  if g%i == 0:
    r.append(i)
    
print(r[K-1])

Fixed submission:
from fractions import gcd
A,B,K = map(int,input().split())
r = []

g = gcd(A,B)
for i in range(1,g+1):
  if g%i == 0:
    r.append(i)
    
print(r[-K])
Buggy python submission (verdict: Time Limit Exceeded):
N,K = map(int,input().split())
h = list(map(int,input().split()))
dp = [10000000000]*(N)
dp[0] = 0

for i in range(N-1):
  for j in range(1,K+1):
    if i+j < N:
      dp[i+j] = min(dp[i+j],dp[i] + abs(h[i+j]-h[i]))
  
print(dp[-1])

Fixed submission:
N,K = map(int,input().split())
h = list(map(int,input().split()))
dp = [10000000000]*(N)
dp[0] = 0

for i in range(N-1):
  for j in range(1,K+1):
    if i+j < N:
      dp[i+j] = min(dp[i+j],dp[i] + abs(h[i+j]-h[i]))
  
print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
N,W = map(int,input().split())
WV = [list(map(int,input().split())) for _ in range(N)]

#i個目を選ぶとき合計価値がjになる場合の重さの最小値
#(i-1,j)  or  (i-1,j-v)+w

dp = [[10**12-1]*100010 for i in range(N)]

dp[0][WV[0][1]] = WV[0][0]
res = WV[0][1]

for i in range(1,N):
  w = WV[i][0]
  v = WV[i][1]
  dp[i][WV[i][1]] = WV[i][0]
  res = max(res,WV[i][1])
  for j in range(1,100010):
    if j>=v:
      dp[i][j] = min(dp[i-1][j],dp[i-1][j-v]+w,dp[i][j])
    else:
      dp[i][j] = min(dp[i-1][j],dp[i][j])
    if 0 < dp[i][j] <= W:
      res = max(res,j)
    
print(res)

Fixed submission:
N,W = map(int,input().split())
WV = [list(map(int,input().split())) for _ in range(N)]

#i個目を選ぶとき合計価値がjになる場合の重さの最小値
#(i-1,j)  or  (i-1,j-v)+w

dp = [[10**12-1]*100010 for i in range(N)]

dp[0][WV[0][1]] = WV[0][0]
res = WV[0][1]

for i in range(1,N):
  w = WV[i][0]
  v = WV[i][1]
  dp[i][WV[i][1]] = WV[i][0]
  res = max(res,WV[i][1])
  for j in range(1,100010):
    if j>=v:
      dp[i][j] = min(dp[i-1][j],dp[i-1][j-v]+w,dp[i][j])
    else:
      dp[i][j] = min(dp[i-1][j],dp[i][j])
    if 0 < dp[i][j] <= W:
      res = max(res,j)
    
print(res)
Buggy python submission (verdict: Runtime Error):
N,M = map(int,input().split())
p = [list(map(int,input().split())) for _ in range(M)]
dp = [-1]*N
ip = [[] for _ in range(N)]
for i in range(M):
  ip[p[i][1]-1].append(p[i][0]-1)

#閉路がないため同じ頂点は通らない
#i番目の頂点に到達するまでの最長手数をメモ化再帰で求める

def maxpath(i):
  if dp[i] != -1:
    return dp[i]
  a = 0
  for el in ip[i]:
    a = max(a,maxpath(el)+1)
  dp[i] = a
  return a
  
for i in range(N):
  maxpath(i)

print(max(dp))

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

N,M = map(int,input().split())
p = [list(map(int,input().split())) for _ in range(M)]
dp = [-1]*N
ip = [[] for _ in range(N)]
for i in range(M):
  ip[p[i][1]-1].append(p[i][0]-1)

#閉路がないため同じ頂点は通らない
#i番目の頂点に到達するまでの最長手数をメモ化再帰で求める

def maxpath(i):
  if dp[i] != -1:
    return dp[i]
  a = 0
  for el in ip[i]:
    a = max(a,maxpath(el)+1)
  dp[i] = a
  return a
  
for i in range(N):
  maxpath(i)

print(max(dp))
Buggy python submission (verdict: Time Limit Exceeded):
import copy

def score(i,j):
  Ali = copy.deepcopy(data)
  Ali[i][j] = 0
  score = 0
  turn = 0
  
  for i in range(1,H+1):
    for j in range(W):
      if Ali[-i][j] == 0:
        for k in range(i+1,H+1):
          if Ali[-k][j] != 0:
            Ali[-i][j] = Ali[-k][j]
            Ali[-k][j] = 0
            break
            
  while True:
    sc = score
    #同じものを消す処理
    for i in range(H):
      a = 0 #今の数字
      b = 0 #今の数字が始まった場所
      
      for j in range(W):
        if Ali[i][j] != a:
          if j-b >= K:
            for k in range(b,j):
              score += Ali[i][k]*2**turn
              Ali[i][k] = 0
          a = Ali[i][j]
          b = j
      if W-b >= K:
        for k in range(b,W):
          score += Ali[i][k]*2**turn
          Ali[i][k] = 0
      
      
    if sc == score:
        break
    turn += 1
      
    #落としていく処理
    #下から上に見ていく
    for i in range(1,H+1):
      for j in range(W):
        if Ali[-i][j] == 0:
          for k in range(i+1,H+1):
            if Ali[-k][j] != 0:
              Ali[-i][j] = Ali[-k][j]
              Ali[-k][j] = 0
              break
              
  return score
  
H,W,K = map(int,input().split())
data = [[int(d) for d in input()] for _ in range(H)]
res = 0

for i in range(H):
  for j in range(W):
    res = max(res,score(i,j))
    
print(res)

Fixed submission:
import copy

def score(i,j):
  Ali = copy.deepcopy(data)
  Ali[i][j] = 0
  score = 0
  turn = 0
  
  for i in range(1,H+1):
    for j in range(W):
      if Ali[-i][j] == 0:
        for k in range(i+1,H+1):
          if Ali[-k][j] != 0:
            Ali[-i][j] = Ali[-k][j]
            Ali[-k][j] = 0
            break
            
  while True:
    sc = score
    #同じものを消す処理
    for i in range(H):
      a = 0 #今の数字
      b = 0 #今の数字が始まった場所
      
      for j in range(W):
        if Ali[i][j] != a:
          if j-b >= K:
            for k in range(b,j):
              score += Ali[i][k]*2**turn
              Ali[i][k] = 0
          a = Ali[i][j]
          b = j
      if W-b >= K:
        for k in range(b,W):
          score += Ali[i][k]*2**turn
          Ali[i][k] = 0
      
      
    if sc == score:
        break
    turn += 1
      
    #落としていく処理
    #下から上に見ていく
    for i in range(1,H+1):
      for j in range(W):
        if Ali[-i][j] == 0:
          for k in range(i+1,H+1):
            if Ali[-k][j] != 0:
              Ali[-i][j] = Ali[-k][j]
              Ali[-k][j] = 0
              break
              
  return score
  
H,W,K = map(int,input().split())
data = [[int(d) for d in input()] for _ in range(H)]
res = 0

for i in range(H):
  for j in range(W):
    res = max(res,score(i,j))
    
print(res)