Problem:


Score : 500 points

Problem Statement

We have N bulbs arranged on a number line, numbered 1 to N from left to right.
Bulb i is at coordinate i.

Each bulb has a non-negative integer parameter called intensity.
When there is a bulb of intensity d at coordinate x, the bulb illuminates the segment from coordinate x-d-0.5 to x+d+0.5.
Initially, the intensity of Bulb i is A_i. We will now do the following operation K times in a row:

For each integer i between 1 and N (inclusive), let B_i be the number of bulbs illuminating coordinate i. Then, change the intensity of each bulb i to B_i.

Find the intensity of each bulb after the K operations.

Constraints

1 \leq N \leq 2 \times 10^5

1 \leq K \leq 2 \times 10^5

0 \leq A_i \leq N

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 \ldots A_N

Output

Print the intensity A{'}_i of each bulb i after the K operations to Standard Output in the following format:

A{'}_1 A{'}_2 \ldots A{'}_N

Sample Input 1

5 1
1 0 0 1 0

Sample Output 1

1 2 2 1 2 

Initially, only Bulb 1 illuminates coordinate 1, so the intensity of Bulb 1 becomes 1 after the operation.
Similarly, the bulbs initially illuminating coordinate 2 are Bulb 1 and 2, so the intensity of Bulb 2 becomes 2.

Sample Input 2

5 2
1 0 0 1 0

Sample Output 2

3 3 4 4 3 



Sample input:
5 1
1 0 0 1 0


Sample output:
1 2 2 1 2

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
N, K = map(int, input().split())
A = list(map(int, input().split()))

i = 0
for i in range(K):
    K -= 1
    B = [0] * (N + 1)
    for i, a in enumerate(A):
        j = max(0, i - a)
        B[j] += 1
        j = min(N, i + a + 1)
        B[j] -= 1
    B.pop()
    A = list(accumulate(B))
    tmp = A[0]
    if all(a == tmp for a in A):
        break

print(*A)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#solve
def solve():
    n, k = LI()
    a = LI()
    for i in range(k):
        bit = [0] * (n+1)
        for j in range(n):
            bit[max(0, j - a[j])] += 1
            bit[min(n, j + a[j] + 1)] -= 1
        f = 0
        bit = list(itertools.accumulate(bit))
        for j in range(n):
            a[j] = bit[j]
            if a[j] < n:
                f = 1
        if f:
            print(bit[0])
            continue
        break
    print(*a)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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

def light_change(A):
    B=[0 for _ in range(len(A))]
    for i in range(len(A)):
        for j in range(max(0,i-A[i]),min(len(A),i+A[i]+1)):
            B[j]+=1
    return B
  
for _ in range(K):
  A=light_change(A)
print(A)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
A = list(map(int,input().split()))

for i in range(k):
    B = [0]*n
    for a in range(n):
        j = A[a]
        l = a - j
        if l < 0:
            l = 0
        r = a + j
        if r > n-1:
            r = n-1
        for k in range(l,r+1):
            B[k] += 1
    A = B[:]

print(A)

Submission status: Wrong Answer

Solution code:
import sys
from copy import deepcopy
n, k = map(int, input().split())
a = list(map(int, input().split()))

for _ in range(k):
    if a[0] == n and a[-1] == n:
        if sum(a) == n*n:
            print(a)
            sys.exit()
    b = [0]*n
    for i in range(n):
        b[i] += 1
        for j in range(1, a[i]+1):
            if i-j >= 0: b[i-j] += 1
            if i+j < n: b[i+j] += 1
    a = deepcopy(b)
print(a)

Submission status: Wrong Answer

Solution code:
import sys
def input():return sys.stdin.readline()[:-1]
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
n,k=NM()
l=L()
dp=[]
from itertools import accumulate
for _ in range(min(20,k)):
    tl,l=l,[0]*(n+1)
    for i,j in enumerate(tl):
        l[max(0,i-j)]+=1
        l[min(n,i+j+1)]-=1
    l=list(accumulate(l))
print(" ".join(map(str,l[:n])))

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
a = list(map(int, input().split()))
print(a[0])
b = []

for k in range(K):
    b = [0 for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if i - a[i]<= j and j <= i+a[i]:
                b[j] += 1
    for i in range(N):
        a[i] = b[i]
print(a)

Submission status: Wrong Answer

Solution code:
N , K = map(int,input().split())
Lum = [a for a in map(int,input().split())]

for i1 in range(K):
    B = [0 for i in range(N)]
    for i in range(N):
        for j in range(max(0,i-Lum[i]),min(i+Lum[i]+1,N)):
            B[j]+=1
    Lum = B
print(Lum)

Submission status: Wrong Answer

Solution code:
n,k,*a = map(int,open(0).read().split())
print(n,k,a)
for _ in range(k):
  b = [0]*n
  for i in range(n):
    for j in range(max(0,i-a[i]),min(n,i+a[i]+1)):
      b[j]+=1
  a = b
print(a,b)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop

N, K = map(int, input().split())
A = [int(i) for i in input().split()]

while K and sum(A) < N * N :
  l = [0] * N
  h = []
  for i in range(N) :
    while h and h[0] < i :
      heappop(h)
    l[i] = len(h)
    heappush(h, (i + A[i]))
    
  r = [0] * N
  h = []
  for i in range(N - 1, -1, -1) :
    while h and h[0] > i :
      heappop(h)
    r[i] = len(h)
    heappush(h, (i - A[i]))
    
  for i in range(N) :
    A[i] = l[i] + r[i] + 1
    
  K -= 1
  
print(*A)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

n, k, *aaa = map(int, sys.stdin.buffer.read().split())
aaa = np.array(aaa, dtype=np.int64)

if (aaa == 0).all():
    print(*aaa)
    exit()

for _ in range(k):
    bbb = np.zeros(n, dtype=np.int64)
    for i in range(n):
        a = aaa[i]
        bbb[max(0, i - a):i + a + 1] += 1
    aaa = bbb

    if (aaa == n).all():
        break

print(*aaa)

Submission status: Wrong Answer

Solution code:
import collections
n,k = map(int, raw_input().split(' '))
ais = map(int ,raw_input().split(' '))
cc = collections.Counter(ais)

for e in ais:
	print cc[e],

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
from numba import njit

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


@njit('i8[:](i8,i8,i8[:])', cache=True)
def func(n, k, A):
    for _ in range(k):
        B = np.zeros(n + 1, np.int64)
        for i, a in enumerate(A):
            B[max(0, i - a)] += 1
            B[min(i + a + 1, n)] -= 1
        A = B.cumsum()[:-1]
    return A


def main():
    N, K = map(int, readline().split())
    A = np.array(readline().split(), np.int64)
    ans = func(N, K, A)
    print(*ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N, K = map(int, readline().split())
    np.set_printoptions(precision=0)
    A = np.array(readline().split(), np.int64)
    for _ in range(K):
        B = np.zeros(N + 1)
        for i, a in enumerate(A):
            B[max(0, int(i - a))] += 1
            B[min(int(i + a + 1), N)] -= 1
        B = B.cumsum()
        A = np.copy(B[:N])
    print(' '.join(map(str, list(map(int, A)))))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
A = list(map(int, input().split()))

from itertools import accumulate
for i in range(k):
    imos = [0]*(n+1)
    for j in range(n):
        d = A[j]
        l = max(0, j-d)
        r = min(n-1, j+d)
        imos[l] += 1
        imos[r+1] -= 1
    imos = list(accumulate(imos))
    for j in range(n):
        A[j] = imos[j]
    if A == [n]*n:
        break

print(*A)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n, k =map(int,input().split())
    A = list(map(int,input().split())) + [0]
    while k > 0:
        B = [0] * (n + 1) 
        for i, a in enumerate(A):
            B[max(0, i - a)] += 1
            B[min(n, i + a + 1)]  -= 1
        if B[0] == n:
            flag = True
        for i in range(1, n+1):
            B[i] += B[i-1]
            if B[i] != n and i < n:
                flag = False
        A = B[:]
        if flag:
            break
        k -= 1
    print(" ".join(map(str, B[:-1])))

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
a_ls = list(map(int, input().split()))

prev_power = a_ls
for i in range(K):
    next_power = [0] * N

    for er in range(N):
        arm = prev_power[er]
        for ed in range(er-arm,er+arm+1):
            if 0<=ed<N:
                next_power[ed] += 1
    #print(i,next_power)
    
    # 全部Nまで成長してたら終了
    all_N = True
    for j in range(N):
        if next_power[j] != N:
            all_N = False
            break

    prev_power = next_power

print(*next_power)

Submission status: Time Limit Exceeded

Solution code:
def main(*, int=int, input=input):
    n, k = map(int, input().split()) 
    A = list(map(int, input().split()))
    
    E = [0] * n
    for i in range(k):
        B = E.copy()
        for j in range(n):
            h = A[j]
            while h >= 0:
                if j - h >= 0:
                    B[j-h] += 1
                
                if j < j + h < n:
                    B [j+h] += 1
                
                h -= 1
        A = B.copy()
    buf = ""        
    for i in range(n):
        buf += str(B[i])
        buf += " "
    print(buf.rstrip())    

if __name__ == "__main__":

    main()

Submission status: Time Limit Exceeded

Solution code:
n,k,*A=map(int,open(0).read().split());e=enumerate
for _ in '_'*min(k,99):
  S=[0]*(n+1)
  B=[0]*(n+1)
  for i,a in e(A):S[max(0,i-a)]+=1;S[min(n,i+a+1)]-=1
  for i,s in e(S[:-1]):B[i+1]=B[i]+s
  A=B[1:]
print(*A)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from sys import stdin
    input = stdin.readline

    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    
    for cnt in range(min(k, 41)):
        ans = []
        bit = [0]*(n+1)
        for i, j in enumerate(a):
            x, y = max(i-j, 0)+1, min(i+j+1, n)+1
            while x < n+1:
                bit[x] += 1
                x += x & (-x)
            while y < n+1:
                bit[y] -= 1
                y += y & (-y)
        for i in range(n):
            ret, x = 0, i+1
            while x > 0:
                ret += bit[x]
                x -= x & (-x)
            ans.append(ret)
        a = ans

    print(*ans)


main()

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
for _ in range(K):
    if len(set(A)) == 1 and A[0] == N:
        break
    work = [0] * (N + 1)
    for i in range(N):
        a = A[i]
        idx0 = max(0, i - a)
        idx1 = min(N, i + a + 1)
        work[idx0] += 1
        work[idx1] -= 1
    now = 0
    for i in range(N):
        now += work[i]
        A[i] = now
print(*A)

Submission status: Time Limit Exceeded

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

for _ in range(min(K, 50)):
    lamp = [0 for i in range(N + 1)]
    for i in range(N):
        lamp[max(0, i - A[i])] += 1
        lamp[min(N, i + A[i] + 1)] -= 1

    ans = 0
    for i in range(N):
        ans += lamp[i]
        A[i] = min(ans, N)

[print(A[i], end=' ') if i != N - 1 else print(A[i]) for i in range(N)]

Submission status: Time Limit Exceeded

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

for _ in range(min(K, 100)):
    lamp = [0 for i in range(N + 1)]
    for i in range(N):
        lamp[max(0, i - A[i])] += 1
        lamp[min(N, i + A[i] + 1)] -= 1

    ans = 0
    for i in range(N):
        ans += lamp[i]
        A[i] = min(ans, N)

[print(A[i], end=' ') if i != N - 1 else print(A[i]) for i in range(N)]

Submission status: Time Limit Exceeded

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

for _ in range(min(K, int(N ** 0.5))):
    lamp = [0 for i in range(N + 1)]
    for i in range(N):
        lamp[max(0, i - A[i])] += 1
        lamp[min(N, i + A[i] + 1)] -= 1

    ans = 0
    for i in range(N):
        ans += lamp[i]
        A[i] = min(ans, N)

[print(A[i], end=' ') if i != N - 1 else print(A[i]) for i in range(N)]

Submission status: Time Limit Exceeded

Solution code:
n, k, *a = map(int, open(0).read().split())

for _ in range(k):
    b = [0] * -~n
    for i in range(len(a)):
        b[max(0, i - a[i])] += 1
        b[min(n, i + a[i] + 1)] -= 1
    for i in range(n):
        b[i + 1] += b[i]

    if all(x == n for x in b[:n]):
        print(' '.join(map(str, b[:n])))
        exit()
    a = b
print(' '.join(map(str, a[:n])))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, k = map(int, input().split())
arr = np.array(list(map(int, input().split())))

for i in range(min(k, 40)):
    tmp_arr = np.zeros(n + 1, np.int64)
    for i, x in enumerate(arr):
        tmp_arr[max(0, i - x)] += 1
        tmp_arr[min(n, i + x + 1)] -= 1
    arr = np.cumsum(tmp_arr)[:-1]

print(*arr)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, k = map(int, input().split())
arr = np.array(list(map(int, input().split())))

for i in range(k):
    tmp_arr = np.zeros(n + 1, np.int64)
    for i, x in enumerate(arr):
        tmp_arr[max(0, i - x)] += 1
        tmp_arr[min(n, i + x + 1)] -= 1
    arr = np.cumsum(tmp_arr)[:-1]
    if np.where(arr == n)[0].shape[0] == n:
        break

print(*arr)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, k = map(int, input().split())
arr = np.array(list(map(int, input().split())))

for i in range(k):
    tmp_arr = np.zeros(n, np.int64)
    for i, x in enumerate(arr):
        tmp_arr[max(0, i - x):min(n, i + x + 1)] += 1
    arr = tmp_arr
    if np.where(arr == n)[0].shape[0] == n:
        break

print(*arr)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
N,K=map(int,input().split())

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

for _ in range(K):
    ans=[0]*len(A)
    start=[0]*len(A)
    end=[0]*len(A)
    
    for index,item in enumerate(A):
        start[max(0,index-item)]+=1
        end[min(len(end)-1,index+item)]+=1
    
    #print(start)
    #print(end)
    
    temp=0
    for i in range(len(ans)):
        temp+=start[i]
        ans[i]=temp
        temp-=end[i]
    
    A=ans[:]

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
# 問題文の意味がわからんコンテスト
# 0の場合も自分自身を照らす、っての気づくところからやっと読解
# Kを5000兆回やったあとはすべての要素がNになっとる この収束はわりと早いらしい
n, k = map(int, input().split())
a = list(map(int, input().split()))

for _ in range(k):
    b = [0] * (n + 1)
    for i in range(n):
        b[max(0, i - a[i])] += 1
        b[min(n, i + a[i] + 1)] -= 1
    for i in range(n):
        b[i + 1] += b[i]
    a = b[:n]
    if b[-1] == n:
        break
print(" ".join(list(map(str, a))))

Submission status: Time Limit Exceeded

Solution code:
# 問題文の意味がわからんコンテスト
# 0の場合も自分自身を照らす、っての気づくところからやっと読解
# Kを5000兆回やったあとはすべての要素がNになっとる この収束はわりと早いらしい
n, k = map(int, input().split())
a = list(map(int, input().split()))

for _ in range(k):
    b = [0] * (n + 1)
    for i in range(n):
        b[max(0, i - a[i])] += 1
        b[min(n, i + a[i] + 1)] -= 1
    for i in range(n):
        b[i + 1] += b[i]
    a = b[:n]
    if b[-1] == n:
        break
print(" ".join(list(map(str, a))))

Submission status: Time Limit Exceeded

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N, K = LI()
    A = LI()

    # 全部0の最遅ケースでもlog(N)*2くらいで収束する log(2*10**5)<50
    for _ in range(min(K, 50)):
        tmp = [0] * (N + 1)
        b = [0] * (N + 1)
        for i in range(N):
            tmp[max(i - A[i], 0)] += 1
            tmp[min(i + A[i] + 1, N)] -= 1
        for i in range(N):
            b[i+1] = tmp[i] + b[i]
        for i in range(N):
            A[i] = b[i+1] 
        # print(A)

    print(*A)

if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N, K = LI()
    A = LI()

    for _ in range(K):
        tmp = [0] * (N + 1)
        b = [0] * (N + 1)
        for i in range(N):
            tmp[max(i - A[i], 0)] += 1
            tmp[min(i + A[i] + 1, N)] -= 1
        for i in range(N):
            b[i+1] = tmp[i] + b[i]
        for i in range(N):
            A[i] = b[i+1] 
        if A.count(N) == N:
            break

    print(*A)

if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N, K = LI()
    A = LI()

    for _ in range(K):
        tmp = [0] * N
        for i in range(N):
            for j in range(max(i - A[i], 0), min(i + A[i] + 1, N)):
                tmp[j] += 1
        for i in range(N):
            A[i] = tmp[i] 
        if A.count(N) == N:
            break

    print(*A)

if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np

N, K = map(int, input().split())
A = list(map(int, input().split()))
B = []
for i in range(1, N+1):
  B.append(list(range(math.ceil(i - A[i-1] -0.5), math.ceil(i + A[i-1] + 0.5))))
A = [0] * N
for x in B:
  for n in range(0, N):
    if n + 1 in x:
      A[n] += 1
if K >= 2:
  for i in range(math.ceil(np.log(K))):
    for k in range(1, N+1):
      B[k-1] = list(range(math.ceil(k - A[k-1] -0.5), math.ceil(k + A[k-1] + 0.5)))
    A = [0] * N
    for x in B:
      for n in range(0, N):
        if n + 1 in x:
          A[n] += 1
print(*A)

Submission status: Time Limit Exceeded

Solution code:
import math

N, K = map(int, input().split())
A = list(map(int, input().split()))
B = []
for i in range(1, N+1):
  B.append(list(range(math.ceil(i - A[i-1] -0.5), math.ceil(i + A[i-1] + 0.5))))
A = [0] * N
for x in B:
  for n in range(0, N):
    if n + 1 in x:
      A[n] += 1
if K >= 2:
  for i in range(K-1):
    for k in range(1, N+1):
      B[k-1] = list(range(math.ceil(k - A[k-1] -0.5), math.ceil(k + A[k-1] + 0.5)))
    A = [0] * N
    for x in B:
      for n in range(0, N):
        if n + 1 in x:
          A[n] += 1
print(*A)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
ls = list(map(int,input().split()))
for j in range(k):
    di = [0]*(n+1)
    fi = [0]*(n+1)
    for i in range(n):
        r = min(n-1,i+ls[i])
        l = max(0,i-ls[i])
        di[l] += 1
        di[r+1] -= 1
    fi[0] = di[0]
    for l in range(1,n+1):
        fi[l] = fi[l-1] + di[l]
    if list(set(fi)) == [n]:
        break
    ls = fi
print(*fi[:-1])

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
ls = list(map(int,input().split()))
for j in range(k):
    di = [0]*(n+1)
    for i in range(n):
        if i - ls[i] >= 0 and i + ls[i] <= n-1:
            di[i - ls[i]] += 1
            di[i + ls[i] + 1] -= 1
        elif i - ls[i] >= 0 and i + ls[i] > n-1:
            di[i - ls[i]] += 1
            di[n] -= 1
        elif i - ls[i] < 0 and i + ls[i] <= n-1:
            di[0] += 1
            di[i + ls[i] + 1] -= 1
        else:
            di[0] += 1
            di[n] -= 1
    fi = [0]*(n+1)
    fi[0] = di[0]
    for l in range(1,n+1):
        fi[l] = fi[l-1] + di[l]
    ls = fi
    if list(set(ls)) == [n]:
        break
print(*fi[:-1])

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
ls = list(map(int,input().split()))
for j in range(k):
    di = [0]*(n+1)
    for i in range(n):
        if i - ls[i] >= 0 and i + ls[i] <= n-1:
            di[i - ls[i]] += 1
            di[i + ls[i] + 1] -= 1
        elif i - ls[i] >= 0 and i + ls[i] > n-1:
            di[i - ls[i]] += 1
            di[n] -= 1
        elif i - ls[i] < 0 and i + ls[i] <= n-1:
            di[0] += 1
            di[i + ls[i] + 1] -= 1
        else:
            di[0] += 1
            di[n] -= 1
    fi = [0]*(n+1)
    fi[0] = di[0]
    for l in range(1,n+1):
        fi[l] = fi[l-1] + di[l]
    ls = fi
print(*fi[:-1])

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
A=list(map(int,input().split()))

for i in range(min(50,k)):
    B=[0]*n
    for j in range(n):
        l=max(0,j-A[j])
        r=min(n-1,j+A[j])
        B[l]+=1
        if r<n-1:
            B[r+1]-=1
    for j in range(1,n):
        B[j]+=B[j-1]
    A=B.copy()
print(*A)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
A=list(map(int,input().split()))

for i in range(min(50,k)):
    B=[0]*n
    for j in range(n):
        for l in range(max(j-A[j],0),min(j+A[j]+1,n)):
            B[l]+=1
    A=B.copy()
print(*A)

Submission status: Time Limit Exceeded

Solution code:
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()

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
N, K = map(int, input().split())
A = list(map(int, input().split()))


def calc_imos(arr):
    imos = [0] * (N + 1)
    for i, a in enumerate(arr):
        l = max(0, i - a)
        r = min(N - 1, i + a)
        imos[l] += 1
        imos[r + 1] -= 1
    imos = list(accumulate(imos))
    return imos[:-1]


for k in range(min(50, K)):
    A = calc_imos(A)
print(*A, sep=' ')

Submission status: Time Limit Exceeded

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline
from numba import jit

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

@jit
def solve(N,K,A):
    for i in range(K):
        imo = [0]*(N+1)
        flag = 1
        for j in range(N):
            imo[max(0,j-A[j])] += 1
            imo[min(N,j+A[j]+1)] -= 1
            if j-A[j]>0 or j+A[j]+1<N:
                flag = 0
        A = list(itertools.accumulate(imo))[:-1]
        if flag == 1:
            break
    return A

A = solve(N,K,A)
print(*A)

Submission status: Time Limit Exceeded

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

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

for i in range(K):
    imo = [0]*(N+1)
    flag = 1
    for j in range(N):
        imo[max(0,j-A[j])] += 1
        imo[min(N,j+A[j]+1)] -= 1
        if j-A[j]>0 or j+A[j]+1<N:
            flag = 0
    A = list(itertools.accumulate(imo))[:-1]
    if flag == 1:
        break
print(*A)

Submission status: Time Limit Exceeded

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

for cnt in range(K):
  B = [0] * (N+1)
  for i in range(N):
    bright = A[i]
    l = max(i-bright,0)
    r = min(i+bright+1, N)
    B[l] += 1
    B[r] -= 1
  for i in range(N):
    B[i+1] += B[i]
  
  A = B[:-1]
  #print(A)
  if min(A) == N:
    #print(cnt)
    break
    
print(" ".join(map(str,A)))

Submission status: Time Limit Exceeded

Solution code:

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

x = X[:]
for _ in range(K):
    if all(v == N for v in x):
        break

    new = [0] * N
    for i in range(N):
        for j in range(max(0, i - x[i]), min(N, i + x[i] + 1)):
            new[j] += 1
    x = new[:]

print(*x)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

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

def calc_imos(arr):
  imos=[0]*(N+1)
  for i,a in enumerate(arr):
    l=max(0,i-a) #照らす範囲の左側インデックス、0が最小
    r=min(N-1,i+a) #照らす範囲右側インデックス,arrの長さ-1=Nが最大
    imos[l]+=1
    imos[r+1]-=1
    #print("imos",imos)
  imos=list(accumulate(imos))
  #print("imos",imos)
  return imos[:-1]

for k in range(min(50,K)):
  A=calc_imos(A)
print(*A,sep=" ")

Submission status: Time Limit Exceeded

Solution code:
rd = lambda:map(int, input().split())
n, k = rd()
v = list(rd())
while k and min(v) < n:
    u = [0]*(n+1)
    for i in range(n):
        u[max(0, i-v[i])] += 1
        u[1+min(n-1, i+v[i])] -= 1
    for i in range(1, n+1):
        u[i] += u[i-1]
    for i in range(n):
        v[i] = u[i]
    k -= 1
for i in range(n):
    print(v[i], end = " ")

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, k = map(int, input().split())
A = np.array(list(map(int, input().split())))
A = np.append(A, 0)
for _ in range(k):
    l = np.zeros((n + 1,), int)
    for i, a in enumerate(A[:-1]):
        l[max(0, i - a)] += 1
        l[min(n, i + a + 1)] -= 1
    A = np.cumsum(l)
    if np.all(A[:-1] == n):
        break
print(*A[:-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import jit


@jit("i8, i8, i8[:]")
def myfunc(n, k, A):
    for _ in range(k):
        l = np.zeros((n + 1,), dtype=np.int64)
        for i, a in enumerate(A[:-1]):
            l[max(0, i - a)] += 1
            l[min(n, i + a + 1)] -= 1
        A = np.cumsum(l)
    return A


def main():
    n, k = map(int, input().split())
    A = np.array(list(map(int, input().split())), dtype=np.int64)
    A = np.append(A, 0)
    print(*myfunc(n, k, A)[:-1])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import jit


@jit
def myfunc(n, k, A):
    for _ in range(k):
        l = np.zeros((n + 1,), dtype=np.int64)
        for i, a in enumerate(A[:-1]):
            l[max(0, i - a)] += 1
            l[min(n, i + a + 1)] -= 1
        A = np.cumsum(l)
    return A


def main():
    n, k = map(int, input().split())
    A = np.array(list(map(int, input().split())), dtype=np.int64)
    A = np.append(A, 0)
    print(*myfunc(n, k, A)[:-1])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import numpy as np

    n, k = map(int, input().split())
    A = np.array(list(map(int, input().split())))
    A = np.append(A, 0)
    for _ in range(k):
        l = np.zeros((n + 1,), dtype=int)
        for i, a in enumerate(A[:-1]):
            l[max(0, i - a)] += 1
            l[min(n, i + a + 1)] -= 1
        A = np.cumsum(l)
    print(*A[:-1])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import numpy as np

    n, k = map(int, input().split())
    A = np.array(list(map(int, input().split())))
    A = np.append(A, 0)
    for _ in range(k):
        l = [0] * (n + 1)
        for i, a in enumerate(A[:-1]):
            l[max(0, i - a)] += 1
            l[min(n, i + a + 1)] -= 1
        A = np.cumsum(l)
    print(*A[:-1])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from itertools import accumulate
    import numpy as np

    n, k = map(int, input().split())
    A = np.array(list(map(int, input().split())))
    A = np.append(A, 0)
    for _ in range(k):
        l = [0] * (n + 1)
        for i, a in enumerate(A[:-1]):
            l[max(0, i - a)] += 1
            l[min(n, i + a + 1)] -= 1
        A = np.array(list(accumulate(l)))
    print(*A[:-1])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from itertools import accumulate
    import numpy as np

    n, k = map(int, input().split())
    A = np.array(list(map(int, input().split())))
    A = np.append(A, 0)
    for _ in range(k):
        l = [0] * (n + 1)
        for i, a in enumerate(A[:-1]):
            l[max(0, i - a)] += 1
            l[min(n, i + a + 1)] -= 1
        A = np.array(list(accumulate(l)))
    print(*A[:-1])


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from itertools import accumulate

    n, k = map(int, input().split())
    A = list(map(int, input().split())) + [0]
    for _ in range(k):
        l = [0] * (n + 1)
        for i, a in enumerate(A[:-1]):
            l[max(0, i - a)] += 1
            l[min(n, i + a + 1)] -= 1
        A = list(accumulate(l))
    print(*A[:-1])

main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate


def main():
    n, k = map(int, input().split())
    A = list(map(int, input().split())) + [0]
    for _ in range(k):
        l = [0] * (n + 1)
        for i, a in enumerate(A[:-1]):
            l[max(0, i - a)] += 1
            l[min(n, i + a + 1)] -= 1
        A = list(accumulate(l))
    print(*A[:-1])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

n, k = map(int, input().split())
A = list(map(int, input().split())) + [0]

for _ in range(k):
    l = [0] * (n + 1)
    for i, a in enumerate(A[:-1]):
        l[max(0, i - a)] += 1
        l[min(n, i + a + 1)] -= 1
    A = list(accumulate(l))

print(*A[:-1])

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

n, k = map(int, input().split())
a = list(map(int, input().split())) + [0]

for _ in range(k):
    l = [0] * (n + 1)
    x = 0
    for i in a[:-1]:
        l[max(0, x - i)] += 1
        l[min(n, x + i + 1)] -= 1
        x += 1
    a = list(accumulate(l))

print(*a[:-1])