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: Time Limit Exceeded

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

while K > 0 and not conv:
    K -= 1
    b = [0]*(N+1)
    for i in range(N):
        l, r = i - A[i], i + A[i] + 1
        if l < 0:   l = 0
        if r > N:   r = N
        b[l] += 1
        b[r] -= 1

    A[0], conv = b[0], True
    for i in range(1, N):
        A[i] = A[i-1] + b[i]
        if b[i] != 0:
            conv = False

if conv:
    print(' '.join(map(str, [N]*N)))
else:
    print(' '.join(map(str, A)))

Submission status: Time Limit Exceeded

Solution code:
"""
https://atcoder.jp/contests/tokiomarine2020/submissions/14229099
"""
N,K = map(int,input().split())
A = list(map(int,input().split()))

def update(A):
    b = [0]*N

    for i,a in enumerate(A):
        l = max(0,i-a)
        r = min(N-1,i+a)

        b[l] += 1
        if r+1 < N:
            b[r+1] -= 1
    
    res = []
    s = 0
    for i in b:
        s += i
        res.append(s)
    return res

for _ in range(min(K,75)):
    A = update(A)

print(*A)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
for k in range(K):
    imos = [0] * (N+1)
    for i,a in enumerate(A):
        l = max(0, i-a)
        r = min(N, i+1+a)
        imos[l] += 1
        imos[r] -= 1
    imos[0] = min(N, imos[0])
    for i in range(N):
        imos[i+1] = min(N, imos[i] + imos[i+1])
    A = imos[:-1]
    if A[0] == A[-1] == N:
        break
print(*A)

Submission status: Time Limit Exceeded

Solution code:
import math

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

i=0
while i<k and i<math.log(n):
    b=[0]*n
    for j in range(0, n):
        x = a[j]
        y=j-x
        if y<0:
            y=0
        while y<=j+x and y<n :
            b[y]+=1
            y+=1
    a=b
    i+=1

ans = str(a[0])
i=1
while i<n:
    ans +=" "+ str(a[i])
    i+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

