Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
#146_F
n, m = map(int, input().split())
s = input()

dp = [[] for _ in range(n+1)]
for i in range(1, n+1):
    if s[i] == '1':
        continue
    l = []
    for j in range(1, m+1):
        if s[i-j] == '1':
            continue
        if i - j < 0:
            continue
        l.append([len(dp[i-j]) + 1, dp[i-j] + [j]])
        
    if len(l) == 0:
        dp[n] = [-1]
        break
        
    l.sort()
    dp[i] = l[0][1]
    
print(*dp[n])

Fixed submission:
#146_F
n, m = map(int, input().split())
s = input()[::-1]
ans = []

flg = True
cur = 0
while cur < n and flg:
    for to in range(cur + m, cur, -1):
        if to > n:
            continue
            
        if s[to] == '0':
            ans.append(to - cur)
            cur = to
            break
        
        if to == cur + 1:
            flg = False

if flg:
    print(*ans[::-1])
else:
    print(-1)
Buggy python submission (verdict: Runtime Error):
#145_D
x,y=map(int,input().split())
mod=10**9+7
if (x+y)%3!=0:
    print(0)
else:
    n=(2*x-y)//3
    m=(2*y-x)//3
    f=[1 for i in range(m+n+1)]
    for i in range(2,m+n+1):
        f[i]=f[i-1]*i%mod
    print(f[m+n]*pow(f[n],mod-2,mod)*pow(f[m],mod-2,mod)%mod)

Fixed submission:
#145_D
x,y=map(int,input().split())
mod=10**9+7
if (x+y)%3!=0:
    print(0)
else:
    n=(2*x-y)//3
    m=(2*y-x)//3
    if n<0 or m<0:
        print(0)
    else:
        f=[1 for i in range(m+n+1)]
        for i in range(2,m+n+1):
            f[i]=f[i-1]*i%mod
        print(f[m+n]*pow(f[n],mod-2,mod)*pow(f[m],mod-2,mod)%mod)
Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
inf = 10 ** 15
dp = [inf for _ in range(n)]
edges = []
for _ in range(m):
    l, r, c = map(int, input().split())
    edges.append((l-1, r-1, c))

edges.sort(key=lambda x: x[0])

dp[0] = 0
for l, r, c in edges:
    for i in range(l+1, r+1):
        dp[i] = min(dp[i], dp[l] + c)

print(dp[n-1] if dp[n-1] < inf else -1)

Fixed submission:
n, m = map(int, input().split())
inf = 10 ** 15
edges = [[] for _ in range(n)]
for _ in range(m):
    l, r, c = map(int, input().split())
    edges[l-1].append((r-1, c))
for i in range(n-1):
    edges[i+1].append((i, 0))

from heapq import heappop, heappush
d = [inf for _ in range(n)]
def dijkstra(s):
    que = []
    d[s] = 0
    heappush(que, (0, s))

    while len(que):
        dist, node = heappop(que)

        if d[node] < dist:
            continue
        for to, cost in edges[node]:
            if d[to] > dist + cost:
                d[to] = dist + cost
                heappush(que, (d[to], to))

dijkstra(0)

print(d[n-1] if d[n-1] != inf else -1)
Buggy python submission (verdict: Time Limit Exceeded):
#144_E
n, k = map(int, input().split())
a = sorted(list(map(int,input().split())))
f = sorted(list(map(int,input().split())))[::-1]

