Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
h,w,m = map(int,input().split())
b = []
x = [0 for _ in range(w)]
y = [0 for _ in range(h)]
for i in range(m):
  bh,bw = map(int,input().split())
  bh -= 1
  bw -= 1
  b.append((bh,bw))
  x[bw] += 1
  y[bh] += 1
#print(b,x,y)

mxx = max(x)
mxy = max(y)
xb = []
for i in range(w):
  xb.append((x[i],i))
xb.sort(reverse = True)
yb = []
for i in range(h):
  yb.append((y[i],i))
yb.sort(reverse = True)
#print(xb,yb)

for xbi,i in xb:
  if xbi < mxx:
    break
  for ybi,j in yb:
    if ybi < mxy:
      continue
    else:
      if (j,i) not in b:
        print(xbi+ybi)
        exit()
print(mxx+mxy-1)

Fixed submission:
h,w,m = map(int,input().split())
b = []
x = [0 for _ in range(w)]
y = [0 for _ in range(h)]
for i in range(m):
  bh,bw = map(int,input().split())
  bh -= 1
  bw -= 1
  b.append((bh,bw))
  x[bw] += 1
  y[bh] += 1
#print(b,x,y)

mxx = max(x)
mxy = max(y)

cmxb = 0
for by,bx in b:
  if y[by]+x[bx] == mxx+mxy:
    cmxb += 1
cmxx = 0
for xi in x:
  if xi == mxx:
    cmxx += 1
cmxy = 0
for yi in y:
  if yi == mxy:
    cmxy += 1
#print(cmxb,cmxx,cmxy)

if cmxb == cmxx*cmxy:
  print(mxx+mxy-1)
else:
  print(mxx+mxy)
Buggy python submission (verdict: Runtime Error):
n,q = map(int,input().split())
c = tuple(map(int,input().split()))
qs = [[] for _ in range(n)]
for i in range(q):
  l,r = map(int,input().split())
  l -= 1
  r -= 1
  qs[l].append((r,i))

class BIT:
    def __init__(self,n):
        self.num=n
        self.dat=[0]*(self.num+1)
        self.depth=n.bit_length()
    
    def add(self,i,x):
        i+=1
        while i<=self.num:
            self.dat[i]+=x
            i+=i&-i
    
    def sum(self,i):
        i+=1
        s=0
        while i>0:
            s+=self.dat[i]
            i-=i&-i
        return s
    
    def lower_bound(self,x):
        sum_=0
        pos=0
        for i in range(self.depth,-1,-1):
            k=pos+(1<<i)
            if k<=self.num and sum_+self.dat[k]<x:
                sum_+=self.dat[k]
                pos+=1<<i
        return pos, sum_

ps = [-1 for _ in range(n)]
pi = [-1 for _ in range(n)]
for i in range(n):
  l = pi[c[i]]
  if l != -1:
    ps[l] = i
  pi[c[i]] = i
    
d = BIT(n)
ans = [0 for _ in range(q)]
for x in range(n-1,-1,-1):
  if ps[x] != -1:
    d.add(ps[x],1)
  for r,i in qs[x]:
    ans[i] = (r-x+1)-d.sum(r)

for i in range(q):
  print(ans[i])


Fixed submission:
n,q = map(int,input().split())
c = tuple(map(int,input().split()))
qs = [[] for _ in range(n)]
for i in range(q):
  l,r = map(int,input().split())
  l -= 1
  r -= 1
  qs[l].append((r,i))

class BIT:
    def __init__(self,n):
        self.num=n
        self.dat=[0]*(self.num+1)
        self.depth=n.bit_length()
    
    def add(self,i,x):
        i+=1
        while i<=self.num:
            self.dat[i]+=x
            i+=i&-i
    
    def sum(self,i):
        i+=1
        s=0
        while i>0:
            s+=self.dat[i]
            i-=i&-i
        return s
    
    def lower_bound(self,x):
        sum_=0
        pos=0
        for i in range(self.depth,-1,-1):
            k=pos+(1<<i)
            if k<=self.num and sum_+self.dat[k]<x:
                sum_+=self.dat[k]
                pos+=1<<i
        return pos, sum_

ps = [-1 for _ in range(n)]
pi = [-1 for _ in range(n+1)]
for i in range(n):
  l = pi[c[i]]
  if l != -1:
    ps[l] = i
  pi[c[i]] = i
    
