Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**8)

# ナップザック問題 典型2
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for i in range(N)]
V = sum([v for w, v in wv])

dp = [[10**10]*(V+1) for i in range(N+1)]
dp[0][0] = 0

for i in range(N):
    for j in range(0, V+1):
        w, v = wv[i]
        if (j-v) >= 0:
            dp[i+1][j] = min([dp[i][j], dp[i][j-v]+w])
        else:
            dp[i+1][j] = dp[i][j]

ans = 0
for i in range(0, V+1):
    if dp[N][i] <= W:
        ans = i

print(ans)


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

# ナップザック問題 典型2
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for i in range(N)]
V = sum([v for w, v in wv])

dp = [[10**10]*(V+1) for i in range(N+1)]
dp[0][0] = 0

for i in range(N):
    for j in range(0, V+1):
        w, v = wv[i]
        if (j-v) >= 0:
            dp[i+1][j] = min([dp[i][j], dp[i][j-v]+w])
        else:
            dp[i+1][j] = dp[i][j]

ans = 0
for i in range(0, V+1):
    if dp[N][i] <= W:
        ans = i

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
s = input().strip()
t = input().strip()
ls = len(s)
lt = len(t)

dp = [[0]*(lt+1) for i in range(ls+1)]

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

ans = ''
i, j = ls, lt
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]+ans
        i -= 1
        j -= 1

print(ans)

Fixed submission:
s = input().strip()
t = input().strip()
ls = len(s)
lt = len(t)

dp = [[0]*(lt+1) for i in range(ls+1)]

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

ans = ''
i, j = ls, lt
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]+ans
        i -= 1
        j -= 1

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**8)

s = input().strip()
t = input().strip()
ls = len(s)
lt = len(t)

dp = [['']*lt for i in range(ls)]


def answer(si, ti):
    if si == ls or ti == lt:
        return ''

    if dp[si][ti] != '':
        return dp[si][ti]

    if s[si] == t[ti]:
        return s[si]+answer(si+1, ti+1)

    a = answer(si+1, ti)
    b = answer(si, ti+1)
    r = a if len(a) > len(b) else b
    dp[si][ti] = r
    return dp[si][ti]


print(answer(0, 0))


Fixed submission:
s = input().strip()
t = input().strip()
ls = len(s)
lt = len(t)

dp = [[0]*(lt+1) for i in range(ls+1)]

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

ans = ''
i, j = ls, lt
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]+ans
        i -= 1
        j -= 1

print(ans)
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict

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

h = defaultdict(list)
for i in range(M):
    x, y = map(int, input().split())
    h[x-1].append(y-1)

dp = [0]*(N+1)


def dist(v):
    if dp[v] > 0:
        return dp[v]
    dp[v] = 0
    for nv in h[v]:
        dp[v] = max([dp[v], dist(nv)+1])
    return dp[v]


ans = 0
for v in range(N):
    ans = max([ans, dist(v)])

print(ans)


Fixed submission:
from collections import defaultdict
import sys
sys.setrecursionlimit(10**8)

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

h = defaultdict(list)
for i in range(M):
    x, y = map(int, input().split())
    h[x-1].append(y-1)

dp = [0]*N


def dist(v):
    if dp[v] > 0:
        return dp[v]
    dp[v] = 0
    for nv in h[v]:
        dp[v] = max([dp[v], dist(nv)+1])
    return dp[v]


ans = 0
for v in range(N):
    ans = max([ans, dist(v)])

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**8)

N = int(input())
*a, = map(int, input().split())
dp = [[0]*(N+1) for _ in range(N+1)]

'''
for l in range(1, N+1):
    for i in range(N-l+1):
        j = i+l
        if (N-l) % 2 == 0:
            # first
            dp[i][j] = max([dp[i+1][j]+a[i], dp[i][j-1]+a[j-1]])
        else:
            # second
            dp[i][j] = min([dp[i+1][j]-a[i], dp[i][j-1]-a[j-1]])

print(dp[0][N])
'''


def solve(l, r):
    if l >= r:
        return 0
    if dp[l][r] > 0:
        return dp[l][r]

    t = N-(r-l)
    if t % 2 == 0:
        dp[l][r] = max([solve(l+1, r)+a[l], solve(l, r-1)+a[r-1]])
    else:
        dp[l][r] = min([solve(l+1, r)-a[l], solve(l, r-1)-a[r-1]])
    return dp[l][r]


print(solve(0, N))


Fixed submission:
N = int(input())
*a, = map(int, input().split())
dp = [[0]*(N+1) for _ in range(N+1)]