l, r = -1, 10 ** 12
while r - l > 1:
    x = (r + l) // 2
    
    res = 0
    for i in range(n):
        res += max(0, a[i] - x // f[i])
    
    if res > k:
        l = x
    else:
        r = x
print(r)

Fixed submission:
#144_E
n, k = map(int, input().split())
a = sorted(list(map(int,input().split())))
f = sorted(list(map(int,input().split())))[::-1]

l, r = -1, 10 ** 12
while r - l > 1:
    x = (r + l) // 2
    
    res = 0
    for i in range(n):
        res += max(0, a[i] - x // f[i])
    
    if res > k:
        l = x
    else:
        r = x
print(r)

Buggy python submission (verdict: Time Limit Exceeded):
#144_E
import heapq
n, k = map(int, input().split())
a = sorted(list(map(int,input().split())))
f = sorted(list(map(int,input().split())))[::-1]

cost = [(-a[i]*f[i], i) for i in range(n)]
heapq.heapify(cost)
for _ in range(k):
    x, idx = heapq.heappop(cost)
    if x == 0:
        break
    heapq.heappush(cost, (-(-x // f[idx] - 1) * f[idx], idx))
print(-heapq.heappop(cost)[0])    

Fixed submission:
#144_E
n, k = map(int, input().split())
a = sorted(list(map(int,input().split())))
f = sorted(list(map(int,input().split())))[::-1]

l, r = -1, 10 ** 12
while r - l > 1:
    x = (r + l) // 2
    
    res = 0
    for i in range(n):
        res += max(0, a[i] - x // f[i])
    
    if res > k:
        l = x
    else:
        r = x
print(r)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
n = int(input())
edges = [[] for _ in range(n)]

for i in range(n):
    s = input()
    for j in range(n):
        if s[j] == '1':
            edges[i].append(j)

#可能か
flg = True
l, r = set(), set()
l.add(0)
que = deque()
que.append((0, True))
is_left = True
while que and flg:
    cur, is_left = que.popleft()
    for to in edges[cur]:
        if is_left:
            if to in l:
                flg = False
            elif to not in r:
                r.add(to)
                que.append((to, False))
        else:
            if to in r:
                flg = False
            elif to not in l:
                l.add(to)
                que.append((to, True))

    if is_left:
        is_left = False
    else:
        is_left = True


if not flg:
    print(-1)

else:
    def warshall_floyd(d, v):
        for k in range(v):
            for i in range(v):
                for j in range(v):
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j])

    inf = 1000
    d = [[inf] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if j in edges[i]:
                d[i][j] = 1

    warshall_floyd(d, n)
    
    ans = 0
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            ans = max(ans, d[i][j]+1)

    print(ans)


Fixed submission:
from collections import deque
n = int(input())
edges = [[] for _ in range(n)]

for i in range(n):
    s = input()
    for j in range(n):
        if s[j] == '1':
            edges[i].append(j)

#可能か
flg = True
l, r = set(), set()
l.add(0)
que = deque()
que.append((0, True))
is_left = True
while que and flg:
    cur, is_left = que.popleft()
    for to in edges[cur]:
        if is_left:
            if to in l:
                flg = False
            elif to not in r:
                r.add(to)
                que.append((to, False))
        else:
            if to in r:
                flg = False
            elif to not in l:
                l.add(to)
                que.append((to, True))

    if is_left:
        is_left = False
    else:
        is_left = True


if not flg:
    print(-1)

else:
    def warshall_floyd(d, v):
        for k in range(v):
            for i in range(v):
                for j in range(v):
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j])

    inf = 1000
    d = [[inf] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if j in edges[i]:
                d[i][j] = 1

    warshall_floyd(d, n)
    
    ans = 0
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            ans = max(ans, d[i][j]+1)

    print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
#142_E
n, m = map(int, input().split())
inf = 10 ** 10
keys = [0 for _ in range(m)]
A = [] 

for i in range(m):
    a, _ = map(int, input().split())
    keys[i] = sum([2 ** (int(c) - 1) for c in input().split()])
    A.append(a)
    
dp = [[inf for _ in range(2 ** n)] for _ in range(m+1)]
dp[0][0] = 0
for i in range(0, m):
    for key in range(2 ** n):
        dp[i+1][key] = dp[i][key]
        
    for key in range(2 ** n):
        dp[i+1][key | keys[i]] = min(dp[i+1][key | keys[i]],
                                     dp[i][key] + A[i])

if dp[m][2 ** n - 1] == inf:
    print(-1)
else:
    print(dp[m][2 ** n - 1])

Fixed submission:
#142_E
n, m = map(int, input().split())
inf = 10 ** 10
keys = [0 for _ in range(m)]
A = [] 

for i in range(m):
    a, _ = map(int, input().split())
    keys[i] = sum([2 ** (int(c) - 1) for c in input().split()])
    A.append(a)
    
dp = [[inf for _ in range(2 ** n)] for _ in range(m+1)]
dp[0][0] = 0
for i in range(0, m):
    for key in range(2 ** n):
        dp[i+1][key] = dp[i][key]
        
    for key in range(2 ** n):
        dp[i+1][key | keys[i]] = min(dp[i+1][key | keys[i]],
                                     dp[i][key] + A[i])

if dp[m][2 ** n - 1] == inf:
    print(-1)
else:
    print(dp[m][2 ** n - 1])
Buggy python submission (verdict: Time Limit Exceeded):
#141_E
n = int(input())
s = input()

ans = 0
for l in range(1, n // 2 + 1):
    for i in range(0, n - 2 * l + 1):
        for j in range(i + l, n - l + 1):
            if s[i: i + l] == s[j: j + l]:
                ans = max(ans, l)
print(ans)

Fixed submission:
#141_E
n = int(input())
s = input()

x = 0
for i in range(n):
    s_ = s[:i+1]
    if s_[i - x:] in s_[: i - x]:
        x += 1

print(x)
Buggy python submission (verdict: Time Limit Exceeded):
#137_C
from collections import Counter
n = int(input())
s = [Counter(input()) for _ in range(n)]

ans = 0
for i in range(n):
    for j in range(i+1,n):
        if s[i] == s[j]:
            ans += 1
            
print(ans)

Fixed submission:
#137_C
from collections import Counter
n = int(input())
w = []
for _ in range(n):
    s = sorted(input())
    w.append(''.join(s))
w.sort()
w = Counter(w)
ans = 0
for t, idx in w.items():
    ans += idx * (idx - 1) // 2
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
#135_D
s=input()
mod=10**9+7

#dp[i][j]...i桁目までで余りがj
dp=[[0 for _ in range(13)] for _ in range(len(s)+1)]
dp[0][0]=1

for i in range(0,len(s)):
    if s[i]=='?':
        for j in range(13):
            for x in range(10):
                dp[i+1][(j*10+x)%13]+=dp[i][j]
                dp[i+1][(j*10+x)%13]%=mod
    else:
        x=int(s[i])
        for j in range(13):
            dp[i+1][(j*10+x)%13]+=dp[i][j]
            dp[i+1][(j*10+x)%13]%=mod
    
print(dp[len(s)][5])

Fixed submission:
#135_D
s=input()
mod=10**9+7

#dp[i][j]...i桁目までで余りがj
dp=[[0 for _ in range(13)] for _ in range(len(s)+1)]
dp[0][0]=1

for i in range(0,len(s)):
    if s[i]=='?':
        for j in range(13):
            for x in range(10):
                dp[i+1][(j*10+x)%13]+=dp[i][j]
                dp[i+1][(j*10+x)%13]%=mod
    else:
        x=int(s[i])
        for j in range(13):
            dp[i+1][(j*10+x)%13]+=dp[i][j]
            dp[i+1][(j*10+x)%13]%=mod
    
print(dp[len(s)][5])

Buggy python submission (verdict: Time Limit Exceeded):
#135_D
s=input()
mod=10**9+7

#dp[i][j]...i桁目までで余りがj
dp=[[0 for _ in range(13)] for _ in range(len(s)+1)]
dp[0][0]=1

for i in range(0,len(s)):
    if s[i]=='?':
        for j in range(13):
            for x in range(10):
                dp[i+1][(j*10+x)%13]+=dp[i][j]
    else:
        x=int(s[i])
        for j in range(13):
            dp[i+1][(j*10+x)%13]+=dp[i][j]
    
print(dp[len(s)][5]%mod)

Fixed submission:
#135_D
s=input()
mod=10**9+7

#dp[i][j]...i桁目までで余りがj
dp=[[0 for _ in range(13)] for _ in range(len(s)+1)]
dp[0][0]=1

for i in range(0,len(s)):
    if s[i]=='?':
        for j in range(13):
            for x in range(10):
                dp[i+1][(j*10+x)%13]+=dp[i][j]
                dp[i+1][(j*10+x)%13]%=mod
    else:
        x=int(s[i])
        for j in range(13):
            dp[i+1][(j*10+x)%13]+=dp[i][j]
            dp[i+1][(j*10+x)%13]%=mod
    
print(dp[len(s)][5])
Buggy python submission (verdict: Runtime Error):
#132_D
n,k=map(int,input().split())
mod=10**9+7

f=[1 for i in range(n-k+2)]
f_inv=[1 for i in range(n-k+2)]
for i in range(1,n-k+2):
    f[i]=f[i-1]*i%mod
    f_inv[i]=pow(f[i],mod-2,mod)
    
def comb(n,k):
    if k>n:
        return 0
    return f[n]*f_inv[k]*f_inv[n-k]%mod

for i in range(1,k+1):
    print(comb(n-k+1,i)*comb(k-1,i-1)%mod)

Fixed submission:
#132_D
n,k=map(int,input().split())
mod=10**9+7

f=[1 for i in range(n+2)]
f_inv=[1 for i in range(n+2)]
for i in range(1,n+2):
    f[i]=f[i-1]*i%mod
    f_inv[i]=pow(f[i],mod-2,mod)
    
def comb(n,k):
    if k>n:
        return 0
    return f[n]*f_inv[k]*f_inv[n-k]%mod

for i in range(1,k+1):
    print(comb(n-k+1,i)*comb(k-1,i-1)%mod)
Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
mod = 10 ** 9 + 7

dp = [[0] * (m+1) for _ in range(n+1)]
for i in range(n+1):
    dp[i][0] = 1
for j in range(m+1):
    dp[0][j] = 1

for i in range(1, n+1):
    for j in range(1, m+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % mod
        else:
            dp[i][j] = (dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]) % mod


print(dp[n][m])

Fixed submission:
n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
mod = 10 ** 9 + 7

dp = [[0] * (m+1) for _ in range(n+1)]
for i in range(n+1):
    dp[i][0] = 1
for j in range(m+1):
    dp[0][j] = 1

for i in range(1, n+1):
    for j in range(1, m+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % mod
        else:
            dp[i][j] = (dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]) % mod


print(dp[n][m])
Buggy python submission (verdict: Time Limit Exceeded):
#129_C
n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]
mod=10**9+7
dp=[1 for i in range(n+1)]
for i in range(1,n+1):
    if i in a:
        dp[i]=0
    elif i==1:
        dp[i]=dp[i-1]
    else:
        dp[i]=(dp[i-1]+dp[i-2])%mod
        
print(dp[n]%mod)

Fixed submission:
#129_C
n,m=map(int,input().split())
a={int(input()) for _ in range(m)}
mod=10**9+7
dp=[0 for i in range(n+1)]
dp[0]=1
for i in range(1,n+1):
    if i in a:
        dp[i]=0
    else:
        dp[i]=(dp[i-1]+dp[i-2])%mod
        
print(dp[n])

Buggy python submission (verdict: Runtime Error):
#129_C
n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]
mod=10**9+7
dp=[1 for i in range(n+1)]
for i in range(1,n+1):
    if i in a:
        dp[i]=0
    elif i==1:
        dp[i]=dp[i-1]
    else:
        dp[i]=(dp[i-1]+dp[i-2])%mid
        
print(dp[n]%mod)

Fixed submission:
#129_C
n,m=map(int,input().split())
a={int(input()) for _ in range(m)}
mod=10**9+7
dp=[0 for i in range(n+1)]
dp[0]=1
for i in range(1,n+1):
    if i in a:
        dp[i]=0
    else:
        dp[i]=(dp[i-1]+dp[i-2])%mod
        
print(dp[n])

Buggy python submission (verdict: Time Limit Exceeded):
#129_C
n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]
dp=[1 for i in range(n+1)]
for i in range(1,n+1):
    if i in a:
        dp[i]=0
    elif i==1:
        dp[i]=dp[i-1]
    else:
        dp[i]=dp[i-1]+dp[i-2]
        
print(dp[n]%(10**9+7))

Fixed submission:
#129_C
n,m=map(int,input().split())
a={int(input()) for _ in range(m)}
mod=10**9+7
dp=[0 for i in range(n+1)]
dp[0]=1
for i in range(1,n+1):
    if i in a:
        dp[i]=0
    else:
        dp[i]=(dp[i-1]+dp[i-2])%mod
        
print(dp[n])
Buggy python submission (verdict: Time Limit Exceeded):
#129_D
h, w = map(int, input().split())
s = [input() for _ in range(h)]

L = [[0]*w for _ in range(h)]
R = [[0]*w for _ in range(h)]
U = [[0]*w for _ in range(h)]
D = [[0]*w for _ in range(h)]

for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            continue
        elif j == 0:
            L[i][j] = 1
        else:
            L[i][j] = L[i][j-1] + 1
            
for i in range(h):
    for j in range(w-1, -1, -1):
        if s[i][j] == '#':
            continue
        elif j == w-1:
            R[i][j] = 1
        else:
            R[i][j] = R[i][j+1] + 1
            
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            continue
        elif i == 0:
            U[i][j] = 1
        else:
            U[i][j] = U[i-1][j] + 1
            
for i in range(h-1, -1, -1):
    for j in range(w):
        if s[i][j] == '#':
            continue
        elif i == h-1:
            D[i][j] = 1
        else:
            D[i][j] = D[i+1][j] + 1

ans = 0
for i in range(h):
    for j in range(w):
        x = L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3
        ans = max(ans, x)
        
print(ans)

Fixed submission:
#129_D
h, w = map(int, input().split())
s = [input() for _ in range(h)]

L = [[0]*w for _ in range(h)]
R = [[0]*w for _ in range(h)]
U = [[0]*w for _ in range(h)]
D = [[0]*w for _ in range(h)]

for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            continue
        elif j == 0:
            L[i][j] = 1
        else:
            L[i][j] = L[i][j-1] + 1
            
for i in range(h):
    for j in range(w-1, -1, -1):
        if s[i][j] == '#':
            continue
        elif j == w-1:
            R[i][j] = 1
        else:
            R[i][j] = R[i][j+1] + 1
            
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            continue
        elif i == 0:
            U[i][j] = 1
        else:
            U[i][j] = U[i-1][j] + 1
            
for i in range(h-1, -1, -1):
    for j in range(w):
        if s[i][j] == '#':
            continue
        elif i == h-1:
            D[i][j] = 1
        else:
            D[i][j] = D[i+1][j] + 1

ans = 0
for i in range(h):
    for j in range(w):
        x = L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3
        ans = max(ans, x)
        
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
#127_C
n, m = map(int, input().split())
s = set(range(1,n+1))

for _ in range(m):
    l, r = map(int, input().split())
    s &= set(range(l, r+1))

print(len(s))

Fixed submission:
#127_C
n, m = map(int, input().split())
L = []
R = []
for _ in range(m):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)
print(max(0, min(R)-max(L)+1))

Buggy python submission (verdict: Time Limit Exceeded):
#127_C
n, m = map(int, input().split())
s = set(range(1,n+1))

for _ in range(m):
    l, r = map(int, input().split())
    s &= set(range(l, r+1))

print(len(s))

Fixed submission:
#127_C
n, m = map(int, input().split())
L = []
R = []
for _ in range(m):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)
print(max(0, min(R)-max(L)+1))
Buggy python submission (verdict: Time Limit Exceeded):
#127_D
import heapq
n, m = map(int, input().split())
a = list(map(int, input().split()))
heapq.heapify(a)
for _ in range(m):
    b, c = map(int, input().split())
    for i in range(b):
        if c > a[0]:
            heapq.heappop(a)
            heapq.heappush(a, c)
