Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
def lcs(s, t):
    n = len(s)
    m = len(t)
    # dp[i][j] := 0-indexでsのi-1文字目までとtのj-1文字目までとのlcsの長さ
    # dp[0][0]は空文字を見ていると考えるからdp[0][0] = 0
    # dp[n][m] := sのn-1文字目まで（0-indexなのでsの末尾）とtのm-1文字目まで(0-indexなのでtの末尾)
    dp = [[0]*(m+1) for _ in range(n+1)]

    for i in range(n):
        for j in range(m):
            # 0-indexでsのi文字目とtのj文字目が等しいなら斜めに移動する
            if s[i] == t[j]:
                dp[i+1][j+1] = dp[i][j] + 1
            # 異なるなら左または上のmaxをとる
            else:
                dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
    res = ""
    while n != 0 and m != 0:  # どちらかが0になったら終わり，dp[0][*]及びdp[*][0]は必ず0なので
        # 上から遷移している場合，nをデクリメントしてよい
        if dp[n][m] == dp[n-1][m]:
            n -= 1
        # 左から遷移している場合，mをデクリメントしてよい
        elif dp[n][m] == dp[n][m-1]:
            m -= 1
        # 左でも上でもなく，左上からの遷移の場合，共通文字
        else:
            n -= 1
            m -= 1
            # 後ろから復元しているので以下のようにする
            res = s[n] + res
    return res


S = input()
T = input()
print(lcs(S, T))


Fixed submission:
s = input()
t = input()

# dp = np.zeros(shape=(len(s), len(t)), dtype=np.int64)
dp = [[0] * (len(t)+1) for i in range(len(s)+1)]

for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+1)
        else:
            dp[i+1][j+1] = max(dp[i+1][j+1], max(dp[i][j+1], dp[i+1][j]))

# print(dp[len(s)][len(t)])


i = len(s)
j = len(t)
# print(type(i))
# print(type(j))
ans = ""
while (i > 0) and (j > 0):
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ans += s[i-1]
        i -= 1
        j -= 1

print(ans[::-1])

Buggy python submission (verdict: Time Limit Exceeded):
s = input()
t = input()

# dp = np.zeros(shape=(len(s), len(t)), dtype=np.int64)
dp = [[0] * (len(t)+1) for i in range(len(s)+1)]

for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+1)
        else:
            dp[i+1][j+1] = max(dp[i+1][j+1], max(dp[i][j+1], dp[i+1][j]))

# print(dp[len(s)][len(t)])


i = len(s)
j = len(t)
# print(type(i))
# print(type(j))
ans = ""
while (i > 0) and (j > 0):
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ans += s[i-1]
        i -= 1
        j -= 1

print(ans[::-1])


Fixed submission:
s = input()
t = input()

# dp = np.zeros(shape=(len(s), len(t)), dtype=np.int64)
dp = [[0] * (len(t)+1) for i in range(len(s)+1)]

for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+1)
        else:
            dp[i+1][j+1] = max(dp[i+1][j+1], max(dp[i][j+1], dp[i+1][j]))

# print(dp[len(s)][len(t)])


i = len(s)
j = len(t)
# print(type(i))
# print(type(j))
ans = ""
while (i > 0) and (j > 0):
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ans += s[i-1]
        i -= 1
        j -= 1

print(ans[::-1])
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = [int(input()) for _ in range(N)]

print("second" if all(a[i] % 2 == 0 for i in range(N)) else "first")


Fixed submission:
N = int(input())
A = [int(input()) for _ in range(N)]

print("second" if all(A[i] % 2 == 0 for i in range(N)) else "first")
Buggy python submission (verdict: Runtime Error):
import sys
N = int(sys.stdin.readline())

if N == 1:
    print('Hello World')
    sys.exit()

if N == 2:
    ans = 0
    for value in sys.stdin.readlines():
        ans += value

    print(ans)


Fixed submission:
import sys
N = int(sys.stdin.readline())

if N == 1:
    print('Hello World')
    sys.exit()