for l in range(1, N+1):
    for i in range(N-l+1):
        j = i+l
        if (N-l) % 2 == 0:
            # first
            dp[i][j] = max([dp[i+1][j]+a[i], dp[i][j-1]+a[j-1]])
        else:
            # second
            dp[i][j] = min([dp[i+1][j]-a[i], dp[i][j-1]-a[j-1]])

print(dp[0][N])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**8)

N = int(input())
*a, = map(int, input().split())

s = [0]*N
s[0] = a[0]
for i in range(1, N):
    s[i] += s[i-1]+a[i]
s = [0]+s

dp = [[0]*(N+1) for _ in range(N+1)]


def solve(l, r):
    if l == r:
        return 0
    if dp[l][r] > 0:
        return dp[l][r]

    n = float('inf')
    m = s[r+1]-s[l]
    for i in range(l, r):
        n = min([n, solve(l, i)+solve(i+1, r)+m])
    dp[l][r] = n
    return n


print(solve(0, N-1))


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

N = int(input())
*a, = map(int, input().split())

s = [0]*N
s[0] = a[0]
for i in range(1, N):
    s[i] += s[i-1]+a[i]
s = [0]+s

dp = [[0]*(N+1) for _ in range(N+1)]


def solve(l, r):
    if l == r:
        return 0
    if dp[l][r] > 0:
        return dp[l][r]

    n = float('inf')
    m = s[r+1]-s[l]
    for i in range(l, r):
        n = min([n, solve(l, i)+solve(i+1, r)+m])
    dp[l][r] = n
    return n


print(solve(0, N-1))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**8)

N = int(input())
*a, = map(int, input().split())

s = [0]*N
s[0] = a[0]
for i in range(1, N):
    s[i] += s[i-1]+a[i]
s = [0]+s

dp = [[0]*(N+1) for _ in range(N+1)]


def solve(l, r):
    if l == r:
        return 0
    if dp[l][r] > 0:
        return dp[l][r]

    n = float('inf')
    m = s[r+1]-s[l]
    for i in range(l, r):
        n = min([n, solve(l, i)+solve(i+1, r)+m])
    dp[l][r] = n
    return n


print(solve(0, N-1))


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

N = int(input())
*a, = map(int, input().split())

s = [0]*N
s[0] = a[0]
for i in range(1, N):
    s[i] += s[i-1]+a[i]
s = [0]+s

dp = [[0]*(N+1) for _ in range(N+1)]


def solve(l, r):
    if l == r:
        return 0
    if dp[l][r] > 0:
        return dp[l][r]

    n = float('inf')
    m = s[r+1]-s[l]
    for i in range(l, r):
        n = min([n, solve(l, i)+solve(i+1, r)+m])
    dp[l][r] = n
    return n


print(solve(0, N-1))
Buggy python submission (verdict: Runtime Error):
N = int(input())
*a, = map(int, input().split())
M = 10**5+1
b = [0]*(M+1)
for i in range(N):
    b[a[i]] += 1
ans = 0
for i in range(1, M+1):
    if i > b[i]:
        ans += b[i]
    elif i < b[i]:
        ans += b[i]-i
print(ans)


Fixed submission:
from collections import defaultdict
N = int(input())
*a, = map(int, input().split())
b = defaultdict(int)
for i in range(N):
    b[a[i]] += 1
ans = 0
for i, v in b.items():
    if i > b[i]:
        ans += b[i]
    elif i < b[i]:
        ans += b[i]-i
print(ans)

Buggy python submission (verdict: Runtime Error):
N = int(input())
*a, = map(int, input().split())
b = [0]*(N+1)
for i in range(N):
    b[a[i]] += 1
ans = 0
for i in range(1, N+1):
    if i > b[i]:
        ans += b[i]
    elif i < b[i]:
        ans += b[i]-i
print(ans)


Fixed submission:
from collections import defaultdict
N = int(input())
*a, = map(int, input().split())
b = defaultdict(int)
for i in range(N):
    b[a[i]] += 1
ans = 0
for i, v in b.items():
    if i > b[i]:
        ans += b[i]
    elif i < b[i]:
        ans += b[i]-i
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
A, B, C, D, E, F = map(int, input().split())
a, b = [], []

for i in range(31):
    for j in range(31):
        v = 100*A*i+100*B*j
        if v < F:
            a.append(v)
        else:
            break