print(sum(a))

Fixed submission:
#127_D
n, m = map(int, input().split())
a = list(map(int, input().split()))
bc = [(1, a[i]) for i in range(n)]+[tuple(map(int, input().split())) for _ in range(m)]
bc.sort(key= lambda x: -x[1])

tmp = 0
ans = 0
for b, c in bc:
    x = min(b, n-tmp)
    ans += c * x
    tmp += x
    
    if tmp == n:
        break

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
#127_D
import heapq
n, m = map(int, input().split())
a = list(map(int, input().split()))
heapq.heapify(a)
for _ in range(m):
    b, c = map(int, input().split())
    for i in range(b):
        if c > a[0]:
            heapq.heappop(a)
            heapq.heappush(a, c)
print(sum(a))

Fixed submission:
#127_D
n, m = map(int, input().split())
a = list(map(int, input().split()))
bc = [(1, a[i]) for i in range(n)]+[tuple(map(int, input().split())) for _ in range(m)]
bc.sort(key= lambda x: -x[1])

tmp = 0
ans = 0
for b, c in bc:
    x = min(b, n-tmp)
    ans += c * x
    tmp += x
    
    if tmp == n:
        break

print(ans)
Buggy python submission (verdict: Runtime Error):
#126_D
n=int(input())
edges=[[] for _ in range(n)]
for _ in range(n-1):
    u,v,w=map(int,input().split())
    edges[u-1].append((v-1,w))
    edges[v-1].append((u-1,w))