if N == 2:
    ans = 0
    for value in sys.stdin.readlines():
        ans += int(value)

    print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
N, T = map(int, sys.stdin.readline().strip().split())  # N個の帰宅経路, T時間以内に

cost = 1001
for line in sys.stdin.readlines():
    c, t = line.strip().split()
    if T >= t:
        cost = min(cost, c)

if cost == 1001:
    print('TLE')
else:
    print(cost)


Fixed submission:
import sys
N, T = map(int, sys.stdin.readline().strip().split())  # N個の帰宅経路, T時間以内に

cost = 1001
for line in sys.stdin.readlines():
    c, t = map(int, line.strip().split())
    if T >= t:
        cost = min(cost, c)

if cost == 1001:
    print('TLE')
else:
    print(cost)
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())  # 項数N, Aの和M

if N == 1:
    print(M)
    eixt()

# Mの約数を列挙する
primes = []
ans = 1


for i in range(1, int(M**(1/2))+1):
    if M % i == 0:
        primes.append(i)
        primes.append(M//i)

# 約数が全て手に入った
for d in primes:
    if M >= N * d:
        ans = d

print(d)


Fixed submission:
N, M = map(int, input().split())  # 項数N, Aの和M

ans = 1
for i in range(1, int(M**(1/2))+1):
    if M % i != 0:
        continue
    j = M // i  # jはどんどん小さくなる
    if j >= N:
        ans = max(ans, i)
    if i >= N:
        ans = max(ans, j)

print(ans)

Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())  # 項数N, Aの和M

ans = 1

if N == 1:
    print(M)
    exit()

for i in range(1000000):
    if (M >= N * i) and (M % i == 0):
        ans = i

print(ans)


Fixed submission:
N, M = map(int, input().split())  # 項数N, Aの和M

ans = 1
for i in range(1, int(M**(1/2))+1):
    if M % i != 0:
        continue
    j = M // i  # jはどんどん小さくなる
    if j >= N:
        ans = max(ans, i)
    if i >= N:
        ans = max(ans, j)

print(ans)
Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())

# Kが偶数の場合, 全てKの倍数または全てK//2に倍数の両方考える必要あり
num = [0]*(K)  # 1以上N以下の整数で余りが0~K-1の個数をカウントする
for i in range(1, N+1):
    num[i % K] += 1  # i % K の取りうる値は0~K-1

ans = 0
for a in range(K+1):  # aに関して全探索を行う
    b = (K-a) % K
    c = (K-a) % K
    if (b + c) % K == 0:
        ans += num[a] * num[b] * num[c]

print(ans)


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

ans = 0

num = [0] * (K+1)
for i in range(1, N+1):
    num[i % K] += 1

for a in range(K+1):
    b = (K-a) % K
    c = (K-a) % K
    if ((b+c) % K) == 0:
        ans += (num[a] * num[b] * num[c])

print(ans)
Buggy python submission (verdict: Runtime Error):
S = input()
K = int(input())
if K == 1:
    print(S[0])
elif S[K-1] == "1":
    print(1)
else:
    for i in range(len(S)):
        if S[i] != "1":
            print(S[i])
            exit()


Fixed submission:
S = input()
K = int(input())
if K == 1:
    print(S[0])
    exit()
else:
    for i in range(K):
        if S[i] != "1":
            print(S[i])
            exit()
print(1)

Buggy python submission (verdict: Runtime Error):
S = input()
K = int(input())
if K == 1:
    print(S[0])
elif S[K] == "1":
    print(1)
else:
    for i in range(len(S)):
        if S[i] != "1":
            print(S[i])
            exit()


Fixed submission:
S = input()
K = int(input())
if K == 1:
    print(S[0])
    exit()
else:
    for i in range(K):
        if S[i] != "1":
            print(S[i])
            exit()
print(1)

