Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
bingo = [list(map(int, input().split(" "))) for i in range(3)]
N = int(input())
b = [int(input()) for i in range(N)]

#list = [[0] * 3] * 3
list = [ [0]*3 for x in range( 0, 3 ) ]
flag = 0

# print(list)

for i in range(0, 3):
    for j in range(0, 3):
        for k in range(0, N):
            if bingo[i][j] == b[k]:
                list[i][j] = 1
                #print(list)
                #print(b[k])
# print(list)
# list = [[1,0,0], [1, 1, 0], [0,0,1]]

for i in range(0, 3):
    hantei = 0
    for j in range(0, 3):
        hantei = hantei + list[i][j]
    if hantei == 3:
        flag = 1
        break

for i in range(0, 3):
    hantei = 0
    for j in range(0, 3):
        hantei = hantei + list[j][i]
    if hantei == 3:
        flag = 1
        break

hantei = 0
for i in range(0, 3):
    hantei = hantei + list[i][i]
if hantei == 3:
    flag = 1

hantei = 0
for i in range(0, 3):
    hantei = hantei + list[i][2 - i]
if hantei == 3:
    flag = 1

if flag == 1:
    print('Yes')
elif flag == 0:
    print('No')
    

Fixed submission:
N = int(input())
p = int(N / 2)

if N % 2 == 1:
    p = p + 1

print(p)
Buggy python submission (verdict: Time Limit Exceeded):
import sys

input = sys.stdin.readline

mod = 998244353

n, k = map(int, input().split())

lr = [tuple(map(int, input().split())) for _ in range(k)]
lr.sort()

leaplist = []
for l, r in lr:
    leaplist += list(range(l, r + 1))
pass

dp = [0] * n
dp[0] = 1
for i in range(1, n):
    for l in leaplist:
        if i < l:
            break
        dp[i] += dp[i - l]
        dp[i] %= mod
print(dp[-1])


Fixed submission:
import sys

input = sys.stdin.readline

mod = 998244353

n, k = map(int, input().split())

lr = [list(map(int, input().split())) for _ in range(k)]
lr.sort()

a = [0] * n
a[0] = 1
a[1] = -1
f = [1]

for i in range(n - 1):
    for l, r in lr:
        if i + l < n:
            a[i + l] += f[i]
            a[i + l] %= mod
        else:
            break
        if i + r + 1 < n:
            a[i + r + 1] -= f[i]
            a[i + r + 1] %= mod
        else:
            break
    f.append((f[i] + a[i + 1]) % mod)
print(f[n - 1])
Buggy python submission (verdict: Time Limit Exceeded):
H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
S = [input() for _ in range(H)]
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