d = BIT(n)
ans = [0 for _ in range(q)]
for x in range(n-1,-1,-1):
  if ps[x] != -1:
    d.add(ps[x],1)
  for r,i in qs[x]:
    ans[i] = (r-x+1)-d.sum(r)

for i in range(q):
  print(ans[i])
Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappush,heappop,heapify

pl = []
pr = []

def f(p):
  res = 0
  s = len(p)
  for i in range(s):
    if p[i][0] > s:
      p[i][0] = -s
    else:
      p[i][0] *= -1
  heapify(p)
  hq = []
  for i in range(s,0,-1):
    #print('p:',p,'i:',i)
    while(len(p) > 0 and p[0][0] == -i):
      a,b = heappop(p)
      heappush(hq,-b)
    #print('hq:',hq)
    if len(hq) > 0:
      b = heappop(hq)
      #print('b:',b)
      res -= b
  return res

def solve():
  ans = 0
  n = int(input())
  for i in range(n):
    k,l,r = map(int,input().split())
    m = min(l,r)
    l -= m
    r -= m
    ans += m
    if l > 0:
      pl.append([k,l])
    else:
      pr.append([n-k,r])
  #print('pl:',pl,'pr:',pr,'ans:',ans)
  ans += f(pl)
  ans += f(pr)
  print(ans)

t = int(input())
for i in range(t):
  solve()

Fixed submission:
from heapq import heappush,heappop,heapify

def f(p):
  res = 0
  s = len(p)
  for i in range(s):
    if p[i][0] > s:
      p[i][0] = s
  p.sort(reverse = True)
  hq = []
  idx = 0
  for i in range(s,0,-1):
    #print('p:',p,'i:',i)
    while(idx < s and p[idx][0] == i):
      heappush(hq,-p[idx][1])
      idx += 1
    #print('hq:',hq)
    if len(hq) > 0:
      res -= heappop(hq)
      #print('res:',res)
  return res

def solve():
  n = int(input())
  pl = []
  pr = []
  ans = 0
  for i in range(n):
    k,l,r = map(int,input().split())
    m = min(l,r)
    l -= m
    r -= m
    ans += m
    if l > 0:
      pl.append([k,l])
    else:
      pr.append([n-k,r])
  #print('pl:',pl,'pr:',pr,'ans:',ans)
  ans += f(pl)
  ans += f(pr)
  print(ans)

t = int(input())
for i in range(t):
  solve()
Buggy python submission (verdict: Time Limit Exceeded):
k = int(input())
s = input()
MOD = 10**9+7

FAC = [1]
INV = [1]
for i in range(1,len(s)+k+1):
  FAC.append((FAC[i-1]*i) % MOD)
  INV.append(pow(FAC[-1],MOD-2,MOD))

def nCr(n,r):
  return FAC[n]*INV[n-r]*INV[r]

ans = 0
for i in range(len(s),len(s)+k+1):
  tmp = nCr(i-1,len(s)-1)*pow(25,i-len(s),MOD)
  tmp %= MOD
  tmp *= pow(26,len(s)+k-i,MOD)
  tmp %= MOD
  ans +=tmp
  ans %= MOD
print(ans)

Fixed submission:
k = int(input())
s = input()
MOD = 10**9+7

FAC = [1]
INV = [1]
for i in range(1,len(s)+k+1):
  FAC.append((FAC[i-1]*i) % MOD)
  INV.append(pow(FAC[-1],MOD-2,MOD))

def nCr(n,r):
  return FAC[n]*INV[n-r]*INV[r]

p25 = [1]
for i in range(len(s)+k):
  p25.append((p25[-1]*25)%MOD)
p26 = [1]
for i in range(len(s)+k):
  p26.append((p26[-1]*26)%MOD)

ans = 0
for i in range(len(s),len(s)+k+1):
  tmp = nCr(i-1,len(s)-1)*p25[i-len(s)]
  tmp %= MOD
  tmp *= p26[len(s)+k-i]
  tmp %= MOD
  ans +=tmp
  ans %= MOD
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
k = int(input())
s = input()
MOD = 10**9+7