Buggy python submission (verdict: Runtime Error):
S = input()
K = int(input())
for i in range(len(S):
    if S[i] != 1:
        print(S[i])
        exit()

Fixed submission:
S = input()
K = int(input())
if K == 1:
    print(S[0])
    exit()
else:
    for i in range(K):
        if S[i] != "1":
            print(S[i])
            exit()
print(1)
Buggy python submission (verdict: Time Limit Exceeded):
N, M, Q = map(int, input().split())  # N個の駅, M本の列車, Q個のクエリ
# 始点と終点を全て格納する
X = [[0]*501 for _ in range(501)]
# 累積和を取るための二次元リスト(累積和自体は一次元, 最後に縦方向に和を取る)
C = [[0]*501 for _ in range(501)]

for _ in range(M):
    left, right = map(lambda x: int(x)-1, input().split())
    X[left][right] += 1  # 始点と終点を全て格納する

# 横方向に累積和を取る
for i in range(N):
    for j in range(N):
        C[i][j] = C[i][j-1] + X[i][j]

for _ in range(Q):
    p, q = map(lambda x: int(x)-1, input().split())
    ans = 0
    for i in range(p, q+1):
        ans += C[i][q] - C[i][p-1]
    print(ans)


Fixed submission:
N, M, Q = map(int, input().split())  # N個の駅, M本の電車, Q個のクエリ
X = [[0]*501 for _ in range(501)]
C = [[0]*501 for _ in range(501)]
for _ in range(M):
    left, right = map(lambda x: int(x)-1, input().split())
    X[left][right] += 1

for i in range(N):
    for j in range(N):
        # 累積和
        C[i][j] = C[i][j-1] + X[i][j]  # 横方向に累積されていく
for _ in range(Q):
    p, q = map(lambda x: int(x)-1, input().split())
    ans = 0
    for i in range(p, q+1):
        ans += C[i][q] - C[i][p-1]
    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, M, Q = map(int, input().split())  # N個の駅, M本の列車, Q個のクエリ
lines = [list(map(int, input().split())) for _ in range(M)]
query = [list(map(int, input().split())) for _ in range(Q)]
for p, q in query:
    # pが始点, qが終点
    ans = 0
    for l, r in lines:
        if l >= p and r <= q:
            ans += 1
    print(ans)


Fixed submission:
N, M, Q = map(int, input().split())  # N個の駅, M本の電車, Q個のクエリ
X = [[0]*501 for _ in range(501)]
C = [[0]*501 for _ in range(501)]
for _ in range(M):
    left, right = map(lambda x: int(x)-1, input().split())
    X[left][right] += 1

for i in range(N):
    for j in range(N):
        # 累積和
        C[i][j] = C[i][j-1] + X[i][j]  # 横方向に累積されていく
for _ in range(Q):
    p, q = map(lambda x: int(x)-1, input().split())
    ans = 0
    for i in range(p, q+1):
        ans += C[i][q] - C[i][p-1]
    print(ans)
Buggy python submission (verdict: Runtime Error):
# -2進数を求める
N = int(input())

if N == 0:
    print(0)
else:
    ans = ""
    while N != 0:
        if N % 2 != 0:
            N -= 1
            ans = "1" + ans
        else:
            ans = "0" + ans
        N = N // (-2)
print(ans)


Fixed submission:
N = int(input())
ans = ""
if N == 0:
    print(0)
    exit()
while N != 0:
    # 下の桁から求めていく
    r = N % 2
    if r < 0:
        r += 2
    N = (N-r) // (-2)
    ans += str(r)
print(ans[::-1])
Buggy python submission (verdict: Runtime Error):
import statistics
N = int(input())
A = list(map(int, input().split()))
B = []

for i in range(len(A)):
    B.append(A[i] - (i+1))

b = statistics.median(B)

ans = 0
for i in range(len(B)):
    ans += abs(B[i] - b)

print(int(ans))


Fixed submission:
import statistics
N = int(input())
A = list(map(int, input().split()))
B = []

for i in range(len(A)):
    B.append(A[i] - (i+1))

b = statistics.median(B)

ans = 0
for i in range(len(B)):
    ans += abs(B[i] - b)

print(int(ans))
Buggy python submission (verdict: Runtime Error):
S = input()
print(ans)
for i in range(4):
  if S[i] == "+":
    ans += 1
  else:
    ans -= 1
print(ans)

Fixed submission:
S = input()
ans = 0
for i in range(4):
  if S[i] == "+":
    ans += 1
  else:
    ans -= 1
print(ans)

Buggy python submission (verdict: Runtime Error):
S = input()
ans = 0
for i in range(4):
  if S[i] == "+":
    ans += 1
   else:
    ans -= 1

print(ans)

Fixed submission:
S = input()
ans = 0
for i in range(4):
  if S[i] == "+":
    ans += 1
  else:
    ans -= 1
print(ans)

Buggy python submission (verdict: Runtime Error):
S = str(input())
ans = 0
for i in range(len(S)):
  if S[i] == "+":
    ans += 1
   else:
    ans -= 1

print(ans)

Fixed submission:
S = input()
ans = 0
for i in range(4):
  if S[i] == "+":
    ans += 1
  else:
    ans -= 1
print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split()))
ans = N
for i in range(N-1):
    wa = 0
    if A[i] & A[i+1] != 0:
        continue
    ans += 1
    wa = A[i] ^ A[i+1]
    for j in range(i+2, 20):  # 全部0だった時にTLEを起こす
        if wa & A[j] == 0:
            wa = wa ^ A[j]
            ans += 1
        else:
            break