visit=[False for _ in range(n)]
d=[0 for i in range(n)]

def dfs(i):
    visit[i]=True
    if all(visit[i] for i in range(n)):
        print(*d,sep='\n')
        exit()
    for v,w in edges[i]:
        if visit[v]==False:
            d[v]=(d[i]+w)%2
            dfs(v)
            
dfs(0)

Fixed submission:
#126_D
import sys
sys.setrecursionlimit(500000)

n=int(input())
edges=[[] for _ in range(n)]
for _ in range(n-1):
    u,v,w=map(int,input().split())
    edges[u-1].append((v-1,w))
    edges[v-1].append((u-1,w))
visit=[False for _ in range(n)]
d=[0 for i in range(n)]

def dfs(i):
    visit[i]=True
    if all(visit[i] for i in range(n)):
        print(*d,sep='\n')
        exit()
    for v,w in edges[i]:
        if visit[v]==False:
            d[v]=(d[i]+w)%2
            dfs(v)
            
dfs(0)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
h, w = map(int, input().split())
a = [input() for _ in range(h)]
inf = 10 ** 7

def bfs(sx, sy):
    d = [[inf for _ in range(w)] for _ in range(h)]
    d[sx][sy] = 0
    que = deque()
    que.append((sx, sy))

    while que:
        px, py = que.popleft()
        if a[px][py] == '#':
            return d[px][py]
        for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            qx, qy = px + dx, py + dy
            if 0 <= qx < h and 0 <= qy < w:
                if d[qx][qy] > d[px][py] + 1:
                    d[qx][qy] = d[px][py] + 1
                    que.append((qx, qy))