a = [(-1, 0), (1, 0), (0, -1), (0, 1)]
b = [(i % 5 - 2, i // 5 - 2) for i in range(25) if (i % 5 - 2, i // 5 - 2) not in a]

d = [[H * W] * W for _ in range(H)]
d[Ch][Cw] = 0
Q = {(Ch, Cw)}
while Q:
    h, w = Q.pop()
    for ah, aw in a:
        nh, nw = h + ah, w + aw
        if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == ".":
            if d[nh][nw] > d[h][w]:
                d[nh][nw] = d[h][w]
                Q.add((nh, nw))
    for ah, aw in b:
        nh, nw = h + ah, w + aw
        if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == ".":
            if d[nh][nw] > d[h][w] + 1:
                d[nh][nw] = d[h][w] + 1
                Q.add((nh, nw))

if d[Dh][Dw] == H * W:
    ans = -1
else:
    ans = d[Dh][Dw]
print(ans)



Fixed submission:
from heapq import heappop, heappush

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
S = [input() for _ in range(H)]
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

a = [(-1, 0), (1, 0), (0, -1), (0, 1)]
b = [(i % 5 - 2, i // 5 - 2) for i in range(25) if (i % 5 - 2, i // 5 - 2) not in a]

d = [[H * W] * W for _ in range(H)]
d[Ch][Cw] = 0
Q = [(0, Ch, Cw)]
while Q:
    now_d, h, w = heappop(Q)
    if now_d > d[h][w]:
        continue
    if (h, w) == (Dh, Dw):
        break
    for ah, aw in a:
        nh, nw = h + ah, w + aw
        if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == ".":
            if d[nh][nw] > d[h][w]:
                d[nh][nw] = d[h][w]
                heappush(Q, (d[nh][nw], nh, nw))
    for ah, aw in b:
        nh, nw = h + ah, w + aw
        if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == ".":
            if d[nh][nw] > d[h][w] + 1:
                d[nh][nw] = d[h][w] + 1
                heappush(Q, (d[nh][nw], nh, nw))

if d[Dh][Dw] == H * W:
    ans = -1
else:
    ans = d[Dh][Dw]
print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
X = input()

N_ub = 2 * 10 ** 5
f = [-1] * (N_ub + 1)
f[0] = 0
for n in range(1, N_ub + 1):
    pc = format(n, "b").count("1")
    f[n] = f[n % pc] + 1

X_pc = X.count("1")
X_res_m1 = 0
X_res_p1 = 0
for i, s in enumerate(reversed(X)):
    if s == "1":
        X_res_m1 += pow(2, i, X_pc - 1)
        X_res_m1 %= X_pc - 1

        X_res_p1 += pow(2, i, X_pc + 1)
        X_res_p1 %= X_pc + 1

ans = []
for i, s in enumerate(reversed(X)):
    if s == "1":
        fx = (X_res_m1 - pow(2, i, X_pc - 1)) % (X_pc - 1)
        ans.append(f[fx] + 1)
    else:
        fx = (X_res_p1 + pow(2, i, X_pc + 1)) % (X_pc + 1)
        ans.append(f[fx] + 1)

print(*reversed(ans), sep="\n")


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

X_pc = X.count("1")
X_res_m1 = 0
X_res_p1 = 0
for i, s in enumerate(reversed(X)):
    if s == "1":
        if X_pc > 1:
            X_res_m1 += pow(2, i, X_pc - 1)
            X_res_m1 %= X_pc - 1

        X_res_p1 += pow(2, i, X_pc + 1)
        X_res_p1 %= X_pc + 1

f = [-1] * (X_pc + 1)
f[0] = 0
for n in range(1, X_pc + 1):
    pc = format(n, "b").count("1")
    f[n] = f[n % pc] + 1

ans = []
for i, s in enumerate(reversed(X)):
    if s == "1":
        if X_pc > 1:
            fx = (X_res_m1 - pow(2, i, X_pc - 1)) % (X_pc - 1)
            ans.append(f[fx] + 1)
        else:
            ans.append(0)

    else:
        fx = (X_res_p1 + pow(2, i, X_pc + 1)) % (X_pc + 1)
        ans.append(f[fx] + 1)

print(*reversed(ans), sep="\n")

Buggy python submission (verdict: Runtime Error):
N = int(input())
X = input()

N_ub = 2 * 10 ** 5
f = [-1] * (N_ub)
f[0] = 0
for n in range(1, N_ub):
    pc = format(n, "b").count("1")
    f[n] = f[n % pc] + 1

X_pc = X.count("1")
X_res_m1 = 0
X_res_p1 = 0
for i, s in enumerate(reversed(X)):
    if s == "1":
        X_res_m1 += pow(2, i, X_pc - 1)
        X_res_m1 %= X_pc - 1

        X_res_p1 += pow(2, i, X_pc + 1)
        X_res_p1 %= X_pc + 1

ans = []
for i, s in enumerate(reversed(X)):
    if s == "1":
        fx = (X_res_m1 - pow(2, i, X_pc - 1)) % (X_pc - 1)
        ans.append(f[fx] + 1)
    else:
        fx = (X_res_p1 + pow(2, i, X_pc + 1)) % (X_pc + 1)
        ans.append(f[fx] + 1)

print(*reversed(ans), sep="\n")


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

X_pc = X.count("1")
X_res_m1 = 0
X_res_p1 = 0
for i, s in enumerate(reversed(X)):
    if s == "1":
        if X_pc > 1:
            X_res_m1 += pow(2, i, X_pc - 1)
            X_res_m1 %= X_pc - 1

        X_res_p1 += pow(2, i, X_pc + 1)
        X_res_p1 %= X_pc + 1

f = [-1] * (X_pc + 1)
f[0] = 0
for n in range(1, X_pc + 1):
    pc = format(n, "b").count("1")
    f[n] = f[n % pc] + 1

ans = []
for i, s in enumerate(reversed(X)):
    if s == "1":
        if X_pc > 1:
            fx = (X_res_m1 - pow(2, i, X_pc - 1)) % (X_pc - 1)
            ans.append(f[fx] + 1)
        else:
            ans.append(0)

    else:
        fx = (X_res_p1 + pow(2, i, X_pc + 1)) % (X_pc + 1)
        ans.append(f[fx] + 1)

print(*reversed(ans), sep="\n")
Buggy python submission (verdict: Time Limit Exceeded):
from time import time
from random import randrange

t0 = time()

D = int(input())
c = list(map(int, input().split()))
s = [list(map(int, input().split())) for _ in range(D)]

N = 26


t = [max(range(26), key=lambda x: si[x]) for si in s]


while time() - t0 < 1.9:
    # init
    diff = 0

    di = randrange(D)
    qi = randrange(N)

    # delete
    old_type = t[di]

    for next_d in range(di + 1, D):
        if t[next_d] == old_type:
            break
    else:
        next_d = D

    for prev_d in range(di - 1, -1, -1):
        if t[prev_d] == old_type:
            break
    else:
        prev_d = -1

    diff -= s[di][old_type]
    diff -= (next_d - di) * (di - prev_d) * c[old_type]

    # insert
    for next_d in range(di + 1, D):
        if t[next_d] == qi:
            break
    else:
        next_d = D

    for prev_d in range(di - 1, -1, -1):
        if t[prev_d] == qi:
            break
    else:
        prev_d = -1

    diff += s[di][qi]
    diff += (next_d - di) * (di - prev_d) * c[qi]

    # saiyou
    if diff >= 0:
        t[di] = qi

ans = [ti + 1 for ti in t]
print(*ans, sep="\n")

Fixed submission:
from time import time

t0 = time()

from random import randrange

D = int(input())
c = list(map(int, input().split()))
s = [list(map(int, input().split())) for _ in range(D)]

N = 26


t = [max(range(26), key=lambda x: si[x]) for si in s]


while time() - t0 < 1.8:
    # init
    diff = 0

    di = randrange(D)
    qi = randrange(N)

    # delete
    old_type = t[di]

    for next_d in range(di + 1, D):
        if t[next_d] == old_type:
            break
    else:
        next_d = D

    for prev_d in range(di - 1, -1, -1):
        if t[prev_d] == old_type:
            break
    else:
        prev_d = -1

    diff -= s[di][old_type]
    diff -= (next_d - di) * (di - prev_d) * c[old_type]

    # insert
    for next_d in range(di + 1, D):
        if t[next_d] == qi:
            break
    else:
        next_d = D

    for prev_d in range(di - 1, -1, -1):
        if t[prev_d] == qi:
            break
    else:
        prev_d = -1

    diff += s[di][qi]
    diff += (next_d - di) * (di - prev_d) * c[qi]

    # saiyou
    if diff >= 0:
        t[di] = qi

ans = [ti + 1 for ti in t]
print(*ans, sep="\n")
Buggy python submission (verdict: Time Limit Exceeded):
D = int(input())
c = list(map(int, input().split()))
s = [list(map(int, input().split())) for _ in range(D)]
t = [int(input()) - 1 for _ in range(D)]
M = int(input())

d = []
q = []
for _ in range(M):
    d_, q_ = map(int, input().split())
    d.append(d_ - 1)
    q.append(q_ - 1)

N = 26


def calc_score(t):
    scores = [0] * N
    last = [-1] * N
    for d in range(D):
        last[t[d]] = d
        scores[t[d]] += s[d][t[d]]

        for i in range(N):
            if last[t[d]] != -1:
                scores[i] -= c[i] * (d - last[i])
    return sum(scores)


for di, qi in zip(d, q):
    t[di] = qi
    print(calc_score(t))

Fixed submission:
D = int(input())
c = list(map(int, input().split()))
s = [list(map(int, input().split())) for _ in range(D)]
t = [int(input()) - 1 for _ in range(D)]
M = int(input())

d = []
q = []
for _ in range(M):
    d_, q_ = map(int, input().split())
    d.append(d_ - 1)
    q.append(q_ - 1)

N = 26


def calc_score(t):
    scores = [0] * N
    last = [-1] * N
    for d in range(D):
        last[t[d]] = d
        scores[t[d]] += s[d][t[d]]

        for i in range(N):
            if last[t[d]] != -1:
                scores[i] -= c[i] * (d - last[i])
    return sum(scores)


score = calc_score(t)


for di, qi in zip(d, q):
    # delete
    old_type = t[di]

    for next_d in range(di + 1, D):
        if t[next_d] == old_type:
            break
    else:
        next_d = D

    for prev_d in range(di - 1, -1, -1):
        if t[prev_d] == old_type:
            break
    else:
        prev_d = -1

    score -= s[di][old_type]
    score -= (next_d - di) * (di - prev_d) * c[old_type]

    # insert
    for next_d in range(di + 1, D):
        if t[next_d] == qi:
            break
    else:
        next_d = D

    for prev_d in range(di - 1, -1, -1):
        if t[prev_d] == qi:
            break
    else:
        prev_d = -1

    score += s[di][qi]
    score += (next_d - di) * (di - prev_d) * c[qi]

    print(score)

    t[di] = qi
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))

A3 = 0
for i in range(2, N):
    A3 ^= A[i]

ans = -1
for i in range(A[0]):
    if (A[0] - i) ^ (A[1] + i) == A3:
        ans = i
        break
print(ans)

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

X = 0
for i in range(2, N):
    X ^= A[i]

S = A[0] + A[1]
A1 = A[0]

D, M = divmod(S - X, 2)
ans = -1
if M % 2 == 0 and D & X == 0 and D <= A1:
    Y = 0
    for p in range(P, -1, -1):
        if (X >> p) & 1 == 1:
            new_Y = Y ^ (1 << p)
            if D ^ new_Y <= A1:
                Y = new_Y

    ans = A1 - (D ^ Y)
    if ans == A1:
        ans = -1

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter


_ = int(input())
A = list(map(int, input().split()))


A2 = list(set(A))
A2.sort()
basis = []

for a in A2:
    for b in basis:
        if a % b == 0:
            break
    else:
        basis.append(a)

ans = 0
c = Counter(A)
for b in basis:
    if c[b] == 1:
        ans += 1

print(ans)

Fixed submission:
from collections import Counter

_ = int(input())
A = list(map(int, input().split()))
a_max = 10 ** 6

c = Counter(A)
b = list(set(A))
b.sort()

dp = [True] * (a_max + 1)
ans = 0
for a in b:
    if dp[a]:
        if c[a] == 1:
            ans += 1
        for i in range(2 * a, a_max + 1, a):
            dp[i] = False

print(ans)

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


_ = int(input())
A = list(map(int, input().split()))

A.sort()
basis = []

for a in A:
    for b in basis:
        if a % b == 0:
            break
    else:
        basis.append(a)

ans = 0
c = Counter(A)
for b in basis:
    if c[b] == 1:
        ans += 1

print(ans)
pass


Fixed submission:
from collections import Counter

_ = int(input())
A = list(map(int, input().split()))
a_max = 10 ** 6

c = Counter(A)
b = list(set(A))
b.sort()

dp = [True] * (a_max + 1)
ans = 0
for a in b:
    if dp[a]:
        if c[a] == 1:
            ans += 1
        for i in range(2 * a, a_max + 1, a):
            dp[i] = False

print(ans)

Buggy python submission (verdict: Runtime Error):
_ = int(input())
A = list(map(int, input().split()))

A.sort()
basis = []

for a in A:
    for b in basis:
        if a % b == 0:
            break
    else:
        basis.append(a)

ans = 0
c = Counter(A)
for b in basis:
    if c[b] == 1:
        ans += 1

print(ans)

Fixed submission:
from collections import Counter

_ = int(input())
A = list(map(int, input().split()))
a_max = 10 ** 6

c = Counter(A)
b = list(set(A))
b.sort()

dp = [True] * (a_max + 1)
ans = 0
for a in b:
    if dp[a]:
        if c[a] == 1:
            ans += 1
        for i in range(2 * a, a_max + 1, a):
            dp[i] = False

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from time import time

t0 = time()
N, K = map(int, input().split())
A = list(map(int, input().split()))



def a_to_b(A):
    c = [0] * N
    for i, a in enumerate(A):
        lb = max(0, i - a)
        c[lb] += 1
        ub = i + a + 1
        if ub < N:
            c[ub] -= 1
    tmp = 0
    B = []
    for ci in c:
        tmp += ci
        B.append(tmp)
    return B


ans = A
for _ in range(K):
    if time() - t0 > 1.99:
        break
    ans = a_to_b(ans)

print(*ans)

Fixed submission:
def a_to_b(A):
    c = [0] * N
    for i, a in enumerate(A):
        lb = max(0, i - a)
        c[lb] += 1
        ub = i + a + 1
        if ub < N:
            c[ub] -= 1
    tmp = 0
    B = []
    for ci in c:
        tmp += ci
        B.append(tmp)
    return B


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

ans = A
for _ in range(K):
    ans = a_to_b(ans)
    if sum(ans) == N ** 2:
        break

print(*ans)

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


def a_to_b(A):
    c = [0] * N
    for i, a in enumerate(A):
        lb = max(0, i - a)
        c[lb] += 1
        ub = i + a + 1
        if ub < N:
            c[ub] -= 1
    tmp = 0
    B = []
    for ci in c:
        tmp += ci
        B.append(tmp)
    return B


ans = A
for _ in range(K):
    ans = a_to_b(ans)

print(*ans)
pass


Fixed submission:
def a_to_b(A):
    c = [0] * N
    for i, a in enumerate(A):
        lb = max(0, i - a)
        c[lb] += 1
        ub = i + a + 1
        if ub < N:
            c[ub] -= 1
    tmp = 0
    B = []
    for ci in c:
        tmp += ci
        B.append(tmp)
    return B


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

ans = A
for _ in range(K):
    ans = a_to_b(ans)
    if sum(ans) == N ** 2:
        break

print(*ans)
Buggy python submission (verdict: Runtime Error):
import bisect
import sys


N = int(input())
a = list(map(int, input().split()))
to = [[] for _ in range(N)]
for _ in range(N - 1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    to[u].append(v)
    to[v].append(u)
del u, v

ans = [-1] * N


def dfs(v, dp):
    # dp は参照渡し
    if len(dp) == 0 or a[v] > dp[-1]:
        dp.append(a[v])
        back = -1
    else:
        pos = bisect.bisect_left(dp, a[v])
        back = dp[pos]
        dp[pos] = a[v]
    ans[v] = len(dp)

    for u in to[v]:
        if ans[u] == -1:
            dfs(u, dp)
    if back == -1:
        dp.pop()
    else:
        dp[pos] = back


sys.setrecursionlimit(10 ** 6)
dfs(0, [])


for an in ans:
    print(an)


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

for i in range(A, B + 1):
    if i % K == 0:
        ans = "OK"
        break
else:
    ans = "NG"
print(ans)
Buggy python submission (verdict: Runtime Error):
import numpy as np

K = int(input())

top = np.ones(10, dtype=int)
# top[0] = 0
adj = np.eye(10, dtype=int)
adj[1:, :-1] += np.eye(9, dtype=int)
adj[:-1, 1:] += np.eye(9, dtype=int)

counts = [top]
tmp = top
for _ in range(10):
    tmp = tmp.__matmul__(adj)
    counts.append(tmp)

for i in range(10):
    for j in range(1, 10):
        if K > counts[i][j]:
            K -= counts[i][j]
        else:
            break
    else:
        continue
    break

ans = [-1] * (i + 1)
ans[i] = j

for d in range(i, 0, -1):
    for k in range(max(0, j - 1), min(9, j + 1) + 1):
        if K > counts[d - 1][k]:
            K -= counts[d - 1][k]
        else:
            ans[d - 1] = k
            j = k
            break


print("".join(list(map(str, ans))[::-1]))


Fixed submission:
import numpy as np

K = int(input())

top = np.ones(10, dtype=int)
adj = np.eye(10, dtype=int)
adj[1:, :-1] += np.eye(9, dtype=int)
adj[:-1, 1:] += np.eye(9, dtype=int)

counts = [top]
tmp = top
for _ in range(10):
    tmp = np.dot(tmp, adj)
    counts.append(tmp)

for i in range(10):
    for j in range(1, 10):
        if K > counts[i][j]:
            K -= counts[i][j]
        else:
            break
    else:
        continue
    break

ans = [-1] * (i + 1)
ans[i] = j

for d in range(i, 0, -1):
    for k in range(max(0, j - 1), min(9, j + 1) + 1):
        if K > counts[d - 1][k]:
            K -= counts[d - 1][k]
        else:
            ans[d - 1] = k
            j = k
            break


print("".join(list(map(str, ans))[::-1]))
Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heapify, heappush, heappop

N, D, A = map(int, input().split())
XH = [tuple(map(int, input().split())) for _ in range(N)]

heap = [(x, h, True) for x, h in XH]
heapify(heap)

ans = 0
bomb_effect = 0
while heap:
    x, h, monster_flg = heappop(heap)
    if monster_flg:
        tairyoku = h - bomb_effect
        if tairyoku > 0:
            new_bomb = -((-tairyoku) // A)
            ans += new_bomb
            heappush(heap, (x + 2 * D + 0.5, new_bomb, False))
            bomb_effect += new_bomb * A
    else:
        bomb_effect -= h * A

print(ans)


Fixed submission:
N, D, A = map(int, input().split())
XH = [tuple(map(int, input().split())) for _ in range(N)]
XH.sort()


ans = 0
bomb_effect = 0
bomb_i = 0
bombs = []
for x, h in XH:
    while (bomb_i < len(bombs)) and (x > bombs[bomb_i][0]):
        bomb_effect -= bombs[bomb_i][1] * A
        bomb_i += 1

    tairyoku = h - bomb_effect
    if tairyoku > 0:
        new_bomb = -((-tairyoku) // A)
        ans += new_bomb
        bombs.append((x + 2 * D + 0.5, new_bomb))
        bomb_effect += new_bomb * A

print(ans)
Buggy python submission (verdict: Runtime Error):
from scipy.sparse.csgraph import dijkstra, csgraph_from_dense
import numpy as np

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

v_id_dict = {}
dista = np.ones((20, 20)) * np.inf

for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            v_id_dict[i, j] = len(v_id_dict)

            if (i > 0) and (S[i - 1][j] == "."):
                dista[v_id_dict[(i, j)], v_id_dict[(i - 1, j)]] = 1

            if (j > 0) and (S[i][j - 1] == "."):
                dista[v_id_dict[(i, j)], v_id_dict[(i, j - 1)]] = 1

dist_mat = dijkstra(
    csgraph_from_dense(dista[: len(v_id_dict), : len(v_id_dict)]),
    directed=False,
    unweighted=False,
)

print(int(dist_mat.max()))


Fixed submission:
from scipy.sparse.csgraph import dijkstra, csgraph_from_dense
import numpy as np

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

v_id_dict = {}
dista = np.ones((400, 400)) * np.inf

for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            v_id_dict[i, j] = len(v_id_dict)

            if (i > 0) and (S[i - 1][j] == "."):
                dista[v_id_dict[(i, j)], v_id_dict[(i - 1, j)]] = 1

            if (j > 0) and (S[i][j - 1] == "."):
                dista[v_id_dict[(i, j)], v_id_dict[(i, j - 1)]] = 1

dist_mat = dijkstra(
    csgraph_from_dense(dista[: len(v_id_dict), : len(v_id_dict)]),
    directed=False,
    unweighted=False,
)

print(int(dist_mat.max()))
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7

A.sort()

factorial = [1]
for i in range(1, N + 1):
    factorial.append(factorial[-1] * i)
inv_factorial = [-1] * (N + 1)
inv_factorial[-1] = pow(factorial[-1], MOD - 2, MOD)
for i in reversed(range(N)):
    inv_factorial[i] = inv_factorial[i + 1] * (i + 1) % MOD


ans = 0
for i in range(N - K + 1):
    c = factorial[N - 1 - i] * inv_factorial[K - 1] * inv_factorial[N - K - i]
    ans += c * (A[-1 - i] - A[i])
    ans %= MOD

print(ans)


Fixed submission:
N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7

A.sort()

factorial = [1]
for i in range(1, N + 1):
    factorial.append(factorial[-1] * i  % MOD)
inv_factorial = [-1] * (N + 1)
inv_factorial[-1] = pow(factorial[-1], MOD - 2, MOD)
for i in reversed(range(N)):
    inv_factorial[i] = inv_factorial[i + 1] * (i + 1) % MOD


ans = 0
for i in range(N - K + 1):
    c = factorial[N - 1 - i] * inv_factorial[K - 1] * inv_factorial[N - K - i]
    ans += c * (A[-1 - i] - A[i])
    ans %= MOD

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

MOD = 10 ** 9 + 7
N = int(input())
x = list(map(int, input().split()))
x.sort()
x_arr = np.array(x)
x_diff = np.diff(x_arr)

a = np.zeros(N - 1, dtype=int)
a[0] += 1
for i in range(1, N - 1):
    a[i] = a[0]
    a[:i] = a[:i] * (i + 1) % MOD
a = np.cumsum(a) % MOD

print(np.dot(a, x_diff) % MOD)


Fixed submission:
MOD = 10 ** 9 + 7
N = int(input())
x = list(map(int, input().split()))
x.sort()

kaijo = [1]
for i in range(1, N):
    kaijo.append(kaijo[-1] * i % MOD)

ans = 0
for i in range(N - 1):
    ans = (ans * (i + 1) + (x[-1] - x[i]) * kaijo[i]) % MOD

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

c = [ai + aj for ai in A for aj in A]
c.sort()

ans = sum(c[-M:])
print(ans)


Fixed submission:
from numpy.fft import rfft, irfft
import numpy as np
from bisect import bisect_left, bisect_right

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

a = np.zeros(2 ** 18)
for Ai in A:
    a[Ai] += 1

fa = rfft(a)
a2 = irfft(fa ** 2)
a2 = np.round(a2).astype(np.int)

cum_a2 = np.cumsum(a2)

index = bisect_left(cum_a2, N ** 2 - M)
eli = cum_a2[index] - (N ** 2 - M)

a2[index] -= eli

ans = sum(A) * 2 * N - (a2[: index + 1] * np.arange(index + 1)).sum()
print(ans)