if __name__ == '__main__':
    N, K = map(int, input().strip().split(" "))
    A = np.array(input().strip().split(" ")).astype(float)

    if K >= 41 or N <= K:
        print(" ".join([str(N)] * N))
    else:
        if N > 30 and N/3 < K:
            print(" ".join([str(N)] * N))
        else:
            for i in range(K):
                B = np.zeros(N)
                for j in range(N):
                    for k in range(max(0, int(j - A[j] - 0.5 + 0.999999)), min(int(j + A[j] + 1 + 0.5), N), 1):
                        B[k] += 1
                A = B.copy()
            print(" ".join(A.astype(int).astype(str)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit
N, K = map(int, input().split())
A = np.array(list(map(int, input().split())), dtype=np.int64)


@njit
def solve(N, K, A):
    # 一度照らされると二度目以降は確実に照らされるはず。
    for i in range(K):
        # j番目の電球を操作
        B = np.array([0] * N, dtype=np.int64)
        if list(set(A)) == [N]:
            break
        for j in range(N):
            if A[j] == N:
                B[j] = N
                continue
            maxA = j + A[j]
            minA = j - A[j]

            for k in range(max(0, minA), min(N, maxA + 1)):
                B[k] += 1
        A = B.copy()
    return A


A = solve(N, K, A)
for i in range(N):
    if i != (N - 1):
        print(A[i], end=" ")
    else:
        print(A[i])

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
import numpy as np
import copy
A = np.array(list(map(int, input().split())))
for _ in range(k):
    C = np.zeros([n,], dtype=np.int32)
    for i in range(n):
        a = A[i]
        l = max(0, i - a)
        r = min(n, i + a + 1)
        C[l:r] += 1
    A = C + 0
print(" ".join(map(str, list(A))))

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int, input().split())
A = list(map(int, input().split()))
temp = [0 for _n in range(N)]
for k in range(K):
  for n in range(N):
    for nn in range(N):
      if (A[nn])>=(abs(nn-n)):
        temp[n] += 1
  A = temp
  temp = [0 for _n in range(N)]
print(*A)

Submission status: Time Limit Exceeded

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

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



for _ in range(K):
    
    A_hat = [0] * N
    # A = A_hat
   
    
    for i in range(N):
        count = 0
        for j in range(N):
            
            l = abs(i - j)
            if l <= A[j]:
                count += 1
    
        A_hat[i] = count
    # print(A_hat)
    A = A_hat
L=[str(a) for a in A_hat]
L=' '.join(L)
print(L)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    if K >= 41:
        K = 41
    for k in range(K):
        next_A = [0 for i in range(N)]
        for i in range(len(A)):
            high = i + A[i] + 1
            if high > N:
                high = N
            low = i - A[i]
            if low < 0:
                low = 0
            for j in range(low,high):
                next_A[j] += 1
        A = next_A
    
    print(*A)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

# 以下カンニング
for _ in range( min( k, 42 ) ):
    b = [ 0 for _ in range( n ) ]

    for i in range( n ):
        l = max( 0, i - a[ i ] )
        r = min( n - 1, i + a[ i ] )
        b[ l ] += 1
        if r + 1 < n:
            b[ r + 1 ] -= 1

    for i in range( 1, n ):
        b[ i ] += b[ i - 1 ]

    a = copy.deepcopy( b )

print( " ".join( list( map( str, a ) ) ) )

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import math
N, K = map(int, input().split())
A = input().split()
AK = [[0 for j in range(N)] for i in range(2)]
for l in range(N):
  AK[0][l] = int(AK[0][l]) + int(A[l])
p = min(K,50)
for m in range(1,p+1,1):
  for o in range(N):
    for x in range(N):
      if((o-AK[0][o]+0.5) < (x+1)) and ((x+1) < (o+AK[0][o]+1.5)):
        AK[1][x] = AK[1][x] +1
  AK[0] = AK[1]
  AK[1] = [0] * N
print(*AK[0])

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
for j in range(k):
  b = [0]*n
  for i in range(n):
    l = max(0, i-a[i])
    r = min(n, i+a[i]+1)
    b[l] += 1
    if r < n:
      b[r] -= 1
  for i in range(1, n): 
    b[i]+=b[i-1]
  a = b
  if a.count(n) == n:
    break
print(" ".join(list(map(str, a))))

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
for k in range(K):
    imos = [0] * (N+1)
    for i,a in enumerate(A):
        l = max(0, i-a)
        r = min(N, i+1+a)
        imos[l] += 1
        imos[r] -= 1
    imos[0] = min(N, imos[0])
    for i in range(N):
        imos[i+1] = min(N, imos[i] + imos[i+1])
    A = imos[:-1]
    if all(a==N for a in A):
        break
print(*A)

Submission status: Time Limit Exceeded

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

K = min(K,50)
for k in range(K):
  light = [0] * N
  for i in range(N):
    start = max(0,i-A[i])
    end = min(N-1, i+A[i])
    for j in range(start, end+1):
      light[j] += 1
    
  A = light

print(" ".join(map(str,light)))

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
n,k = map(int,input().split())
A = list(map(int,input().split()))
for _ in range(k):
    c = [0]*n
    for i,j in enumerate(A):
        l = max(0,i-j)
        r = min(n-1,i+j)
        c[l] += 1
        if r+1 < n:
            c[r+1] -= 1
    if A != list(accumulate(c)):
        A = list(accumulate(c))
    else:
        break
print(" ".join(map(str,A)))

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
dp2=list(map(int,input().split()))
    
for ki in range(1,k+1):
    ims=[0]*(n+1)
    for ni in range(n):
        if 0>ni-dp2[ni]:
            ims[0]+=1
        else:
            ims[ni-dp2[ni]]+=1
        if n<ni+dp2[ni]+1:
            ims[n]-=1
        else:
            ims[ni+dp2[ni]+1]-=1

    dp2[0]=ims[0]
    for ni in range(1,n):
        dp2[ni]=dp2[ni-1]+ims[ni]
           
for i in range(n):
    print(dp2[i],end=" ")
print()

Submission status: Time Limit Exceeded

Solution code:
n,k=[int(_) for _ in input().split()]
A=[int(_) for _ in input().split()]
_A=[0 for i in range(n+1)]
for i in range(k):
    for j in range(n+1):
        _A[j]=0
    for j in range(n):
        _A[max(0,j-A[j])]+=1
        _A[min(n,j+A[j]+1)]-=1
    for j in range(1,n):
        _A[j]+=_A[j-1]
        
    for j in range(n):
        A[j]=_A[j]
    if sum(_A)==n*n:
        break

for i in range(n):
    print(A[i],end=" ")
print()

Submission status: Time Limit Exceeded

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

for k in range(K):
    for i in range(N):
        if A[i] != N:
            break
    else:
        break

    B = [0] * N
    for i in range(N):
        d = A[i]
        left = max(0, i - d)
        right = min(N-1, i + d)
        for index in range(left, right+1):
            B[index] += 1
    A = B
print(" ".join(map(str, A)))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

K = min(K, 100)

for _ in range(K):
    imos = [0] * (N + 1)

    for i in range(N):
        a = A[i]
        s = max(0, i - a)
        e = min(N, i + a + 1)
        imos[s] += 1
        imos[e] -= 1

    nxt = [0] * N
    t = 0
    for i in range(N):
        t += imos[i]
        nxt[i] = t

    A = nxt

print(" ".join(map(str, A)))

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
if N%2 == 0:
    b = N//2
else:
    b = (N//2) +2
if N==1:
    print(1)
    exit()
if K >= 41:
    for i in range(N-1):
        print(N,end=" ")
    print(N)
    exit()
for k in range(K):
    nextgen = [0]*N
    for i in range(N):
        # print("i=",i)
        a = A[i]
        start = i-a
        if start <0:
            start = 0
        end = i+a+1
        if end <=N-1:
            nextgen[end] += -1
        nextgen[start] += 1
    dp = 0
    for i in range(N):
        dp += nextgen[i]
        A[i] = dp
s = ' '.join([str(i) for i in A])
print(s)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

if __name__ == '__main__':
    N, K = map(int, input().strip().split(" "))
    A = np.array(input().strip().split(" ")).astype(float)

    if K >= 41 or N <= K:
        print(" ".join([str(N)] * N))
    else:
        for i in range(K):
            B = np.zeros(N)
            for j in range(N):
                for k in range(max(0, int(j - A[j] - 0.5 + 0.999999)), min(int(j + A[j] + 1 + 0.5), N), 1):
                    B[k] += 1
            A = B.copy()
        print(" ".join(A.astype(int).astype(str)))

Submission status: Time Limit Exceeded

Solution code:

# いもす法の利用
import copy 
N,K=map(int,(input().split()))
A=list(map(int,(input().split())))
B= [0 for _ in range(N)]
for i in range(K):
  B= [0 for _ in range(N)]
  C=0
  for j in A:

    if(C-j<0):
      left=0
      B[left]+=1
    else:
      left=C-j
      B[left]+=1
    if(C+j+1>=N):
      right=N-1
    else:
      right=C+j+1
      B[right]-=1

    C+=1
  
  ruiseki = [0] * N  # 累積和用リスト
  ruiseki[0] = B[0]
  for m in range(N):
      ruiseki[m] = ruiseki[m-1] + B[m]
  A = copy.copy(ruiseki)
  if(i==50):
    reuseki = [N]*N
    break
print(*ruiseki)

Submission status: Time Limit Exceeded

Solution code:
import sys
n,k = map(int,input().split())
ls = list(map(int,input().split()))
if n >17 and k >n/2:
    for q in range(len(ls)):
        print(len(ls),end=" ")
    sys.exit()
if k >= len(ls):
    for q in range(len(ls)):
        print(len(ls),end=" ")
    sys.exit()
for _ in range(k):
    new = [0]*n
    for i in range(n):
        p = 0
        for l in range(1,max(n-i,i+1)):
            if i+l >= 0 and i+l <n:
                if ls[i+l] >= l:
                    p += 1
            if i-l >= 0 and i-l <n:
                if ls[i-l] >= l:
                    p += 1
        new[i] = p+1
    ls = new
print(*ls)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(min(k, 41)):
    b = [0]*n
    for j in range(n):
        for l in range(a[j]+1):
            if j >= l:
                b[j-l] += 1
            if n-1-j >= l:
                b[j+l] += 1
            if l == 0:
                b[j] -= 1
    a = b
print(*a)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
a = [int(i) for i in input().split()]
d = [0]*(n+1)
for x in range(k):
    for i in range(n):
        l = max(0,i-a[i])
        r = min(n-1,i+a[i])+1
        d[l] += 1
        d[r] -= 1
    for i in range(n): d[i+1] += d[i]
    if x == k-1: break
    for i in range(n):
        if d[i] != n: break
    else:
        break
    a = d[:]
    d = [0]*(n+1)
print(*d[:n])

Submission status: Time Limit Exceeded

Solution code:
import math

N, K = map(int, input().split())
if K >= 1000 and N / 2 + 1 < K:
    K = int(math.sqrt(N))
A_list = list(map(int, input().split()))

A_New_list = [0 for i in range(N)]
for k in range(K):
    for i in range(N):
        for j in range(A_list[i] + 1):
            if j == 0:
                # if A_list[i] != 0:
                A_New_list[i] += 1
            else:
                if i + j < N:
                    A_New_list[i+j] += 1
                if i - j >= 0:
                    A_New_list[i-j] += 1
    # print(A_New_list)
    A_list = A_New_list
    if k != K - 1:
        A_New_list = [0 for n in range(N)]
A_New_list = [str(a) for a in A_New_list]
ans = " ".join(A_New_list)
print(ans)

Submission status: Time Limit Exceeded

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

for i in range(K):
  B = [0]*len(A)
  for j in range(len(A)):
    llim = max([0, j-A[j]])
    ulim = min([len(A), j+A[j]+1])
    B[llim]+=1
    if ulim<len(A):
      B[ulim]-=1
  for j in range(1,len(A),1):
    B[j] +=B[j-1]

  if A==B:
    break
  A=B

print(*A)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, K = map(int, input().split())
A = list(map(int, input().split()))
lights = np.zeros(N, dtype='int32')

for _ in range(min(K, 45)):
    lights = np.zeros(N, dtype='int32')
    for i, flash in enumerate(A):
        front = i-flash if i-flash >= 0 else 0
        back = i+flash if i+ flash < N else N-1
        lights[front:back+1] += 1
    A = np.copy(lights)

for i in A:
    print(int(i),end=' ')
print()

Submission status: Time Limit Exceeded

Solution code:
def change(lst):
  lst1 = [0]*len(lst)
  for i in range(len(lst)):
    for j in range(i-lst[i], i+lst[i]+1):
      if j < 0 or j >= len(lst):
        continue
      lst1[j] += 1
  return lst1

n, k = map(int, input().split())
lst = list(map(int, input().split()))
if k >= n:
  lst = [n]*n
else:
  for _ in range(k):
    lst = change(lst)

print(" ".join(map(str, lst)))

Submission status: Time Limit Exceeded

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

for num in range(k):
    light = []
    ans = [0] * n
    for i,ramp in enumerate(li,1):
        a = max(i - ramp,1)
        b = min(i + ramp,n)
        light.append([a,b])

    for j, m in light:
        for l in range(j,m+1):
            ans[l-1] += 1
    li = ans.copy()
    if min(ans) == n:
        break

print(*ans,sep=" ")

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit
N, K = map(int, input().split())
A = np.array(list(map(int, input().split())))


@njit
def solve(N, K, A):
    # 一度照らされると二度目以降は確実に照らされるはず。
    for i in range(K):
        # j番目の電球を操作
        B = np.array([0] * N)
        if list(set(A)) == [N]:
            break
        for j in range(N):
            if A[j] == N:
                B[j] = N
                continue
            maxA = j + A[j]
            minA = j - A[j]

            for k in range(max(0, minA), min(N, maxA + 1)):
                B[k] += 1
        A = B.copy()
    return A


A = solve(N, K, A)
for i in range(N):
    if i != (N - 1):
        print(A[i], end=" ")
    else:
        print(A[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
input = lambda: sys.stdin.readline().rstrip()
n, k = map(int, input().split())
imos = list(map(int, ("0 " + input()).split()))
logk = k * math.log(2 * 10**5) + 1
# print(logk)
for ii in range(min(k, logk)):
    ans = [0 for _ in range(n + 1)]
    for i in range(1, n + 1):
        left = max(1, i - imos[i])
        # right = min(n, i + imos[i])
        ans[left] += 1
        if i + imos[i] + 1 <= n:
            ans[i + imos[i] + 1] -= 1
    now = 0
    for i in range(len(ans)):
        now += ans[i]
        imos[i] = now

# print(imos)
for i in imos[1:]:
    print(i)

# print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n, k = map(int, input().split())
a_list = np.array(list(map(int, input().split())))

for ki in range(k):
  b_list = np.array([0] * n)
  i = 0
  for ai in a_list:
    b_list += np.array([0]*(max(0,i-ai)) + [1]*(n-(max(0,i-ai))-(max(0,n-(i+1+ai)))) + [0]*(max(0,n-(i+1+ai))))
    i += 1
  a_list = b_list
  if np.all(a_list == n):
    break

print(*a_list)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
n -= 1

for _ in range(k):
    b = [0]*len(a)
    for i in range(len(a)):
        light = a[i]
        if i-light >= 0 and i+light <= n:
            for j in range(i-light, i+light+1):
                b[j] += 1
        elif i+light <= n:
            for j in range(0, i+light+1):
                b[j] += 1
        elif i-light >= 0:
            for j in range(i-light, n+1):
                b[j] += 1
        else:
            for j in range(0, n+1):
                b[j] += 1
    a = b.copy()

b_str = [str(l) for l in b]
b_str = " ".join(b_str)
print(b_str)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

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

    for i in range(min(K,50)):
        dm = [0]*N
        for x in range(N):
            dm[max(x - A[x],0)]+=1
            if x+A[x]+1<N:
                dm[x+A[x]+1]+=-1
        for j in range(1,N):
            dm[j]=dm[j-1]+dm[j]
        A[:] = dm[:]
    print(*A)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

a = deque(map(int, input().split()))
ad = {}
for i in range(n):
    ad[i] = a.popleft()

def makea(ad):
    newa = {}
    for i in range(n):
        newa[i] = 0
    for i in range(n):
        if i - ad[i] >= 0:
            if i + ad[i] <= n-1:
                for j in range(i-ad[i], i+ad[i]+1):
                    newa[j] += 1
            else:
                for j in range(i-ad[i], n):
                    newa[j] += 1
        elif i + ad[i] <= n-1:
            for j in range(i+ad[i]+1):
                newa[j] += 1
        else:
            for j in range(n):
                newa[j] += 1
    return newa

for _ in range(k):
    ad = makea(ad)
    if "".join(map(str, list(ad.values()))) == int("1"*n):
        break

print(" ".join(map(str, list(ad.values()))))

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
As = list(map(int, input().split()))
 
 
def change(arr):
  newAs = [0] * n
  for i, a in enumerate(arr):
    for t in range(max(i - a, 0), min(i + a + 1, n)):
      newAs[t] += 1
  return newAs
 
 
for temp in range(min(k, 40)):
  As = change(As)
print(' '.join(map(str, As)))

Submission status: Time Limit Exceeded

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


def query(lamps):
    counts = [0] * n
    for idx, power in enumerate(lamps):
        start, end = idx - power, idx + power
        if start < 0:
            start = 0
        counts[start] += 1

        if end >= n-1:
            continue
        counts[end+1] -= 1

    now = 0
    for idx, count in enumerate(counts):
        now += count
        lamps[idx] = now


def full_check(counts, full):
    for count in counts:
        if count == full:
            continue
        else:
            return False

    return True


for _ in range(k):
    query(A)
    if full_check(A, n):
        break

print(*A)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def c(A):
    N = len(A)
    B = np.zeros_like(A)
    for i, a in enumerate(A):
        l = max(0, i - a)
        r = min(N - 1, i + a)
        B[l] += 1
        if r + 1 < N:
            B[r + 1] -= 1

    B = np.cumsum(B)
    return B


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


K = min(K, 50)
for _ in range(K):
    A = c(A)

print(' '.join(A.astype(str)))

Submission status: Time Limit Exceeded

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

while K > 0 and A_min < N:
    K -= 1
    b = [0]*(N+1)
    for i in range(N):
        l, r = i - A[i], i + A[i] + 1
        if l < 0:   l = 0
        if r > N:   r = N
        b[l] += 1
        b[r] -= 1

    A[0], A_min = b[0], b[0]
    for i in range(1, N):
        A[i] = A[i-1] + b[i]
        if A_min > A[i]:
            A_min = A[i]

if A_min == N:
    print(' '.join(map(str, [N]*N)))
else:
    print(' '.join(map(str, A)))

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
*A, = map(int, input().split())
for k in range(41):
    B = [0] * N
    for i, a in enumerate(A):
        l = max(0, i - a)
        r = min(N - 1, i + a)
        B[l] += 1
        if r + 1 < N: B[r + 1] -= 1
    for i in range(1, N): B[i] += B[i-1]
    A = B
    if k == K - 1: break
print(*A)

Submission status: Time Limit Exceeded

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

for num in range(k):
    light = []
    ans = [0] * n
    for i,ramp in enumerate(li,1):
        a = max(i - ramp,1)
        b = min(i + ramp,n)
        light.append([a,b])

    for j, m in light:
        for l in range(j,m+1):
            ans[l-1] += 1
    li = ans.copy()
    if ans == [n]*k:
        break

print(*ans,sep=" ")

Submission status: Time Limit Exceeded

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from itertools import accumulate

def resolve():
    it = map(int, sys.stdin.read().split())
    N, K = next(it), next(it)
    A = [next(it) for i in range(N)]

    for k in range(K):
        B = [0]*(N+1)
        for i, di in enumerate(A):
            lhs = max(0, i-di)
            rhs = min(i+di+1, N)

            B[lhs] += 1
            B[rhs] -= 1

        if B[0] == N:
            print(*[N]*N)
            return
        A = accumulate(B)

    print(*list(A)[:-1])

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import copy

def blight(dist,_i):
	l=_i-dist
	r=_i+dist+1
	if l<0:l=0
	if r>n:r=n
	for _ in range(l,r):
		b[_]+=1

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

cnt=0
cntmax=10
while cnt<k:
	b=[0]*n
	for i in range(n):
		blight(a[i],i)
	cnt+=1
	a=copy.deepcopy(b)
print(" ".join(map(str,b)))

Submission status: Time Limit Exceeded

Solution code:
import math
from sys import stdin,stdout
#% 998244353
from heapq import heapify,heappop,heappush
import collections

n,k=list(map(int,stdin.readline().split()))
a=list(map(int,stdin.readline().split()))


for i in range(min(k,100)):
    #nw=[0]*n
    pr=[0]*n
    for x,d in enumerate(a):
        if d==0:
            pr[x]+=1
            if x!=n-1:
                pr[x+1]-=1
            continue
        l=math.floor(x-d)
        r=math.floor(x+d)
        l=max(0,l)
        r=min(n-1,r)
        pr[l]+=1
        if r!=n-1:
            pr[r+1]-=1
    
    for m in range(1,n):
        pr[m]+=pr[m-1]
    
    a[:]=pr


        

for i in a:
    print(i,end=" ")

Submission status: Time Limit Exceeded

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


if K > 1000:
    A = [N] * N
else:
    for count in range(K):
        B = [0] * N
        for i in range(1,N+1):
            # i - A[i]以上、i + A[i]以下のBの要素に1を足す
            startIndex = i - A[i - 1] - 1
            endIndex = i + A[i -1] - 1
            if startIndex < 0:
                startIndex = 0
            if N < endIndex:
                endIndex = N - 1
            for j in range(N):
                if startIndex <= j and j <= endIndex:
                    B[j] = B[j] + 1
        A = B

A=[str(a) for a in A]
A = ' '.join(A)
print(A)

Submission status: Time Limit Exceeded

Solution code:
import copy

def blight(dist,_i):
	l=_i-dist
	r=_i+dist+1
	if l<0:l=0
	if r>n:r=n
	for _ in range(l,r):
		b[_]+=1

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

cnt=0
cntmax=30
while cnt<k:
	b=[0]*n
	for i in range(n):
		blight(a[i],i)
	cnt+=1
	a=copy.deepcopy(b)
print(" ".join(map(str,b)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit

N, K = list(map(int, input().strip().split()))
A = np.array(input().strip().split(), dtype=int)

@njit
def calc(A, step):
    b = np.array([0]*N)
    for i in range(N):
        left = int(max(0, i-A[i]))
        right = int(min(N-1, i+A[i]))
        b[left:right+1] +=1

    if A is not b and step < K:
        step += 1
        A = b.copy()
        return calc(A, step)
    else:
        return b.copy()

ans = calc(A, 1)
ans = [str(x) for x in ans]
print(" ".join(ans))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

# Calculate intensity
N, K = [int(v) for v in input().split(" ")]
A_arr = np.array([int(v) for v in input().split(" ")])
step = np.arange(len(A_arr))
if K > N//2+11:
  print(" ".join([str(N)]*N))
  exit()

def get_Intensity(A_arr):
  inten = np.zeros(len(A_arr))
  for i in range(len(A_arr)):
    isLuminated = np.abs(step - i) < A_arr
    inten[i] = np.sum(isLuminated)
  return inten
Intensity = A_arr
for i in range(K):
  Intensity = get_Intensity(Intensity+1)
  if np.sum(Intensity) == N**2:
    break
print(" ".join([str(v) for v in Intensity.astype(int)]))

Submission status: Time Limit Exceeded

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

for i in range(K):
    B=[0]*(N+1)
    for j in range(N):
        l=max(0,j-A[j])
        r=min(N-1,j+A[j])
        B[l]+=1
        B[r+1]-=1
    for j in range(1,N):
        B[j]=B[j]+B[j-1]
    ok=True
    for j in range(N):
        if B[j]!=N:
            ok=False
            break
    if ok:
        print(*B[:N])
        exit()
        
    A=B.copy()
print(*A[:N])

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
As = list(map(int, input().split()))
 
 
def change(arr):
  newAs = [0] * n
  for i, a in enumerate(arr):
    for t in range(max(i - a, 0), min(i + a + 1, n)):
      newAs[t] += 1
  return newAs
 
 
for temp in range(min(k, 10**2)):
  As = change(As)
print(' '.join(map(str, As)))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import math
N, K = map(int, input().split())
A = list(map(int, input().split()))

if K > 40:
    K = 40

for k in range(K):
    D = [0]*N

    for i in range(N):
        D[i] += 1
        if A[i] == 0:
            continue

        left = math.ceil(i - A[i] - 0.5)
        right = math.floor(i + A[i] + 0.5)
        if left < 0: left = 0
        if right > N-1: right = N-1
    
        for j in range(left, right+1):
            if i == j: continue
            D[j] += 1

    A = D


print(' '.join(map(str,A)))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

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

    for i in range(min(K,100)):
        dm = [0]*N
        for x in range(N):
            dm[max(x - A[x],0)]+=1
            if x+A[x]+1<N:
                dm[x+A[x]+1]+=-1
        for j in range(1,N):
            dm[j]=dm[j-1]+dm[j]
        A[:] = dm[:]
    print(*A)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
import sys

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

for cnt in range(k):
    tmp = [0] * (n + 2)
    for i in range(n):
        power = arr[i]
        left = max(0, i - power + 1)
        right = min(n + 1, i + power + 2)
        tmp[left] += 1
        tmp[right] -= 1
    arr = list(accumulate(tmp))[1:-1]
    if cnt > 50:
        arr = [n] * n
        print(*arr)
        sys.exit()

print(*arr)

Submission status: Time Limit Exceeded

Solution code:
def change(lst):
  lst1 = [0]*len(lst)
  for i in range(len(lst)):
    for j in range(i-lst[i], i+lst[i]+1):
      if j < 0 or j >= len(lst):
        continue
      lst1[j] += 1
  return lst1

n, k = map(int, input().split())
lst = list(map(int, input().split()))
for _ in range(k):
  lst = change(lst)

print(" ".join(map(str, lst)))

Submission status: Time Limit Exceeded

Solution code:
def adjust_light(arr):
    counter = [0] * len(arr)
    is_break = True
    
    for idx in range(0, len(arr)):
        if is_break is True:
            is_break = (arr[idx] == len(arr))
        min = idx - arr[idx]
        if min < 0:
            min = 0
        max = idx + arr[idx]
        if max >= len(arr):
            max = len(arr)-1
        for position in range(min, max+1):
            counter[position] = counter[position] + 1

    return counter, is_break

n, k = list(map(int, input().split(' ')))
arr = list(map(int, input().split(' ')))
for idx in range(0, k):
    arr, is_break = adjust_light(arr)
    if is_break:
        break
print(*arr)