for i in range(3000//C+2):
    for j in range(3000//D+2):
        v = C*i+D*j
        if v < F:
            b.append(v)
        else:
            break

a.sort()
b.sort()

c = 0
ans = [0, 0]
for ai in a:
    for bi in b:
        t = ai+bi
        if t > 0 and t <= F and (E*ai//100) >= bi:
            tc = 100*bi/(ai+bi)
            if c < tc:
                c = tc
                ans = [t, bi]
if c == 0:
    while True:
        c = 0
print(*ans)


Fixed submission:
A, B, C, D, E, F = map(int, input().split())
a, b = [], []

for i in range(3001):
    for j in range(3001):
        v = 100*A*i+100*B*j
        if v <= F:
            a.append(v)
        else:
            break

for i in range(3001):
    for j in range(3001):
        v = C*i+D*j
        if v <= F:
            b.append(v)
        else:
            break

a.sort()
b.sort()

c = -1
ans = [0, 0]
for ai in a:
    for bi in b:
        t = ai+bi
        if t > 0 and t <= F and (E*ai//100) >= bi:
            tc = 100*bi/(ai+bi)
            if c < tc:
                c = tc
                ans = [t, bi]

print(*ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
*a, = map(int, input().split())
two, four, no = [], [], []
for i in range(N):
    if a[i] % 4 == 0:
        four += 1
    elif a[i] % 2 == 0:
        two += 1
    else:
        no += 1

ok = (two >= max(0, (N-4)) and four >= 2) or four >= N//2
ok = ok and ((four-no) >= 2 or ((four+no) == N and (no-four) <= 1))
if ok:
    print("Yes")
else:
    print("No")


Fixed submission:
N = int(input())
*a, = map(int, input().split())
two, four, no = 0, 0, 0
for i in range(N):
    if a[i] % 4 == 0:
        four += 1
    elif a[i] % 2 == 0:
        two += 1
    else:
        no += 1

ok = four == no or (four+two) == N
ok = ok or ((four+no) == N and abs(four-no) <= 1)
if ok:
    print("Yes")
else:
    print("No")
Buggy python submission (verdict: Runtime Error):
import copy
N, M = map(int, input().split())
dp = [[float('inf')]*N for _ in range(N)]

for i in range(N):
    dp[i][i] = 0

for i in range(M):
    a, b, c = map(int, input().split())
    dp[a-1][b-1] = c
    dp[b-1][a-1] = c

g = copy.deepcopy(dp)

# ワーシャルフロイド
for k in range(N):
    for i in range(N):
        for j in range(N):
            dp[i][j] = min([dp[i][j], dp[i][k]+dp[k][j]])


# 経路復元
p = {}
for i in range(N):
    for j in range(i+1, N):
        c = i
        while c != j:
            for k in range(N):
                if k != c and (g[c][k]+dp[k][j]) == dp[c][j]:
                    p[(c, k) if c < k else (k, c)] = 1
                    c = k
                    break
print(max([0, M-len(p)))


Fixed submission:
import copy
N, M = map(int, input().split())
dp = [[float('inf')]*N for _ in range(N)]
ms = []
for i in range(N):
    dp[i][i] = 0

for i in range(M):
    a, b, c = map(int, input().split())
    dp[a-1][b-1] = c
    dp[b-1][a-1] = c
    ms.append([a-1, b-1, c])

g = copy.deepcopy(dp)

# ワーシャルフロイド
for k in range(N):
    for i in range(N):
        for j in range(N):
            dp[i][j] = min([dp[i][j], dp[i][k]+dp[k][j]])

# 全頂点でmが使われたかどうか
ans = M
for m in ms:
    a, b, c = m
    for n in range(N):
        if dp[n][b] == (dp[n][a]+c):
            ans -= 1
            break
print(ans)

Buggy python submission (verdict: Runtime Error):
import copy
N, M = map(int, input().split())
dp = [[float('inf')]*N for _ in range(N)]

for i in range(N):
    dp[i][i] = 0

for i in range(M):
    a, b, c = map(int, input().split())
    dp[a-1][b-1] = c
    dp[b-1][a-1] = c

g = copy.deepcopy(dp)

# ワーシャルフロイド
for k in range(N):
    for i in range(N):
        for j in range(N):
            dp[i][j] = min([dp[i][j], dp[i][k]+dp[k][j]])


# 経路復元
p = {}
for i in range(N):
    for j in range(N):
        c = i
        while c != j:
            for k in range(N):
                if k != c and (g[c][k]+dp[k][j]) == dp[c][j]:
                    p[(c, k) if c < k else (k, c)] = 1
                    c = k
                    break
print(max([0, M-len(p)))


Fixed submission:
import copy
N, M = map(int, input().split())
dp = [[float('inf')]*N for _ in range(N)]
ms = []
for i in range(N):
    dp[i][i] = 0

for i in range(M):
    a, b, c = map(int, input().split())
    dp[a-1][b-1] = c
    dp[b-1][a-1] = c
    ms.append([a-1, b-1, c])

g = copy.deepcopy(dp)

# ワーシャルフロイド
for k in range(N):
    for i in range(N):
        for j in range(N):
            dp[i][j] = min([dp[i][j], dp[i][k]+dp[k][j]])

# 全頂点でmが使われたかどうか
ans = M
for m in ms:
    a, b, c = m
    for n in range(N):
        if dp[n][b] == (dp[n][a]+c):
            ans -= 1
            break
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
class UnionFindTree:
    def __init__(self):
        self.p = {}
        self.rank = {}

    def make(self, x):
        self.p[x] = x
        self.rank[x] = 0

    def find(self, x):
        if x in self.p:
            if self.p[x] != x:
                # 経路圧縮
                self.p[x] = self.find(self.p[x])
            return self.p[x]
        return None

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

    def unite(self, x, y):
        return self._unite(self.find(x), self.find(y))

    def _unite(self, x, y):
        if self.rank[x] < self.rank[y]:
            self.p[x] = y
            return y
        else:
            self.p[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            return x


N, K, L = map(int, input().split())

utf1 = UnionFindTree()
utf2 = UnionFindTree()
for i in range(N):
    utf1.make(i+1)
    utf2.make(i+1)

for i in range(K):
    p, q = map(int, input().split())
    utf1.unite(p, q)
for i in range(L):
    r, s = map(int, input().split())
    utf2.unite(r, s)

ans = [0]*N
for i in range(1, N+1):
    for j in range(1, N+1):
        a = utf1.same(i, j)
        b = utf2.same(i, j)
        if a and a == b:
            ans[i-1] += 1
print(" ".join([str(_) for _ in ans]))


Fixed submission:
from collections import Counter


class UnionFindTree:
    def __init__(self):
        self.p = {}
        self.rank = {}

    def make(self, x):
        self.p[x] = x
        self.rank[x] = 0

    def find(self, x):
        if x in self.p:
            if self.p[x] != x:
                # 経路圧縮
                self.p[x] = self.find(self.p[x])
            return self.p[x]
        return None

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

    def unite(self, x, y):
        return self._unite(self.find(x), self.find(y))

    def _unite(self, x, y):
        if self.rank[x] < self.rank[y]:
            self.p[x] = y
            return y
        else:
            self.p[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            return x


N, K, L = map(int, input().split())

utf1 = UnionFindTree()
utf2 = UnionFindTree()
for i in range(N):
    utf1.make(i+1)
    utf2.make(i+1)

for i in range(K):
    p, q = map(int, input().split())
    utf1.unite(p, q)
for i in range(L):
    r, s = map(int, input().split())
    utf2.unite(r, s)

pairs = [(utf1.find(i+1), utf2.find(i+1)) for i in range(N)]
counts = Counter(pairs)
print(" ".join([str(counts[k]) for k in pairs]))
Buggy python submission (verdict: Time Limit Exceeded):
h,w,a,b=map(int,input().split())
ans = 0

mod = 10**9 + 7
flist = [1] * (h+w+1)
for i in range(1,h+w):
    flist[i] = (flist[i-1] * i)

def cmb(n,r):
    return flist[n]//(flist[r]*flist[n-r])

for x in range(b,w):
    c = x + (h - a - 1)
    d = (w - x - 1) + (a - 1)
    e = cmb(c, x) * cmb(d, a - 1)
    ans = (ans+e)%mod

print(ans)

Fixed submission:
h,w,a,b=map(int,input().split())
ans = 0

mod = 10**9 + 7
fac = [1] * (h+w+1)
inv = [1] * (h+w+1)
for i in range(1,h+w):
    fac[i] = (fac[i-1] * i)%mod
    inv[i] = pow(fac[i], mod-2, mod)

def cmb(n,r):
    return fac[n] * inv[r] * inv[n-r] % mod
    
for x in range(b,w):
    c = x + (h - a - 1)
    d = (w - x - 1) + (a - 1)
    e = cmb(c, x) * cmb(d, a - 1)
    ans = (ans+e)%mod

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n, k = map(int, input().split())
    mod = 998244353
    dp = [0] * (n + 1)
    dp[1] = 1
    delta = []
    for _ in range(k):
        l, r = map(int, input().split())
        for i in range(l, r + 1):
            delta.append(i)
    delta.sort()
    for i in range(n):
        for d in delta:
            if i + d > n:
                break
            dp[i + d] += dp[i]
            dp[i + d] %= mod
    print(dp[n])


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    n, k = map(int, input().split())
    mod = 998244353
    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = -1
    left = [0] * k
    right = [0] * k
    for i in range(k):
        left[i], right[i] = map(int, input().split())
        right[i] += 1
    for i in range(1, n + 1):
        dp[i] += dp[i - 1]
        for j in range(k):
            if i + left[j] <= n:
                dp[i + left[j]] += dp[i]
            if i + right[j] <= n:
                dp[i + right[j]] -= dp[i]
        dp[i] %= mod
    print(dp[n])


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    h, w, m = map(int, input().split())
    height = [0 for _ in range(h)]
    width = [0 for _ in range(w)]
    target = set()
    for _ in range(m):
        x, y = map(lambda x: int(x) - 1, input().split())
        target.add((x, y))
        height[x] += 1
        width[y] += 1
    ans = 0
    for i in range(h):
        for j in range(w):
            now_ans = height[i] + width[j]
            if (i, j) in target:
               now_ans -= 1
            ans = max(ans, now_ans)
    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
def max_bomb_set(l):
    l.sort(key=lambda x: x[0], reverse=True)
    res = []
    for cnt, tag in l:
        if cnt == l[0][0]:
            res.append(tag)
        else:
            break
    return res, l[0][0]


def main():
    h, w, m = map(int, input().split())
    height = [[0, i] for i in range(h)]
    width = [[0, i] for i in range(w)]
    target = set()
    for _ in range(m):
        x, y = map(lambda x: int(x) - 1, input().split())
        target.add((x, y))
        height[x][0] += 1
        width[y][0] += 1
    max_height, max_h_val = max_bomb_set(height)
    max_width, max_w_val = max_bomb_set(width)
    ans = max_h_val + max_w_val
    for hh in max_height:
        for ww in max_width:
            if (hh, ww) not in target:
                return ans
    return ans - 1


if __name__ == '__main__':
    print(main())
Buggy python submission (verdict: Time Limit Exceeded):
from math import floor, ceil


def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    lower = 1
    upper = a[-1]
    while upper - lower >= 0.25 or floor(upper) != floor(lower):
        target = (lower + upper) / 2
        now = 0
        for i in range(n):
            now += ceil(a[i] / target) - 1
        if now > k:
            lower = target
        else:
            upper = target
    print(ceil(lower) if k > 0 else a[-1])


if __name__ == '__main__':
    main()



Fixed submission:
from math import ceil


def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    ng = 0
    ok = 10 ** 9 + 7
    while ok - ng > 1:
        mid = (ok + ng) // 2
        cnt = 0
        for i in range(n):
            cnt += (a[i] - 1) // mid
        if cnt <= k:
            ok = mid
        else:
            ng = mid
    print(ceil(ok) if k > 0 else a[-1])


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
from math import floor, ceil


def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    lower = 1
    upper = a[-1]
    for _ in range(10000):
        target = (lower + upper) / 2
        now = 0
        for i in range(n):
            now += ceil(a[i] / target) - 1
        if now > k:
            lower = target
        else:
            upper = target
    print(ceil(lower) if k > 0 else a[-1])


if __name__ == '__main__':
    main()



Fixed submission:
from math import ceil


def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    ng = 0
    ok = 10 ** 9 + 7
    while ok - ng > 1:
        mid = (ok + ng) // 2
        cnt = 0
        for i in range(n):
            cnt += (a[i] - 1) // mid
        if cnt <= k:
            ok = mid
        else:
            ng = mid
    print(ceil(ok) if k > 0 else a[-1])


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    op = 0
    while True:
        new = [0 for _ in range(n + 1)]
        for i in range(n):
            new[max(0, i - a[i])] += 1
            new[min(n, i + a[i] + 1)] -= 1
        for i in range(1, n + 1):
            new[i] += new[i - 1]
        a = new[:-1]
        op += 1
        if op == k or all(aa == n for aa in a):
            break
    print(" ".join(map(str, a)))


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    op = 0
    while True:
        new = [0 for _ in range(n + 1)]
        for i in range(n):
            new[max(0, i - a[i])] += 1
            new[min(n, i + a[i] + 1)] -= 1
        for i in range(1, n + 1):
            new[i] += new[i - 1]
        a = new[:-1]
        op += 1
        if op == k or all(aa == n for aa in a):
            break
    print(" ".join(map(str, a)))


if __name__ == '__main__':
    main()