FAC = [1]
INV = [1]
for i in range(1,len(s)+k+1):
  FAC.append((FAC[i-1]*i) % MOD)
  INV.append(pow(FAC[-1],MOD-2,MOD))

def nCr(n,r):
  return FAC[n]*INV[n-r]*INV[r]

ans = 0
for i in range(len(s),len(s)+k+1):
  ans += nCr(i-1,len(s)-1)*pow(25,i-len(s),MOD)*pow(26,len(s)+k-i,MOD)
  ans %= MOD
print(ans)

Fixed submission:
k = int(input())
s = input()
MOD = 10**9+7

FAC = [1]
INV = [1]
for i in range(1,len(s)+k+1):
  FAC.append((FAC[i-1]*i) % MOD)
  INV.append(pow(FAC[-1],MOD-2,MOD))

def nCr(n,r):
  return FAC[n]*INV[n-r]*INV[r]

p25 = [1]
for i in range(len(s)+k):
  p25.append((p25[-1]*25)%MOD)
p26 = [1]
for i in range(len(s)+k):
  p26.append((p26[-1]*26)%MOD)

ans = 0
for i in range(len(s),len(s)+k+1):
  tmp = nCr(i-1,len(s)-1)*p25[i-len(s)]
  tmp %= MOD
  tmp *= p26[len(s)+k-i]
  tmp %= MOD
  ans +=tmp
  ans %= MOD
print(ans)
Buggy python submission (verdict: Runtime Error):
def main():
  import sys
  input = sys.stdin.readline
  
  n = int(input())
  s = [[],[]]
  for i in range(2):
    s[i] = tuple(map(int,input().split()))
  u = [[],[]]
  for i in range(2):
    u[i] = tuple(map(int,input().split()))
  
  val = [[0 for _ in range(n)] for _ in range(2)]
  d = [[0 for _ in range(n)] for _ in range(n)]
  ans = [[0 for _ in range(n)] for _ in range(n)]
  
  def flip():
    for i in range(n):
      for j in range(i,n):
        d[i][j],d[j][i] = d[j][i],d[i][j]
    
  def solve():
    for i in range(n):
      for j in range(n):
        d[i][j] = -1
    for k in range(1):
      for i in range(n):
        if s[k][i] != val[k][i]:
          for j in range(n):
            if d[i][j] != -1 and d[i][j] != val[k][i]:
              return False
            d[i][j] = val[k][i]
      flip()
    #print(d)
    for l in range(2):
      for k in range(2):
        for i in range(n):
          if s[k][i] == val[k][i]:
            p = []
            ok = False
            for j in range(n):
              if d[i][j] == val[k][i]:
                ok = True
              if d[i][j] == -1:
                p.append(j)
            if ok:
              continue
            if len(p) == 0:
              return False
            elif len(p) == 1:
              d[i][p[0]] = val[k][i]
        flip()
    #print(d)
    start = 0
    for i in range(n):
      num = start
      flag = False
      for j in range(n):
        if d[i][j] == -1:
          flag = True
          d[i][j] = num
          num ^= 1
      if flag:
        start ^= 1
    return True
  
  for b in range(64):
    for i in range(2):
      for j in range(n):
        val[i][j] = (u[i][j]>>b)&1
    if solve():
      for i in range(n):
        for j in range(n):
          ans[i][j] |= d[i][j]<<b
    else:
      print(-1)
      exit()
  
  for i in range(n):
    print(*ans[i])

main()


Fixed submission:
from heapq import heappop, heappush

n,m,s = map(int,input().split())
e = [[] for _ in range(n)]
for i in range(m):
  u,v,a,b = map(int,input().split())
  u -= 1
  v -= 1
  e[u].append((v,a,b))
  e[v].append((u,a,b))
c = []
d = []
for i in range(n):
  x,y = map(int,input().split())
  c.append(x)
  d.append(y)

INF = float('inf')
def dijkstra(s,n,g): # sからの最短距離 頂点数n g[v]=[(u1,w1),(u2,w2)....]:vからuへの有向辺があり、重みw
  que = []
  d = [INF for _ in range(n)]
  d[s] = 0
  heappush(que,(0,s))
  while len(que) > 0:
    p = heappop(que)
    v = p[1]
    if d[v] < p[0]:
      continue
    for u,w in g[v]:
      if d[u] > d[v]+w:
        d[u] = d[v]+w
        heappush(que,(d[u],u))
  return d