print(ans)


Fixed submission:
n = int(input())
a = list(map(int,input().split()))
l,r = 0,0
ans = 0
s = 0
while l < n:
  if r < n and s+a[r] == s^a[r]:
    s += a[r]
    r += 1
    #print(s)
  else:
    ans += r-l
    s -= a[l]
    #print(s)
    l += 1

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
ans = N
for i in range(N-1):
    wa = 0
    if A[i] & A[i+1] != 0:
        continue
    ans += 1
    wa = A[i] ^ A[i+1]
    for j in range(i+2, N):
        if wa & A[j] == 0:
            wa = wa ^ A[j]
            ans += 1
        else:
            break
print(ans)


Fixed submission:
n = int(input())
a = list(map(int,input().split()))
l,r = 0,0
ans = 0
s = 0
while l < n:
  if r < n and s+a[r] == s^a[r]:
    s += a[r]
    r += 1
    #print(s)
  else:
    ans += r-l
    s -= a[l]
    #print(s)
    l += 1

print(ans)
Buggy python submission (verdict: Runtime Error):
a, b, c, d = map(int, input().split())

if abs(a-c) =< d:
  print("Yes")
elif abs(a-b) =< d and abs(b-c) =< d:
  print("Yes")
else:
  print("No")

Fixed submission:
a, b, c, d = map(int, input().split())

if d >= abs(a-c):
    print("Yes")
elif abs(a-b) <= d and abs(b-c) <= d:
    print("Yes")
else:
    print("No")
Buggy python submission (verdict: Time Limit Exceeded):
X = int(input())

ans = []
for i in range(1000):
    for j in range(1000):
        if i**j > X:
            continue
        ans.append(i**j)
print(max(ans))


Fixed submission:
X = int(input())

ans = []
for i in range(1, 1000):
    for j in range(2, 11):
        if i**j > X:
            continue
        ans.append(i**j)
print(max(ans))
Buggy python submission (verdict: Time Limit Exceeded):
S = str(input())
K = int(input())

# Sのsubstring全列挙を行う
ans = []

for i in range(len(S)):
    for j in range(i+1, len(S)+1):
        ans.append(S[i:j])

ans = list(set(ans))
ans.sort()
print(ans[K-1])


Fixed submission:
S = str(input())
K = int(input())

# Sのsubstring全列挙を行う
ans = []

for i in range(len(S)):
    for j in range(i+1, i+K+1):
        ans.append(S[i:j])

ans = list(set(ans))
ans.sort()

print(ans[K-1])

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

# Sのsubstring全列挙を行う
ans = []

for i in range(len(S)):
    for j in range(i+1, len(S)+1):
        ans.append(S[i:j])

ans = list(set(ans))
ans.sort()
print(ans[K-1])