ans = 0
for i in range(h):
    for j in range(w):
        if a[i][j] == '.':
            ans = max(ans, bfs(i, j))

print(ans)

Fixed submission:
from collections import deque
h, w = map(int, input().split())
a = [input() for _ in range(h)]
inf = 10 ** 7

d = [[inf for _ in range(w)] for _ in range(h)]
que = deque()

for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            que.append((i, j))
            d[i][j] = 0

while que:
    px, py = que.popleft()
    for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        qx, qy = px + dx, py + dy
        if 0 <= qx < h and 0 <= qy < w:
            if d[qx][qy] > d[px][py] + 1:
                d[qx][qy] = d[px][py] + 1
                que.append((qx, qy))

ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, d[i][j])

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
#124_D
N,K=map(int,input().split())
S=input()
cnt=[]
if S[0]=='0':
    cnt.append(0)
res=1
for i in range(1,N):
    if S[i-1]==S[i]:
        res+=1
    else:
        cnt.append(res)
        res=1
cnt.append(res)
if S[-1]=='0':
    cnt.append(0)

ans=0
for i in range(0,len(cnt),2):
    res=sum(cnt[i:i+2*K+1])
    ans=max(ans,res)
    
print(ans)

Fixed submission:
#124_D
N,K=map(int,input().split())
S=input()
cnt=[]
if S[0]=='0':
    cnt.append(0)
