Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
S = input()
cnt = 1
counts = []

if S[0]=='0':
  counts.append(0)
if N == 1:
  counts.append(1)
  
for i in range(1,N):
  if S[i-1]!=S[i]:
    counts.append(cnt)
    cnt = 1
  else:
    cnt += 1
  #print(i)
  if i == N-1:
    counts.append(cnt)

#print(counts)
m = 0
K = min(K,len(counts)//2)
for i in range(len(counts)//2-K+1):
  m = max(m,sum(counts[2*i:2*(i+K)+1]))
print(m)

Fixed submission:
N, K = map(int, input().split())
S = input()
cnt = 1
counts = []

if S[0]=='0':
  counts.append(0)
if N == 1:
  counts.append(1)
  
for i in range(1,N):
  if S[i-1]!=S[i]:
    counts.append(cnt)
    cnt = 1
  else:
    cnt += 1
  #print(i)
  if i == N-1:
    counts.append(cnt)

#print(counts)
K = min(K,len(counts)//2)
for i in range(len(counts)//2-K+1):
  if i == 0:
    s = sum(counts[:2*K+1])
    m = s
  else:
    s += sum(counts[2*(i+K)-1:2*(i+K)+1])-sum(counts[2*i-2:2*i])
    m = max(m,s)
  #print(s)
print(m)
Buggy python submission (verdict: Runtime Error):
#UnionFind木
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * n

  def find(self, x):
    if self.parents[x] < 0:
      return x
    else:
      self.parents[x] = self.find(self.parents[x])
      return self.parents[x]

  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)

    if x == y:
      return

    if self.parents[x] > self.parents[y]:
            x, y = y, x

    self.parents[x] += self.parents[y]
    self.parents[y] = x

  def same(self, x, y):
        return self.find(x) == self.find(y)

  def roots(self):
    return [i for i, x in enumerate(self.parents) if x < 0]

  def members(self, x):
    root = self.find(x)
    return [i for i in range(self.n) if self.find(i) == root]

  def __str__(self):
    return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N, M = map(int, input().split())

A = [0]*M
B = [0]*M
for i in range(M):
  A[i],B[i] = map(int, input().split())
  A[i] -= 1
  B[i] -= 1

ans = []

A = A[::-1]
B = B[::-1]
uf = UnionFind(N)
total = N*(N-1)//2
ans.append(total)
for i in range(M):
  if uf.same(A[i],B[i]):
    ans.append(total)
    continue
  m = abs(uf.parents[uf.find(A[i])])
  n = abs(uf.parents[uf.find(B[i])])
  #print(uf)
  #print(A[i]+1,m,B[i]+1,n)
  uf.union(A[i],B[i])
  total -= m*n
  ans.append(total)
  
#print(ans)   

print(*ans[:-1][::-1], sep='\n')


Fixed submission:
A, B, C = map(int, input().split())
print(min(B//A,C))

Buggy python submission (verdict: Runtime Error):
#UnionFind木
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * n

  def find(self, x):
    if self.parents[x] < 0:
      return x
    else:
      self.parents[x] = self.find(self.parents[x])
      return self.parents[x]

  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)

    if x == y:
      return

    if self.parents[x] > self.parents[y]:
            x, y = y, x

    self.parents[x] += self.parents[y]
    self.parents[y] = x

  def same(self, x, y):
        return self.find(x) == self.find(y)

  def roots(self):
    return [i for i, x in enumerate(self.parents) if x < 0]

  def members(self, x):
    root = self.find(x)
    return [i for i in range(self.n) if self.find(i) == root]

  def __str__(self):
    return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N, M = map(int, input().split())

A = [0]*M
B = [0]*M
for i in range(M):
  A[i],B[i] = map(int, input().split())
  A[i] -= 1
  B[i] -= 1

ans = []

A = A[::-1]
B = B[::-1]
uf = UnionFind(N)
total = N*(N-1)//2
ans.append(total)
for i in range(M):
  if uf.same(A[i],B[i]):
    ans.append(total)
    continue
  m = len(uf.members(A[i]))
  n = len(uf.members(B[i]))
  uf.union(A[i],B[i])
  total -= m*n
  ans.append(total)
  
#print(ans)   

print(*ans[:-1][::-1], sep='\n')


Fixed submission:
A, B, C = map(int, input().split())
print(min(B//A,C))
Buggy python submission (verdict: Time Limit Exceeded):
H, W = map(int, input().split())
S = [0]*(H+2)
S[0] = '*'*(W+2)
S[H+1] = '*'*(W+2)
for h in range(1,H+1):
  S[h] = '*' + input() + '*'

import sys
sys.setrecursionlimit(10**8)

bw = ['#','.']

visited = [[False]*(W+2) for h in range(H+2)]
ans = 0
dh = [0,1,0,-1]
dw = [1,0,-1,0]

def dfs(h,w,c):
  #print(h,w,c, bw_count)
  for i in range(4):
    h0 = h+dh[i]
    w0 = w+dw[i]
    if S[h0][w0]==bw[c^1] and visited[h0][w0]==False:
      visited[h0][w0]=True
      bw_count[c^1]+=1
      dfs(h0,w0,c^1)
  
for h in range(H+2):
  for w in range(W+2):
    if S[h][w]=='#' and visited[h][w]==False:
      bw_count = [1,0]
      visited[h][w]=True
      dfs(h,w,0)
      ans += bw_count[0]*bw_count[1]

print(ans)   

#print(*ans, sep='\n')


Fixed submission:
H, W = map(int, input().split())
S = [0]*(H+2)
S[0] = '*'*(W+2)
S[H+1] = '*'*(W+2)
for h in range(1,H+1):
  S[h] = '*' + input() + '*'

import sys
sys.setrecursionlimit(10**8)

bw = ['#','.']

visited = [[False]*(W+2) for h in range(H+2)]
ans = 0
dh = [0,1,0,-1]
dw = [1,0,-1,0]

def dfs(h,w,c):
  #print(h,w,c, bw_count)
  for i in range(4):
    h0 = h+dh[i]
    w0 = w+dw[i]
    if S[h0][w0]==bw[c^1] and visited[h0][w0]==False:
      visited[h0][w0]=True
      bw_count[c^1]+=1
      dfs(h0,w0,c^1)
  
for h in range(H+2):
  for w in range(W+2):
    if S[h][w]=='#' and visited[h][w]==False:
      bw_count = [1,0]
      visited[h][w]=True
      dfs(h,w,0)
      ans += bw_count[0]*bw_count[1]

print(ans)   

#print(*ans, sep='\n')
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
H = list(map(int, input().split()))
H = [H[0]]*K+H
def solve(H):
    dp = [0]*(N+K)
    for i in range(K,N+K):
        dp[i]= 10**10
        for j in range(1,K+1):
            dp[i] = min(dp[i],dp[i-j]+abs(H[i]-H[i-j]))
    ans = dp[-1]
    return ans
print(solve(H))

Fixed submission:
N, K = map(int, input().split())
H = list(map(int, input().split()))
H = [H[0]]*K+H
def solve(H):
    dp = [0]*(N+K)
    for i in range(K,N+K):
        dp[i]= 10**10
        for j in range(1,K+1):
            dp[i] = min(dp[i],dp[i-j]+abs(H[i]-H[i-j]))
    ans = dp[-1]
    return ans
print(solve(H))
Buggy python submission (verdict: Time Limit Exceeded):
N, W = map(int, input().split())
w = [0]*N
v = [0]*N
for i in range(N):
    w[i],v[i] = map(int, input().split())

def solve(w,v):
    dp = [[0]*(W+1) for i in range(N+1)]
    for i in range(1,N+1):
        for j in range(W+1):
            if j < w[i-1]:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1])
    ans = dp[-1][-1]
    return ans
print(solve(w,v))

Fixed submission:
N, W = map(int, input().split())
w = [0]*N
v = [0]*N
for i in range(N):
    w[i],v[i] = map(int, input().split())

def solve(w,v):
    dp = [[0]*(W+1) for i in range(N+1)]
    for i in range(1,N+1):
        for j in range(W+1):
            if j < w[i-1]:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1])
    ans = dp[-1][-1]
    return ans
print(solve(w,v))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
P = list(map(float, input().split()))


def solve():
    dp = [[0]*(i+3) for i in range(N+1)]
    dp[0][1] = 1
    for i in range(1,N+1):
        for j in range(1,i+2):
            dp[i][j] = dp[i-1][j-1]*P[i-1]+dp[i-1][j]*(1-P[i-1])
    ans = sum(dp[-1][(N+3)//2:])
    return ans
print(solve())

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


def solve():
    dp = [[0]*(N+1) for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(1,N+1):
        dp[i][0] = dp[i-1][0]*(1-P[i-1])
    for i in range(1,N+1):
        for j in range(1,i+1):
            dp[i][j] = dp[i-1][j-1]*P[i-1]+dp[i-1][j]*(1-P[i-1])
    ans = sum(dp[-1][(N+2)//2:])
    return ans
print(solve())

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
P = list(map(float, input().split()))


def solve():
    dp = [[0]*(N+1) for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(1,N+1):
        dp[i][0] = dp[i-1][0]*(1-P[i-1])
    for i in range(1,N+1):
        for j in range(1,i+1):
            dp[i][j] = dp[i-1][j-1]*P[i-1]+dp[i-1][j]*(1-P[i-1])
    ans = sum(dp[-1][(N+2)//2:])
    return ans
print(solve())

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


def solve():
    dp = [[0]*(N+1) for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(1,N+1):
        dp[i][0] = dp[i-1][0]*(1-P[i-1])
    for i in range(1,N+1):
        for j in range(1,i+1):
            dp[i][j] = dp[i-1][j-1]*P[i-1]+dp[i-1][j]*(1-P[i-1])
    ans = sum(dp[-1][(N+2)//2:])
    return ans
print(solve())
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**8)
def calc(N,i,j,k):
  if dp[i][j][k]>=0:
    return dp[i][j][k]
  ans = 1
  if k-1>=0 and j+1<=N:
    ans += calc(N,i,j+1,k-1)*k/N
  if j-1>=0 and i+1<=N:
    ans += calc(N,i+1,j-1,k)*j/N
  if i-1>=0:
    ans += calc(N,i-1,j,k)*i/N
  if i+j+k>0:
    ans *= N/(i+j+k)
  dp[i][j][k] = ans
  return ans

N = int(input())
A = list(map(int, input().split()))
one = A.count(1)
two = A.count(2)
three = A.count(3)
dp = [[[-1]*(N+1) for _ in range(N+1)] for _ in range(N+1)]
dp[0][0][0] = 0
ans = calc(N,one,two,three)
print(ans)

Fixed submission:
N = int(input())
A = list(map(float, input().split()))
def solve():
    dp = [[[0]*(N+1-i-j) for j in range(N+1-i)] for i in range(N+1)]
    dp[N][0][0] = 0
    for i in range(N-1,-1,-1):
        for j in range(N-i,-1,-1):
            for k in range(N-i-j,-1,-1):
                dp[i][j][k] = 1/(1-i/N)
                if j != 0:
                    dp[i][j][k] += dp[i+1][j-1][k]*(j/(N-i))
                if k != 0:
                    dp[i][j][k] += dp[i][j+1][k-1]*(k/(N-i))
                if i+j+k != N:
                    dp[i][j][k] += dp[i][j][k+1]*(1-(j+k)/(N-i))
    c = {}
    for i in range(1,3):
        c[i] = A.count(i)
    ans = dp[0][c[1]][c[2]]
    # print(*dp,sep='\n')
    return ans
print(solve())

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(float, input().split()))
def solve():
    dp = [[[0]*(N+1-i-j) for j in range(N+1-i)] for i in range(N+1)]
    dp[N][0][0] = 0
    for i in range(N-1,-1,-1):
        for j in range(N-i,-1,-1):
            for k in range(N-i-j,-1,-1):
                dp[i][j][k] = 1/(1-i/N)
                if j != 0:
                    dp[i][j][k] += dp[i+1][j-1][k]*(j/(N-i))
                if k != 0:
                    dp[i][j][k] += dp[i][j+1][k-1]*(k/(N-i))
                if i+j+k != N:
                    dp[i][j][k] += dp[i][j][k+1]*(1-(j+k)/(N-i))
    c = {}
    for i in range(1,3):
        c[i] = A.count(i)
    ans = dp[0][c[1]][c[2]]
    # print(*dp,sep='\n')
    return ans
print(solve())

Fixed submission:
N = int(input())
A = list(map(float, input().split()))
def solve():
    dp = [[[0]*(N+1-i-j) for j in range(N+1-i)] for i in range(N+1)]
    dp[N][0][0] = 0
    for i in range(N-1,-1,-1):
        for j in range(N-i,-1,-1):
            for k in range(N-i-j,-1,-1):
                dp[i][j][k] = 1/(1-i/N)
                if j != 0:
                    dp[i][j][k] += dp[i+1][j-1][k]*(j/(N-i))
                if k != 0:
                    dp[i][j][k] += dp[i][j+1][k-1]*(k/(N-i))
                if i+j+k != N:
                    dp[i][j][k] += dp[i][j][k+1]*(1-(j+k)/(N-i))
    c = {}
    for i in range(1,3):
        c[i] = A.count(i)
    ans = dp[0][c[1]][c[2]]
    # print(*dp,sep='\n')
    return ans
print(solve())
Buggy python submission (verdict: Runtime Error):
def solve():
  N, K = map(int, input().split())
  A = list(map(int, input().split()))
  dp = ['Second']*(K*2)
  for i in range(K):
    if dp[i]!='Second':
      continue
    for j in range(N):
      dp[i+A[j]]='First'
  ans = dp[K]
  return ans
print(solve())def solve():
  N, K = map(int, input().split())
  A = list(map(int, input().split()))
  dp = ['Second']*(K*2)
  for i in range(K):
    if dp[i]!='Second':
      continue
    for j in range(N):
      dp[i+A[j]]='First'
  ans = dp[K]
  return ans
print(solve())

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

dp = ['First']*(K+1)
dp[0] = 'Second'
def solve(dp):
    for i in range(1,K+1):
        for j in range(N):
            dp[i] = 'Second'
            if dp[i-A[j]]=='Second':
                dp[i] = 'First'
                break
    ans = dp[K]
    return ans
print(solve(dp))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**8)
def calc(N,i,j):
  if dp[i][j]<float('inf'):
    return dp[i][j]
  if (N-(j-i+1))%2==0:
    if i==j:
      dp[i][j] = A[i]
    else:
      dp[i][j] = max(calc(N,i,j-1)+A[j],calc(N,i+1,j)+A[i])
  else:
    if i==j:
      dp[i][j] = -A[i]
    else:
      dp[i][j] = min(calc(N,i,j-1)-A[j],calc(N,i+1,j)-A[i])
  return dp[i][j]

N = int(input())
A = list(map(int, input().split()))
dp = [[float('inf')]*N for _ in range(N)]
ans = calc(N,0,N-1)
print(ans)

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


def solve(N,A):
    s,e = 0, N-1
    dp = [[0]*N for i in range(N)]
    for k in range(N):
        for i in range(N):
            j = i+k
            if j>=N:
                continue
            sign = (-1)**(N-1-k)
            if k==0:
                dp[i][j] = sign*A[i]
                continue
            dp[i][j] = sign*max(sign*dp[i+1][j]+A[i],sign*dp[i][j-1]+A[j])
    ans = dp[0][N-1]
    return ans
print(solve(N,A))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**8)
def calc(N,i,j):
  if dp[i][j]<float('inf'):
    return dp[i][j]
  if (N-(j-i+1))%2==0:
    if i==j:
      dp[i][j] = A[i]
    else:
      dp[i][j] = max(calc(N,i,j-1)+A[j],calc(N,i+1,j)+A[i])
  else:
    if i==j:
      dp[i][j] = -A[i]
    else:
      dp[i][j] = min(calc(N,i,j-1)-A[j],calc(N,i+1,j)-A[i])
  return dp[i][j]

N = int(input())
A = list(map(int, input().split()))
dp = [[float('inf')]*N for _ in range(N)]
ans = calc(N,0,N-1)
print(ans)

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


def solve(N,A):
    s,e = 0, N-1
    dp = [[0]*N for i in range(N)]
    for k in range(N):
        for i in range(N):
            j = i+k
            if j>=N:
                continue
            sign = (-1)**(N-1-k)
            if k==0:
                dp[i][j] = sign*A[i]
                continue
            dp[i][j] = sign*max(sign*dp[i+1][j]+A[i],sign*dp[i][j-1]+A[j])
    ans = dp[0][N-1]
    return ans
print(solve(N,A))

Buggy python submission (verdict: Runtime Error):
def calc(N,i,j):
  if dp[i][j]<float('inf'):
    return dp[i][j]
  if (N-(j-i+1))%2==0:
    if i==j:
      dp[i][j] = A[i]
    else:
      dp[i][j] = max(calc(N,i,j-1)+A[j],calc(N,i+1,j)+A[i])
  else:
    if i==j:
      dp[i][j] = -A[i]
    else:
      dp[i][j] = min(calc(N,i,j-1)-A[j],calc(N,i+1,j)-A[i])
  return dp[i][j]

N = int(input())
A = list(map(int, input().split()))
dp = [[float('inf')]*N for _ in range(N)]
ans = calc(N,0,N-1)
print(ans)

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


def solve(N,A):
    s,e = 0, N-1
    dp = [[0]*N for i in range(N)]
    for k in range(N):
        for i in range(N):
            j = i+k
            if j>=N:
                continue
            sign = (-1)**(N-1-k)
            if k==0:
                dp[i][j] = sign*A[i]
                continue
            dp[i][j] = sign*max(sign*dp[i+1][j]+A[i],sign*dp[i][j-1]+A[j])
    ans = dp[0][N-1]
    return ans
print(solve(N,A))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
edge = [[] for _ in range(N)]
for i in range(N-1):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

import sys
sys.setrecursionlimit(10**8)

mod = 10**9+7
def dfs(v):
    white,black = 1,1
    for u in edge[v]:
        if visited[u]==False:
            visited[u]=True
            w,b = dfs(u)
            white *= w+b
            white %= mod
            black *= w
            black %= mod
    return white,black

visited = [False]*N
visited[0]=True
print(sum(dfs(0))%mod)

Fixed submission:
N = int(input())
edge = [[] for _ in range(N)]
for i in range(N-1):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

import sys
sys.setrecursionlimit(10**8)

mod = 10**9+7
def dfs(v):
    white,black = 1,1
    for u in edge[v]:
        if visited[u]==False:
            visited[u]=True
            w,b = dfs(u)
            white *= w+b
            white %= mod
            black *= w
            black %= mod
    return white,black

visited = [False]*N
visited[0]=True
print(sum(dfs(0))%mod)
Buggy python submission (verdict: Time Limit Exceeded):
def solve():
  N = int(input())
  s = input()
  mod = 10**9+7
  dp = [[0]*N for _ in range(N)]
  dp[-1][0]=1
  for i in range(N-2,-1,-1):
    if s[i]=='>':
      for j in range(N-i-2,-1,-1):
        dp[i][j] = dp[i][j+1]+dp[i+1][j]
        dp[i][j]%mod
    else:
      for j in range(1,N-i):
        dp[i][j] = dp[i][j-1]+dp[i+1][j-1]
        dp[i][j]%mod
  ans = sum(dp[0])%mod
  return ans
print(solve())

Fixed submission:
def solve():
  N = int(input())
  s = input()
  mod = 10**9+7
  dp = [[0]*N for _ in range(N)]
  dp[-1][0]=1
  for i in range(N-2,-1,-1):
    if s[i]=='>':
      for j in range(N-i-2,-1,-1):
        dp[i][j] = dp[i][j+1]+dp[i+1][j]
        dp[i][j] %= mod
    else:
      for j in range(1,N-i):
        dp[i][j] = dp[i][j-1]+dp[i+1][j-1]
        dp[i][j] %= mod
  ans = sum(dp[0])%mod
  return ans
print(solve())

Buggy python submission (verdict: Time Limit Exceeded):
def solve():
  N = int(input())
  s = input()
  mod = 10**9+7
  dp = [[0]*N for _ in range(N)]
  dp[-1][0]=1
  for i in range(N-2,-1,-1):
    if s[i]=='>':
      for j in range(N-i-2,-1,-1):
        dp[i][j] = dp[i][j+1]+dp[i+1][j]
        dp[i][j]%mod
    else:
      for j in range(1,N-i):
        dp[i][j] = dp[i][j-1]+dp[i+1][j-1]
        dp[i][j]%mod
  ans = sum(dp[0])%mod
  return ans
print(solve())

Fixed submission:
def solve():
  N = int(input())
  s = input()
  mod = 10**9+7
  dp = [[0]*N for _ in range(N)]
  dp[-1][0]=1
  for i in range(N-2,-1,-1):
    if s[i]=='>':
      for j in range(N-i-2,-1,-1):
        dp[i][j] = dp[i][j+1]+dp[i+1][j]
        dp[i][j] %= mod
    else:
      for j in range(1,N-i):
        dp[i][j] = dp[i][j-1]+dp[i+1][j-1]
        dp[i][j] %= mod
  ans = sum(dp[0])%mod
  return ans
print(solve())

Buggy python submission (verdict: Time Limit Exceeded):
def solve():
  N = int(input())
  s = input()
  mod = 10**9+7
  dp = [[0]*N for _ in range(N)]
  dp[-1][0]=1
  for i in range(N-2,-1,-1):
    if s[i]=='>':
      dp[i][-1]=0
      for j in range(N-2,-1,-1):
        dp[i][j] = dp[i][j+1]+dp[i+1][j]
        dp[i][j]%mod
    else:
      dp[i][0] = 0
      for j in range(1,N-i):
        dp[i][j] = dp[i][j-1]+dp[i+1][j-1]
        dp[i][j]%mod
  ans = sum(dp[0])%mod
  return ans
print(solve())

Fixed submission:
def solve():
  N = int(input())
  s = input()
  mod = 10**9+7
  dp = [[0]*N for _ in range(N)]
  dp[-1][0]=1
  for i in range(N-2,-1,-1):
    if s[i]=='>':
      for j in range(N-i-2,-1,-1):
        dp[i][j] = dp[i][j+1]+dp[i+1][j]
        dp[i][j] %= mod
    else:
      for j in range(1,N-i):
        dp[i][j] = dp[i][j-1]+dp[i+1][j-1]
        dp[i][j] %= mod
  ans = sum(dp[0])%mod
  return ans
print(solve())
Buggy python submission (verdict: Runtime Error):
from itertools import groupby, accumulate, product, permutations, combinations
def solve():
  N = int(input())
  B = [0]*N
  for i in range(N):
    a,b = input().split()
    a1,a2 = map(int,a.split(':'))
    b1,b2 = map(int,b.split(':'))
    a = a1*60+a2
    b = b1*60+b2
    B[i] = [a,b]
  A = [[0]*N for _ in range(N)]
  for i in range(N):
    for j in range(N):
      if B[i][0]>=B[j][1] and B[i][1]<=B[j][0]+1440:
        A[i][j] = 1
        A[j][i] = 1
  dp = [float('inf')]*(1<<N)
  dp[0] = 0
  for i in range(N):
    dp[1<<i] = 1
  for i in range(2,N+1):
    for com in combinations(range(N),i):
      S = 0
      for c in com:
        S += 1<<c
      last = com[-1]
      dp[S] = dp[S-(1<<last)]
      for c in com[:-1]:
        if A[last][c]==0:
          dp[S] = float('inf')
  for i in range(2,N+1):
    for com in combinations(range(N),i):
      S = sum([1<<c for c in com])
      T = (S-1)&S
      while T>0:
        dp[S] = min(dp[S],dp[T]+dp[S-T])
        T = (T-1)&S
  ans = dp[-1]
  return ans
print(solve())

Fixed submission:
from itertools import groupby, accumulate, product, permutations, combinations
def solve():
  N = int(input())
  A = [list(map(int, input().split())) for _ in range(N)]
  dp = [0]*(1<<N)
  dp[0] = 0
  for i in range(2,N+1):
    for com in combinations(range(N),i):
      S = sum([1<<c for c in com])
      last = com[-1]
      dp[S] = dp[S-(1<<last)]
      for c in com:
        dp[S] += A[last][c]
  for i in range(2,N+1):
    for com in combinations(range(N),i):
      S = sum([1<<c for c in com])
      T = (S-1)&S
      while T>0:
        dp[S] = max(dp[S],dp[T]+dp[S-T])
        T = (T-1)&S
  ans = dp[-1]
  return ans
print(solve())

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import groupby, accumulate, product, permutations, combinations
def solve():
  N = int(input())
  A = [list(map(int, input().split())) for _ in range(N)]
  dp = [0]*(1<<N)
  dp[0] = 0
  for i in range(2,N+1):
    for com in combinations(range(N),i):
      S = 0
      for c in com:
        S += 1<<c
      last = com[-1]
      dp[S] = dp[S-(1<<last)]
      for c in com:
        dp[S] += A[last][c]
  for i in range(2,N+1):
    for com in combinations(range(N),i):
      S = 0
      for c in com:
        S += 1<<c
      for p in product([0,1],repeat=i-1):
        s = 0
        for j in range(i-1):
          if p[j]==1:
            s += 1<<com[j]
        dp[S] = max(dp[S],dp[s]+dp[S-s])
  ans = dp[-1]
  return ans
print(solve())

Fixed submission:
from itertools import groupby, accumulate, product, permutations, combinations
def solve():
  N = int(input())
  A = [list(map(int, input().split())) for _ in range(N)]
  dp = [0]*(1<<N)
  dp[0] = 0
  for i in range(2,N+1):
    for com in combinations(range(N),i):
      S = sum([1<<c for c in com])
      last = com[-1]
      dp[S] = dp[S-(1<<last)]
      for c in com:
        dp[S] += A[last][c]
  for i in range(2,N+1):
    for com in combinations(range(N),i):
      S = sum([1<<c for c in com])
      T = (S-1)&S
      while T>0:
        dp[S] = max(dp[S],dp[T]+dp[S-T])
        T = (T-1)&S
  ans = dp[-1]
  return ans
print(solve())