Fixed submission:
S = str(input())
K = int(input())

# Sのsubstring全列挙を行う
ans = []

for i in range(len(S)):
    for j in range(i+1, i+K+1):
        ans.append(S[i:j])

ans = list(set(ans))
ans.sort()

print(ans[K-1])
Buggy python submission (verdict: Runtime Error):
A, B, C = map(int, input.split())
if A+B >= C:
  print("Yes")
else:
  print("No")

Fixed submission:
A, B, C = map(int, input().split())
if A+B >= C:
  print("Yes")
else:
  print("No")
Buggy python submission (verdict: Time Limit Exceeded):
H, W, D = map(int, input().split())
status = {}
for i in range(H):
    A = list(map(int, input().split()))
    for j in range(W):
        status[A[j]] = (i+1, j+1)
Q = int(input())
Q = [list(map(int, input().split())) for _ in range(Q)]
# print(status)
for s, t in Q:
    ans = 0
    while s != t:
        tmp_t = s+D
        ans += abs((status[tmp_t][0] - status[s][0])) + abs(status[tmp_t][1]-status[s][1])
        s = tmp_t
    print(ans)


Fixed submission:
# 累積話の考え方を使う
H, W, D = map(int, input().split())
status = {}
for i in range(H):
    A = list(map(int, input().split()))
    for j in range(W):
        status[A[j]] = (i+1, j+1)
Q = int(input())
query = [list(map(int, input().split())) for _ in range(Q)]
# print(status)

# 目的地は必ずDだけ小さいマスからしか移動してこない
cumulative_sum = [0] * (H*W+1)
for i in range(H*W+1):
    if i <= D:
        cumulative_sum[i] = 0
        continue
    else:
        cumulative_sum[i] = cumulative_sum[i-D] + abs(status[i][0] - status[i-D][0]) + abs(status[i][1] - status[i-D][1])

for s, t in query:
    print(cumulative_sum[t] - cumulative_sum[s])
Buggy python submission (verdict: Runtime Error):
def eratosutenes(n):
    primes = [1] * (n+1)  # 0からnまでの素数リスト, 最初は全てが素数だと仮定する
    primes[0] = 0
    primes[1] = 0

    for i in range(2, int(n**(1/2))+1):
        if primes[i] == 0:
            continue
        if primes[i] == 1:
            for j in range(i * 2, n+1, i):
                primes[j] = 0
    return primes


# 素数に1がたち、素数でないものに0がたつリストができた
primes = eratosutenes(2017)

Q = int(input())
query = []

for _ in range(Q):
    l, r = map(int, input().split())
    query.append((l, r))

like_numbers_ruisekiwa = [0]  # 0のときは0