def newv(v,s):
  return v*2500+s

s = min(s,2499)
e2 = [[] for _ in range(n*2500)]
for u in range(n):
  for j in range(2500):
    #if j+c[u] < 2500:
    #  e2[newv(u,j)].append((newv(u,j+c[u]),d[u]))
    e2[newv(u,j)].append((newv(u,min(j+c[u],2499)),d[u]))
    for v,a,b in e[u]:
      if j >= a:
        e2[newv(u,j)].append((newv(v,j-a),b))

l = dijkstra(newv(0,s),n*2500,e2)
for i in range(1,n):
  ans = INF
  for j in range(2500):
    ans = min(l[newv(i,j)],ans)
  print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10 ** 9)

n = int(input())
a = list(map(int,input().split()))

b = []
for i in range(n):
  b.append((a[i],i))
b.sort(reverse = True)

ans = 0
def f(l,r,i,h):
  global ans
  if i == n:
    ans = max(ans,h)
    return
  x = b[i][0]
  y = b[i][1]
  f(l+1,r,i+1,h+x*abs(y-l))
  f(l,r-1,i+1,h+x*abs(y-r))

f(0,n-1,0,0)
print(ans)

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

b = []
for i in range(n):
  b.append((a[i],i))
b.sort(reverse = True)

dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
for i in range(n):
  x = b[i][0]
  y = b[i][1]
  for l in range(i+1):
    r = i-l
    dp[i+1][l+1] = max(dp[i+1][l+1],dp[i][l]+x*(y-l))
    dp[i+1][l] = max(dp[i+1][l],dp[i][l]+x*(n-1-r-y))

ans = 0
for i in range(n+1):
  ans = max(dp[n][i],ans)
print(ans)
#print(dp)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s = input()
r = []
g = []
b = []
for i in range(n):
  if s[i] == 'R':
    r.append(i)
  elif s[i] == 'G':
    g.append(i)
  else:
    b.append(i)
ans = 0
for ri in r:
  for gi in g:
    for bi in b:
      a = [ri,gi,bi]
      a.sort()
      if a[1]-a[0] != a[2]-a[1]:
        ans += 1
print(ans)

Fixed submission:
import bisect

n = int(input())
s = input()
rgb = [[],[],[]]
for i in range(n):
  if s[i] == 'R':
    rgb[0].append(i)
  elif s[i] == 'G':
    rgb[1].append(i)
  else:
    rgb[2].append(i)
x = []
for i in range(3):
  x.append((len(rgb[i]),i))
x.sort()
y = []
for i in range(3):
  y.append(rgb[x[i][1]])
a = 0
for y0 in y[0]:
  for y1 in y[1]:
    b = (y0+y1)//2
    if abs(b-y0) == abs(b-y1):
      r = bisect.bisect_left(y[2],b)
      if r < len(y[2]) and y[2][r] == b:
        a += 1
    b = min(y0,y1)-abs(y0-y1)
    if b >= 0:
      r = bisect.bisect_left(y[2],b)
      if r < len(y[2]) and y[2][r] == b:
        a += 1
    b = max(y0,y1)+abs(y0-y1)
    if b < n:
      r = bisect.bisect_left(y[2],b)
      if r < len(y[2]) and y[2][r] == b:
        a += 1
print(len(y[0])*len(y[1])*len(y[2])-a)
Buggy python submission (verdict: Time Limit Exceeded):
def main():
  H,W,K = map(int,input().split())
  S = [[] for _ in range(H)]
  for i in range(H):
    for s in input():
      S[i].append(int(s))
  #print(S)
  
  ans = 10000
  for i in range(2**(H-1)):
    th = bin(i).count('1')
    ans0 = th
    T = [[0 for _ in range(W)] for _ in range(th+1)]
    ti = 0
    for j in range(H):
      for k in range(W):
        T[ti][k] += S[j][k]
      if (i>>j)&1 == 1:
        ti += 1
    #print(th,T)
    tw = 0
    #for k in range(W):
    k = 0
    while(k < W):
      f = True
      #print(tw)
      for j in range(th+1):
        if sum(T[j][tw:k+1]) > K:
          f = False
        #print(sum(T[j][tw:k+1]),f,tw,k)
      if not f:
        if tw == k:
          ans0 = 10000
          break
        else:
          tw = k
          k -= 1
          ans0 += 1
      k += 1
    ans = min(ans0,ans)
  print(ans)