res=1
for i in range(1,N):
    if S[i-1]==S[i]:
        res+=1
    else:
        cnt.append(res)
        res=1
cnt.append(res)
if S[-1]=='0':
    cnt.append(0)

cnt_sum=[0]
for i in range(len(cnt)):
    tmp=cnt_sum[i]+cnt[i]
    cnt_sum.append(tmp)
    
ans=1
for i in range(0,len(cnt_sum),2):
    res=cnt_sum[min(len(cnt_sum)-1,2*K+1+i)]-cnt_sum[i]
    ans=max(ans,res)
    
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
#124_D
N,K=map(int,input().split())
S=input()
cnt=[]
if S[0]=='0':
    cnt.append(0)
res=1
for i in range(1,N):
    if S[i-1]==S[i]:
        res+=1
    else:
        cnt.append(res)
        res=1
cnt.append(res)
if S[-1]=='0':
    cnt.append(0)

ans=0
for i in range(0,len(cnt),2):
    res=sum(cnt[i:i+2*K+1])
    ans=max(ans,res)
    
print(ans)

Fixed submission:
#124_D
N,K=map(int,input().split())
S=input()
cnt=[]
if S[0]=='0':
    cnt.append(0)
res=1
for i in range(1,N):
    if S[i-1]==S[i]:
        res+=1
    else:
        cnt.append(res)
        res=1
cnt.append(res)
if S[-1]=='0':
    cnt.append(0)

cnt_sum=[0]
for i in range(len(cnt)):
    tmp=cnt_sum[i]+cnt[i]
    cnt_sum.append(tmp)
    
ans=1
for i in range(0,len(cnt_sum),2):
    res=cnt_sum[min(len(cnt_sum)-1,2*K+1+i)]-cnt_sum[i]
    ans=max(ans,res)
    
print(ans)