for i in range(1, len(primes)):
    if i % 2 == 1:  # 奇数のときだけ処理をする
        if primes[i] == 1 and primes[(i+1)//2] == 1:  # 両方素数ならインクリメントする
            like_numbers_ruisekiwa.append(like_numbers_ruisekiwa[-1] + 1)
        else:
            like_numbers_ruisekiwa.append(like_numbers_ruisekiwa[-1])
    if i % 2 == 0:
        like_numbers_ruisekiwa.append(like_numbers_ruisekiwa[-1])


for i in range(len(query)):
    l, r = query[i]
    print(like_numbers_ruisekiwa[r] - like_numbers_ruisekiwa[l-1])


Fixed submission:
def eratosutenes(n):
    primes = [1] * (n+1)  # 0からnまでの素数リスト, 最初は全てが素数だと仮定する
    primes[0] = 0
    primes[1] = 0

    for i in range(2, int(n**(1/2))+1):
        if primes[i] == 0:
            continue
        if primes[i] == 1:
            for j in range(i * 2, n+1, i):
                primes[j] = 0
    return primes


# 素数に1がたち、素数でないものに0がたつリストができた
primes = eratosutenes(100001)

Q = int(input())
query = []

for _ in range(Q):
    l, r = map(int, input().split())
    query.append((l, r))

like_numbers_ruisekiwa = [0]  # 0のときは0

for i in range(1, len(primes)):
    if i % 2 == 1:  # 奇数のときだけ処理をする
        if primes[i] == 1 and primes[(i+1)//2] == 1:  # 両方素数ならインクリメントする
            like_numbers_ruisekiwa.append(like_numbers_ruisekiwa[-1] + 1)
        else:
            like_numbers_ruisekiwa.append(like_numbers_ruisekiwa[-1])
    if i % 2 == 0:
        like_numbers_ruisekiwa.append(like_numbers_ruisekiwa[-1])


for i in range(len(query)):
    l, r = query[i]
    print(like_numbers_ruisekiwa[r] - like_numbers_ruisekiwa[l-1])
Buggy python submission (verdict: Runtime Error):
X = str(input())
tmp = 0
for i in range(len(X)):
  tmp += int(X[i])

if X % tmp == 0:
  print('Yes')
else:
  print('No')

Fixed submission:
X = str(input())
tmp = 0
for i in range(len(X)):
  tmp += int(X[i])

if int(X) % tmp == 0:
  print('Yes')
else:
  print('No')
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input().rstrip())
A = list(map(int, input().rstrip().split()))
B = list(map(int, input().rstrip().split()))
C = list(map(int, input().rstrip().split()))

A.sort()
B.sort()
C.sort()

def bin_search(vlist, targ):
    lb = -1
    ub = len(vlist)
    while ub - lb > 1:
        mid = (lb + ub) // 2
        if vlist[mid] >= targ:
            ub = mid
        else:
            lb = mid
    return ub

total = 0
for c in C:
    b_ub = bin_search(B, c)
    for b in B[:b_ub]:
        a_ub = bin_search(A, b)
        total += len(A[:a_ub])

print(total)

Fixed submission:
import bisect
N = int(input())

A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.sort()
B.sort()
C.sort()

ans = 0
for b in B:
    lower_a = bisect.bisect_left(A, b)
    upper_c = N - bisect.bisect_right(C, b)
    ans += lower_a*upper_c

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
for h in range(3501):
    for n in range(3501):
        if 4*h*n - N*n - N*h == 0:
            continue
        w = N*h*n / (4*h*n - N*n - N*h)
        if w > 0 and int(w) == w:
            print(h, n, int(w))
            exit()


Fixed submission:
N = int(input())
for h in range(3501):
    for n in range(3501):
        if 4*h*n - N*n - N*h == 0:
            continue
        w = N*h*n / (4*h*n - N*n - N*h)
        if w > 0 and int(w) == w:
            print(h, n, int(w))
            exit()
Buggy python submission (verdict: Time Limit Exceeded):
from scipy.sparse.csgraph import floyd_warshall
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]

# for a in A:
#     print(a)
# 余分な辺を消去する問題
graph = floyd_warshall(A)
for i in range(N):
    for j in range(N):
        if A[i][j] != graph[i][j]:
            print(-1)
            exit()

# 最短経路であることは分かった
flag = [[True]*N for _ in range(N)]
for k in range(N):
    for i in range(N):
        for j in range(N):
            if graph[i][j] == graph[i][k] + graph[k][j] and i != k and k != j:
                flag[i][j] = False

ans = 0
for i in range(N):
    for j in range(i+1, N):
        if flag[i][j] == True:
            ans += graph[i][j]
print(int(ans))


Fixed submission:
import copy

def warshal_floyd(d):
    # d[i][j] := iからjへの最短距離
    global N
    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])
    # "今現在求まっているiからjへの最短距離"と"今現在求まっているiからkへの最短距離 + 今現在求まっているkからjへの最短距離 の和"を比較する
    return d


N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
graph = copy.deepcopy(A)
# for a in A:
#     print(a)
# 余分な辺を消去する問題
A = warshal_floyd(A)
for i in range(N):
    for j in range(N):
        if A[i][j] != graph[i][j]:
            print(-1)
            exit()

# 最短経路であることは分かった
flag = [[True]*N for _ in range(N)]
for k in range(N):
    for i in range(N):
        for j in range(N):
            if graph[i][j] == graph[i][k] + graph[k][j] and i != k and k != j:
                flag[i][j] = False