main()

Fixed submission:
def main():
  H,W,K = map(int,input().split())
  S = [[] for _ in range(H)]
  for i in range(H):
    for s in input():
      S[i].append(int(s))
  #print(S)
  
  ans = 10000
  for i in range(2**(H-1)):
    # 横方向の割り方を全検索する。
    # T:横方向の割り方を固定したときに、同じブロック内のホワイトチョコの個数を縦方向に集約した配列。
    th = bin(i).count('1')
    T = [[0 for _ in range(W)] for _ in range(th+1)]
    ti = 0
    for j in range(H):
      for k in range(W):
        T[ti][k] += S[j][k]
      if (i>>j)&1 == 1:
        ti += 1
    #print(th,T)

    # 縦方向の1列分の中に、Kより大きい個数のホワイトチョコが含まれる場合は
    # どのように割っても条件を満たさないのでスキップする。
    f = True
    for k in range(W):
      for j in range(th+1):
        if T[j][k] > K:
          f = False
    if not f:
      continue

    # 横方向に順にホワイトチョコの数を数えていき、Kを超える場合は割る回数ans0を+1する。
    ans0 = th
    T0 = [0 for _ in range(th+1)]
    for k in range(W):
      f = True
      for j in range(th+1):
        T0[j] += T[j][k]
        if T0[j] > K:
          f = False
      if not f:
        ans0 += 1
        # 割った場合は、カウントしていたホワイトチョコの数をカレントの1列分に戻す。
        for j in range(th+1):
          T0[j] = T[j][k]
    ans = min(ans0,ans)
  print(ans)

main()
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
Q = int(input())
r = False
for i in range(Q):
  q = list(input().split())
  if q[0] == '1':
    if r:
      r = False
    else:
      r = True
  else:
    if (q[1] == '1' and not r) or (q[1] == '2' and r):
      S = q[2]+S
    else:
      S = S+q[2]
print(''.join(list(reversed(S))) if r else S)


Fixed submission:
S = input()
Q = int(input())
r = False
F = []
B = []
for i in range(Q):
  q = list(input().split())
  if q[0] == '1':
    if r:
      r = False
    else:
      r = True
  else:
    if (q[1] == '1' and not r) or (q[1] == '2' and r):
      F.append(q[2])
    else:
      B.append(q[2])

if r:
  print(''.join(B[::-1]+list(reversed(S))+F))
else:
  print(''.join(F[::-1]+list(S)+B))
Buggy python submission (verdict: Time Limit Exceeded):
N,M,K = map(int,input().split())
d = [[float('inf') for _ in range(N)] for _ in range(N)]
for i in range(M):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  d[a][b] = 1
  d[b][a] = 1
for i in range(N):
  d[i][i] = 0
for k in range(N):
  for i in range(N):
    for j in range(N):
      d[i][j] = min(d[i][j],d[i][k]+d[k][j])
for i in range(K):
  c,e = map(int,input().split())
  c -= 1
  e -= 1
  d[c][e] = float('inf')
  d[e][c] = float('inf')
ans =[]
for i in range(N):
  cnt = 0
  for j in range(N):
    if i != j and d[i][j] > 1 and d[i][j] != float('inf'):
      cnt += 1
  ans.append(cnt)
print(*ans)

                                      


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

N,M,K = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(M)]
CD = [list(map(int,input().split())) for _ in range(K)]

V = [[] for _ in range(N)]
for a,b in AB:
  a -= 1
  b -= 1
  V[a].append(b)
  V[b].append(a)
# print(V)

L = [0 for _ in range(N)]
def dfs(u,l):
  L[u] = l
  for t in V[u]:
    if L[t] == 0:
      dfs(t,l)

l = 1
for i in range(N):
  if L[i] == 0:
    dfs(i,l)
    l += 1
#print(L)
C = {}
for ll in L:
  if ll in C:
    C[ll] += 1
  else:
    C[ll] = 1
#print(C)
ans = [C[L[i]]-1 for i in range(N)]
for a,b in AB:
  a -= 1
  b -= 1
  ans[a] -= 1
  ans[b] -= 1