ans = 0
for i in range(N):
    for j in range(i+1, N):
        if flag[i][j] == True:
            ans += graph[i][j]
print(int(ans))
Buggy python submission (verdict: Runtime Error):
# 二項係数を"やるだけ"にしてくれるライブラリ
from collections import Counter
MAX = 1000005
MOD = 10**9+7
factrial = [0]*MAX
inverse = [0]*MAX
factrial_inverse = [0]*MAX


# テーブルを作る前処理
def COMinit():
    global factrial, inverse, factrial_inverse
    factrial[0] = 1
    factrial[1] = 1
    inverse[1] = 1
    factrial_inverse[0] = 1
    factrial_inverse[1] = 1
    for i in range(2, MAX):
        factrial[i] = factrial[i-1] * i % MOD
        inverse[i] = MOD - inverse[MOD % i] * (MOD//i) % MOD
        factrial_inverse[i] = factrial_inverse[i-1] * inverse[i] % MOD


# 二項係数計算
def COM(n, k):
    global factrial, inverse, factrial_inverse
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return factrial[n] * (factrial_inverse[k] * factrial_inverse[n-k] % MOD) % MOD


# 前処理完了
COMinit()


N, P = map(int, input().split())  # 袋がN個, mod2をPにしたい
A = list(map(lambda x: int(x)%2, input().split()))
# print(A)

kisuu = sum(A)  # 奇数個の袋の数
guusuu = N-kisuu  # 偶数個の袋の数

# Pが1のとき，偶数側の袋を任意の数と，奇数側の数を奇数個選ぶ
if P == 1:
    aaa
    tmp_guusuu = 0
    tmp_kisuu = 0
    # 偶数側を任意の個数選ぶ
    for i in range(guusuu+1):
        tmp_guusuu += COM(guusuu, i)
    for i in range(kisuu+1):
        if i % 2 == 0:
            continue
        tmp_kisuu += COM(kisuu, i)
    print(tmp_guusuu*tmp_kisuu)

# Pが0のとき，偶数側の袋を任意の数と，奇数側の数を偶数個選ぶ
elif P == 0:
    tmp_guusuu = 0
    tmp_kisuu = 0
    # 偶数側を任意の個数選ぶ
    for i in range(guusuu+1):
        tmp_guusuu += COM(guusuu, i)
    # 奇数側を0個数以上の偶数個選ぶ
    for i in range(kisuu+1):
        if i % 2 == 1:
            continue
        tmp_kisuu += COM(kisuu, i)
    print(tmp_guusuu*tmp_kisuu)


Fixed submission:
nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]


N, P = map(int, input().split())  # 袋がN個, 2をPにしたい
A = list(map(lambda x: int(x)%2, input().split()))
# print(A)

kisuu = sum(A)  # 奇数個の袋の数
guusuu = N-kisuu  # 偶数個の袋の数

# Pが1のとき，偶数側の袋を任意の数と，奇数側の数を奇数個選ぶ
if P == 1:
    tmp_guusuu = 0
    tmp_kisuu = 0
    # 偶数側を任意の個数選ぶ
    for i in range(guusuu+1):
        tmp_guusuu += cmb(guusuu, i)
    for i in range(kisuu+1):
        if i % 2 == 0:
            continue
        tmp_kisuu += cmb(kisuu, i)
    print(tmp_guusuu*tmp_kisuu)

# Pが0のとき，偶数側の袋を任意の数と，奇数側の数を偶数個選ぶ
elif P == 0:
    tmp_guusuu = 0
    tmp_kisuu = 0
    # 偶数側を任意の個数選ぶ
    for i in range(guusuu+1):
        tmp_guusuu += cmb(guusuu, i)
    # 奇数側を0個数以上の偶数個選ぶ
    for i in range(kisuu+1):
        if i % 2 == 1:
            continue
        tmp_kisuu += cmb(kisuu, i)
    print(tmp_guusuu*tmp_kisuu)