for c,d in CD:
  c -= 1
  d -= 1
  if L[c] == L[d]:
    ans[c] -= 1
    ans[d] -= 1
print(*ans)
Buggy python submission (verdict: Time Limit Exceeded):
N,K = map(int,input().split())
P = list(map(int,input().split()))

E = []
for p in P:
  E.append((p+1)*p/2/p)
mx = 0
for i in range(N-K+1):
  mx = max(sum(E[i:i+K]),mx)
print(mx)


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

E = []
for p in P:
  E.append((p+1)*p/2/p)
csum = [0]
for i in range(N):
  csum.append(csum[-1]+E[i])
mx = 0
for i in range(N-K+1):
  mx = max(csum[K+i]-csum[i],mx)
print(mx)
Buggy python submission (verdict: Time Limit Exceeded):
def main():
  import sys
  input = sys.stdin.readline
  
  N = int(input())
  E = [[] for _ in range(N)]
  for i in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    E[a].append((b,i))
    E[b].append((a,i))
  
  EG = []
  def dfs(u,v,p):
    if u == v:
      return True
    for t,i in E[u]:
      if t == p:
        continue
      if dfs(t,v,u):
        EG.append(i)
        return True
    return False
  
  M = int(input())
  EM = []
  for i in range(M):
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    EM.append((u,v))
  
  ans = 0
  for i in range(1<<M):
    EG2 = []
    bc = 0
    for j in range(M):
      if (i>>j)&1 == 1:
        bc += 1
        u,v = EM[j]
        EG = []
        dfs(u,v,-1)
        EG2 += EG
    p = len(set(EG2))
    if bc%2 == 0:
      ans += 2**(N-1-p)
    else:
      ans -= 2**(N-1-p)
  print(ans)

if __name__ == '__main__':
  main()


Fixed submission:
def main():
  import sys
  input = sys.stdin.readline
  
  N = int(input())
  E = [[] for _ in range(N)]
  for i in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    E[a].append((b,i))
    E[b].append((a,i))
  
  EG = []
  def dfs(u,v,p):
    if u == v:
      return True
    for t,i in E[u]:
      if t == p:
        continue
      if dfs(t,v,u):
        EG.append(i)
        return True
    return False
  
  M = int(input())
  EM = []
  for i in range(M):
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    EM.append((u,v))
  
  ES = []
  for i in range(M):
    u,v = EM[i]
    EG = []
    dfs(u,v,-1)
    ES.append((u,v,EG))
  
  ans = 0
  for i in range(1<<M):
    EG2 = []
    bc = 0
    for j in range(M):
      if (i>>j)&1 == 1:
        bc += 1
        EG2 += ES[j][2]
    p = len(set(EG2))
    if bc%2 == 0:
      ans += 2**(N-1-p)
    else:
      ans -= 2**(N-1-p)
  print(ans)

if __name__ == '__main__':
  main()
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
# M:カードの数字の最大値+1
M = max(max(A),max(B))+1

INF = float('inf')
# dp[mask][a]:maskのカードが操作済で、そのうち右端のカードの数字がaであるときの操作回数の最小値
dp = [[INF for _ in range(M)] for _ in range(1<<N)]
dp[0][0] = 0

for i in range(1<<N):
  # idx:操作済カードの枚数
  idx = 0
  for k in range(N):
    if (i>>k)&1 == 1:
      idx += 1
  for j in range(M):
    if dp[i][j] >= INF:
      continue
    for k in range(N):
      # k:右端の操作済カードの次に来るカード
      # kがすでに操作済の場合はcontinueする
      if i&(1<<k) == 1:
        continue
      
      # kが何回操作されるかによってkの数字が表の数字になるか裏の数字になるかが決まる
      if abs(k-idx)%2 == 0:
        c = A[k]
      else:
        c = B[k]

      # kの数字広義単調増加にならない場合はcontinue
      if j > c:
        continue
      
      # t:kを右端の操作済カードの次に並べるための操作回数
      # それは、初期配置でkより左にあってまだ操作済でないカードの枚数と一致する
      t = 0
      for l in range(k):
        if (i>>l)&1 == 0:
          t += 1
      #print(i,k,idx,c,dp[i|(1<<k)][c],t)
      dp[i|(1<<k)][c] = min(dp[i|(1<<k)][c],dp[i][j]+t)

#print(dp)
ans = INF
for i in range(M):
  ans = min(dp[(1<<N)-1][i],ans)
print(ans if ans < INF else -1)

Fixed submission:
def main():
  N = int(input())
  A = list(map(int,input().split()))
  B = list(map(int,input().split()))
  # M:カードの数字の最大値+1
  M = max(max(A),max(B))+1
  
  INF = float('inf')
  # dp[mask][a]:maskのカードが操作済で、そのうち右端のカードの数字がaであるときの操作回数の最小値
  dp = [[INF for _ in range(M)] for _ in range(1<<N)]
  dp[0][0] = 0
  
  for i in range(1<<N):
    # idx:操作済カードの枚数
    idx = 0
    for k in range(N):
      if (i>>k)&1 == 1:
        idx += 1
    for j in range(M):
      if dp[i][j] >= INF:
        continue
      for k in range(N):
        # k:右端の操作済カードの次に来るカード
        # kがすでに操作済の場合はcontinueする
        if i&(1<<k) == 1:
          continue
        
        # kが何回操作されるかによってkの数字が表の数字になるか裏の数字になるかが決まる
        if abs(k-idx)%2 == 0:
          c = A[k]
        else:
          c = B[k]
  
        # kの数字広義単調増加にならない場合はcontinue
        if j > c:
          continue
        
        # t:kを右端の操作済カードの次に並べるための操作回数
        # それは、初期配置でkより左にあってまだ操作済でないカードの枚数と一致する
        t = 0
        for l in range(k):
          if (i>>l)&1 == 0:
            t += 1
        #print(i,k,idx,c,dp[i|(1<<k)][c],t)
        dp[i|(1<<k)][c] = min(dp[i|(1<<k)][c],dp[i][j]+t)
  
  #print(dp)
  ans = INF
  for i in range(M):
    ans = min(dp[(1<<N)-1][i],ans)
  print(ans if ans < INF else -1)

if __name__ == '__main__':
  main()
Buggy python submission (verdict: Time Limit Exceeded):
H,W = map(int,input().split())
S = [list(input()) for _ in range(H)]
#print(S)
idx = 0
for i in range(H):
  for j in range(W):
    if S[i][j] == '.':
      S[i][j] = idx
      idx += 1
#print(S)
D = [[float('inf') for _ in range(idx)] for _ in range(idx)]
for i in range(H):
  for j in range(W):
    if S[i][j] == '#':
      continue
    for dy,dx in [(-1,0),(1,0),(0,-1),(0,1)]:
      if 0 <= i+dy < H and 0 <= j+dx < W and S[i+dy][j+dx] != '#':
        D[S[i][j]][S[i+dy][j+dx]] = 1
        D[S[i+dy][j+dx]][S[i][j]] = 1
for i in range(idx):
  D[i][i] = 0

for k in range(idx):
  for i in range(idx):
    for j in range(idx):
      D[i][j] = min(D[i][k]+D[k][j],D[i][j])
#print(D)
ans = 0
for d in D:
  ans = max(max(d),ans)
print(ans)

Fixed submission:
def main():
  import sys
  input = sys.stdin.readline
  
  H,W = map(int,input().split())
  S = [list(input()) for _ in range(H)]
  #print(S)
  idx = 0
  for i in range(H):
    for j in range(W):
      if S[i][j] == '.':
        S[i][j] = idx
        idx += 1
  #print(S)
  D = [[float('inf') for _ in range(idx)] for _ in range(idx)]
  for i in range(H):
    for j in range(W):
      if S[i][j] == '#':
        continue
      for dy,dx in [(-1,0),(1,0),(0,-1),(0,1)]:
        if 0 <= i+dy < H and 0 <= j+dx < W and S[i+dy][j+dx] != '#':
          D[S[i][j]][S[i+dy][j+dx]] = 1
          D[S[i+dy][j+dx]][S[i][j]] = 1
  for i in range(idx):
    D[i][i] = 0
  
  for k in range(idx):
    for i in range(idx):
      for j in range(idx):
        D[i][j] = min(D[i][k]+D[k][j],D[i][j])
  #print(D)
  ans = 0
  for d in D:
    ans = max(max(d),ans)
  print(ans)

if __name__ == '__main__':
  main()