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:
import copy
def resolve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    cut_mode = True
    
    if cut_mode and K + min(A) >= N:
        print(" ".join(map(str, [N]*N)))
        return

    from functools import lru_cache

    @lru_cache(maxsize=100000)
    def func(i, a):
        A_tmp = [0] * len(A)
        #print(A_tmp[i:i+a+1])
        A_tmp[i:i+a+1] = [1]*(len(A_tmp[i:i+a+1]))

        #print(A_tmp[i-a:i+1])
        A_tmp[max(0, i-a):i+1] = [1]*(len(A_tmp[max(0, i-a):i+1]))
        
        #print(A_tmp)
        return A_tmp


    for i in range(K):
        #print("i", i)
        A_next = [0] * len(A)
        for i, a in enumerate(A):
            #print(i, a)
            A_tmp = func(i, a)
            #print("A_tmp", A_tmp)
            A_next = [x + y for (x, y) in zip(A_next, A_tmp)]
            #print("A_next", A_next)

        A = copy.deepcopy(A_next)
        #print("new A: ", A)

        if cut_mode and min(A) == N:
            break 

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

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
# 解説参照
n,k = map(int,input().split())
A = list(map(int,input().split()))

for j in range(min(k,41)):
  B = [0]*(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 = B.copy()
print(*B)

Submission status: Time Limit Exceeded

Solution code:
import copy

n, k = map(int, input().split())
*lumen, = list(map(int, input().split()))
lamps = [set() for i in range(n)]

for h in range(k):
    num_of_lamps = [0] * n

    for i in range(1, n+1):
        x_min = i - lumen[i-1]
        x_max = i + lumen[i-1]
        if x_min < 1:
            x_min = 1
        if x_max > n:
            x_max = n
        for j in range(x_min, x_max+1):
            num_of_lamps[j-1] += 1

    lumen = copy.copy(num_of_lamps)

lumen = ' '.join(list(map(str,lumen)))
print(lumen)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
# import copy
# def input(): return sys.stdin.readline().rstrip()
# input = sys.stdin.readline
input = sys.stdin.buffer.readline
# sys.setrecursionlimit(10 ** 7)

N, K = map(int, input().split())
A = np.array(list(map(int, (input().split()))))
# A = list(map(int, (input().split())))
# nd = np.zeros((N,N), dtype=bool)
# print(*A)
for i in range(K):
    # cnt = [0]*N
    cnt = np.zeros_like(A)
    for j, x in enumerate(A):
        # nd[j, max(j-A[j],0):min(j+A[j]+1,N)] = True
        l = max(j-x,0)
        r = min(j+x+1,N)
        cnt[l] += 1
        if r<N:
            cnt[r] -= 1
        # for k in range(max(j-A[j],0), min(j+A[j]+1,N)):
        #     cnt[k] += 1
    # print(nd)
    # A = np.count_nonzero(nd, axis=0)
    # print(cnt)
    A = np.cumsum(cnt)
    if A[0] == A[N-1] == N:
        break
    # print(*A)

print(*A)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np 
 
N,K = map(int, input().split())
 
A_array = np.array(list(map(int, input().split())))
 
if K > 40:
   K = 40

for k in range(K):
 
    B_list = list()
 
    inf_array = np.array(range(N)) + 0.5 - A_array
    sup_array = np.array(range(N)) + 1.5 + A_array
        
    B_list = [((inf_array <= m+1) & (m+1<=sup_array)).sum() for m in range(N)]
 
    A_array = np.array(B_list)
    
print(' '.join(map(str, A_array)))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys

N,K,*A = map(int, sys.stdin.buffer.read().split())

for _ in range(K):
  Anext = [0 for _ in range(N+1)]
  for i in range(N):
    Anext[max(0,i-A[i])] += 1
    Anext[min(N,i+A[i]+1)] -= 1
  cumsum = 0
  for i in range(N):
    cumsum += Anext[i]
    A[i] = cumsum
  if min(A)==N:
    break

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    N,K = map(int, input().split())
    A = list(map(int, input().split()))
    for i in range(min(K,500)):
        B = [0]*N
        for j in range(N):
            l = max(0,j-A[j])
            r = min(N-1,j+A[j])
            B[l:r+1] = map(lambda x:x+1, B[l:r+1])
        A = B
    print(*A)

main()

Submission status: Time Limit Exceeded

Solution code:
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
empty = [0 for _ in range(N)]

for k in range(min(K, 1000)):
  plus = empty[:]
  for n in range(N):
    l = n - A[n]
    r = n + A[n]
    for i in range(l, r + 1):
      if 0 <= i < N:
        plus[i] += 1
  A = plus

print(' '.join(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,40)
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:
import numpy as np

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

lights = np.array(list(map(int, input().split())))

for _ in range(k):
  if lights.all == n:
    break
  li = lights
  lights = np.array([0]*n)
  for i,x in enumerate(li):
    lights[max(0,i-x):min(n,i+x+1)] += 1

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

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

def do(A):
  B = [0] * (N+2)
  for i, a in enumerate(A, 1):
    l = max(i - a, 0)
    r = min(i + a + 1, N+1)
    B[l] += 1
    B[r] -= 1
  B = list(accumulate(B))
  return B[1:-1]

def check(A):
  for a in A:
    if a < N:
      return False
  return True

for i in range(K):
  A = do(A)
  if check(A):
    print(*A)
    quit()

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, 41 ) ):
    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 = b

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

Submission status: Time Limit Exceeded

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


@njit('i8,i8,i8[::1]', cache=True)
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())
A=list(map(int,input().split()))
cur=A
N2=N*N
for _ in range(K):
    nex=[0]*N
    for i in range(N):
        d=cur[i]
        l=max(0,i-d)
        r=i+d
        nex[l]+=1
        if r+1<N:
            nex[r+1]-=1
    for i in range(1,N):
        nex[i]+=nex[i-1]
    cur=nex
    if sum(cur)==N2:
        break
print(*cur,sep=' ')

Submission status: Time Limit Exceeded

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

A = A + [0]
K = min(K, 50)
for k in range(K):
    t = [0]*(N+1)
    for i in range(N):
        l = max(i-A[i], 0)
        r = min(i+A[i], N-1)
        t[l] += 1
        t[r+1] -= 1

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

    A = S.copy()
print(*S)

Submission status: Time Limit Exceeded

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

def ope(A):
    C = np.array([0]*N)
    for i in range(N):
        B = np.array([0]*N)
        B[i:i+A[i]+1] = 1
        B[max(i-A[i],0):i] = 1
        C = B + C
        #print(B,C)
    return C

for k in range(1,K+1):
    A = ope(A)

print(*A)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np 
 
N,K = map(int, input().split())
 
A_array = np.array(list(map(int, input().split())))
 
if K > 500:
   K = 500

for k in range(K):
 
    B_list = list()
 
    inf_array = np.array(range(N)) + 0.5 - A_array
    sup_array = np.array(range(N)) + 1.5 + A_array
        
    B_list = [((inf_array <= m+1) & (m+1<=sup_array)).sum() for m in range(N)]
 
    A_array = np.array(B_list)
    
print(' '.join(map(str, A_array)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

for i in range(K):
    B = np.zeros((N,)).astype(np.int)
    for j in range(N):
        B[max(0, j - A[j]):min(N, j + A[j] + 1)] += 1
    A = B
    if np.all(A == N):
        break

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

Submission status: Time Limit Exceeded

Solution code:
import sys

import numpy as np

readline = sys.stdin.buffer.readline


def f(N, K, A):
    p = 0
    for i in range(K):
        C = np.zeros(N + 1, dtype=np.int64)

        for j, a in enumerate(A):
            l = max(0, j - a)
            r = min(j + a + 1, N)
            C[l] += 1
            C[r] -= 1

        A = np.cumsum(C)

        if len(set(A[:-1])) == 1:
            p += 1
            if p == 2:
                break
    return A


def solver():
    N, K = map(int, readline().split())
    A = list(map(int, readline().split()))
    A = f(N, K, A)
    print(*A[:-1])


solver()

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
if K <42:
    for q in range(K):
        foo = [1 for k in range(N)]
        for k in range(N):
            for j in range(1, min(A[k]+1, N-k)):
                foo[k+j] +=1
            for j in range(1, min(A[k]+1, k+1)):
                foo[k-j] +=1
        #print(foo)

        for k in range(N):
            A[k] = foo[k]
        #print(A)
else:
    for k in range(N):
        A[k] = N
ans = ""
for k in range(len(A)):
    ans += str(A[k]) + " "

print(ans.rstrip())

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
readline = sys.stdin.readline
N,K = map(int,readline().split())
A = np.array(readline().split(), dtype=np.int64)
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 = np.zeros(N,dtype=np.int64)
    for i in range(N):
        a = A[i]
        end = i+a+1
        if end <=N-1:
            nextgen[end] += -1
        nextgen[max(0,i-a)] += 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:
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))

for k in range(min(K, 1000)):
  plus = [0 for _ in range(N)]
  for n in range(N):
    l = n - A[n]
    r = n + A[n]
    for i in range(l, r + 1):
      if 0 <= i < N:
        plus[i] += 1
  A = plus

print(' '.join(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(min(K, 100)):
    an = [0] * n
    for i in range(n):
        if an[i] < n:
            an[i] += 1
        for j in range(1, a[i]+1):
            if i - j >= 0 and an[i-j] < n:
                an[i-j] += 1
            if i + j < n and an[i+j] < n:
                an[i+j] += 1
    else:
        a = an
print(*a)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
input = sys.stdin.readline

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

lights = np.array(list(map(int, input().split())))

for _ in range(k):
  if lights.all == n:
    break
  li = lights
  lights = np.array([0]*n)
  for i,x in enumerate(li):
    lights[max(0,i-x):min(n,i+x+1)] += 1

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

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]
        start = max(0, i-light)
        end = min(i+light, n)
        for j in range(start, end+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:
import copy
N,K = map(int,input().split())
A = list(map(int,input().split()))

for i in range(K):
  l = [0]*N
  for i in range(N):
    m,p = i-A[i],i+A[i]
    if p+1 <= N-1:
      l[p+1] -= 1
    if m >= 0:
      l[m] += 1
    if m < 0:
      l[0] += 1
  for i in range(N-1):
    l[i+1] += l[i]
  A = copy.deepcopy(l)
  if A[0] == N:
    break 
print(*A)

Submission status: Time Limit Exceeded

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

if K > 41:
    K = 41

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

    for i in range(N):
        left = max(i - A[i], 0)
        right = min(i + A[i], N-1)
        D[left] += 1
        if right + 1 < N: D[right+1] -= 1
    

    for i in range(1, N):
        D[i] += D[i-1]
    A = D


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

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
  if(C==100):
    reuseki = [N]*N
    break
  ruiseki = [0] * N  # 累積和用リスト
  ruiseki[0] = B[0]
  for m in range(N):
      ruiseki[m] = ruiseki[m-1] + B[m]
  A = copy.copy(ruiseki)

print(*ruiseki)

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))
if K >= 500:
    K = 500
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:
import numpy as np 
 
N,K = map(int, input().split())
 
A_array = np.array(list(map(int, input().split())))
 
if K > 1000:
   K = 1000

for k in range(K):
 
    B_list = list()
 
    inf_array = np.array(range(N)) + 0.5 - A_array
    sup_array = np.array(range(N)) + 1.5 + A_array
        
    B_list = [((inf_array <= m+1) & (m+1<=sup_array)).sum() for m in range(N)]
 
    A_array = np.array(B_list)
    
print(' '.join(map(str, A_array)))

Submission status: Time Limit Exceeded

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

def ope(A):
    C = np.array([0]*N)
    for i in range(N):
        B = np.array([0]*N)
        B[i:i+A[i]+1] = 1
        if i - A[i] <= 0:
            B[0:i] = 1
        else:
            B[i-A[i]:i] = 1
        C = B + C
        #print(B,C)
    return C

for k in range(1,K+1):
    A = ope(A)

print(*A)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time
from decimal import *


def I(): return int(input())
def S(): return input()
def MI(): return map(int, input().split())
def MS(): return map(str, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def print_matrix(mat):
    for i in range(len(mat)):
        print(*['IINF' if v == IINF else "{:0=4}".format(v) for v in mat[i]])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']
show_flg = False
# show_flg = True

def pl(x, d):
        return x - d - 0.5


def pr(x, d):
    return x + d + 0.5


def b(A, K):
    for k in range(K):
        ans = []
        for i in range(len(A)):
            c = 0
            for j in range(len(A)):
                l = pl(j, A[j])
                r = pr(j, A[j])

                if i >= l and i <= r:
                    c += 1
            ans.append(c)
        A = ans
        if ans[-1] == len(A):
            print(k, ans)
            return ans
    return A

def main():
    N, K = MI()
    A = LI()
    # N = 100000
    # A = [0] * N
    l_arr = []
    r_arr = []

    # print(b(A, K))

    for i in range(N):
        l = pl(i, A[i])
        r = pr(i, A[i])
        l_arr.append((l, r))
        r_arr.append((r, l))
        # c = r - l
        # v.append(math.ceil(c))
        # print(i+1, 'left', pl(i+1, A[i]), 'right', pr(i+1, A[i]))

    l_arr.sort()
    r_arr.sort()
    # print('l_arr', l_arr)
    # print('r_arr', r_arr)

    ans = [0] * N

    for k in range(min(41, K)):
        nl_arr = []
        nr_arr = []
        for i in range(N):
            l_idx = bisect.bisect_right(l_arr, (i, None))
            r_idx = bisect.bisect_right(r_arr, (i, None))
            ans[i] = l_idx - r_idx
            l = pl(i, ans[i])
            r = pr(i, ans[i])
            nl_arr.append((l, r))
            nr_arr.append((r, l))

        nl_arr.sort()
        nr_arr.sort()
        l_arr = nl_arr
        r_arr = nr_arr

        # print(k, ans[-1])
        if ans[-1] == N:
            break
        # print(idx, l_arr[idx])
        # print(*ans)
    # print(*A)
    # print(k)
    print(*ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math
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, max(K, int(math.log2(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


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

    for i in range(K):
        imos = [0] * (N + 1)
        for j in range(N):
            # s = A[j]
            l, r = max(0, j - A[j]), min(j + A[j], N - 1)
            # print("l,r,s = {} {} {}".format(l, r, s))
            imos[l] += 1
            imos[r + 1] -= 1
        for k in range(N):
            imos[k + 1] = imos[k] + imos[k + 1]
        A = imos[:N]
        if A.count(N) == N:
            print(*A)
            sys.exit()

    print(*imos[:N])


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()))
lights = [0] * N

for _ in range(min(K, 42)):
    lights = [0] * N
    for i, flash in enumerate(A):
        lights[max(0, i-flash)] += 1
        if i+flash < N-1:
            lights[i+flash+1] -= 1
    for i in range(1, N):
        lights[i] += lights[i-1]
    A = copy.deepcopy(lights)

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
# import copy
# def input(): return sys.stdin.readline().rstrip()
# input = sys.stdin.readline
input = sys.stdin.buffer.readline
# sys.setrecursionlimit(10 ** 7)

N, K = map(int, input().split())
# A = np.array(list(map(int, (input().split()))))
A = list(map(int, (input().split())))
# nd = np.zeros((N,N), dtype=bool)
# print(*A)
for i in range(K):
    cnt = [0]*N
    for j in range(N):
        # nd[j, max(j-A[j],0):min(j+A[j]+1,N)] = True
        l = max(j-A[j],0)
        r = min(j+A[j]+1,N)
        cnt[l] += 1
        if r<N:
            cnt[r] -= 1
        # for k in range(max(j-A[j],0), min(j+A[j]+1,N)):
        #     cnt[k] += 1
    # print(nd)
    # A = np.count_nonzero(nd, axis=0)
    # print(cnt)
    A = np.cumsum(cnt)
    if A[0] == A[N-1] == N:
        break
    # print(*A)

print(*A)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
T=list(map(int,input().split()))
if K==0:
    print(T)
    exit()
 
if N<=K:
    L=[N]*N
    print(L)
if K>50:
    K=50
#S = [[0 for j in range(3)] for i in range(2)]　2行3列の場合
S = [[0 for j in range(N)] for i in range(K+1)]
 
for i in range(N):
    S[0][i]=T[i]
 
#print(S)
for i in range(K):
    for j in range(N):
        d=S[i][j]
        #print(d)
        for k in range(max(j-d,0),min(j+d+1,N)):
            #print(k,max(j-d,0),min(j+d+1,K+1))
            S[i+1][k]+=1
 
 
#print(S[K])
 
Z=[str(a) for a in S[K]]
Z=" ".join(Z)
print(Z)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
cur=A
N2=N*N
for _ in range(K):
    nex=[0]*N
    for i in range(N):
        d=cur[i]
        l=max(0,i-d)
        r=i+d
        nex[l]+=1
        if r+1<N:
            nex[r+1]-=1
    for i in range(1,N):
        nex[i]+=nex[i-1]
    cur=nex
    if sum(cur)==N2:
        break
print("{}".format(cur[0]),end='')      
for i in range(1,N):       
    print(" {}".format(cur[i]),end='')
print()

Submission status: Time Limit Exceeded

Solution code:
import math


N,K=map(int,input().split())
A=list(map(int,input().split()))
A.insert(0,0)
Atemp=[0 for i in range(len(A))]
#print(Atemp)
flag=1

for i in range(min(41,K)):
    for j in range(1,len(A)):

        start=max(1,j-A[j])
        end=min(len(A),j+A[j]+1)
        for k in range(start,end):
            Atemp[k]+=1


    A=Atemp.copy()
    Atemp = [0 for p in range(len(A))]
    """
    if flag==1:
        for o in range(1,len(A)):
            A[o]+=(K-i+1)*len(A)
            print(o)
        break
    flag=1
    """
    #print(A)
for m in range(1,len(A)):
    print(A[m],end=" ")

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
for j in range(min(k, 41)):
  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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import math
import sys

N, K = map(int, input().split())
if K > 41:
  K = 41
A = list(map(int, input().split()))
A.insert(0, 0)
B = [0] * (N+1)
ans = [N] * N

def operation():
  global A, B, N
  for i in range(1, N+1):
    left = max(1, math.ceil(i - A[i] - 0.5))
    right = min(N, math.floor(i + A[i] + 0.5))
    B[left] += 1
    if right+1 <= N:
      B[right+1] -= 1
  for i in range(1, N+1):
    B[i] += B[i-1]


operation()

#print(A)
#print(B)

for _ in range(K):
  for i in range(1, N+1):
    if A[i] != B[i]:
      A[i] = B[i]
    B[i] = 0
  operation()

print(*A[1:])

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
L = [1 for _ in range(N)]
for i in range(min(K,30)):
    for j in range(N):
        for k in range(j-A[j],j+A[j]+1):
            if 0 <= k < N and k != j:
                L[k] += 1
    A = L
    L = [1 for _ in range(N)]
print(*A)

Submission status: Time Limit Exceeded

Solution code:
import sys

import numpy as np

readline = sys.stdin.buffer.readline


def f(N, K, A):
    p = 0
    for i in range(K):
        C = np.zeros(N + 1, dtype=np.int64)

        for j, a in enumerate(A):
            l = max(0, j - a)
            r = min(j + a + 1, N)
            C[l] += 1
            C[r] -= 1

        A = np.cumsum(C)

        if len(set(A)) == 1:
            p += 1
            if p == 2:
                break
    return A


def solver():
    N, K = map(int, readline().split())
    A = list(map(int, readline().split()))
    A = f(N, K, A)
    print(*A[:-1])


solver()

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, 50)

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())
T=list(map(int,input().split()))
if K==0:
    print(T)
    exit()
 
if N<=K:
    L=[N]*N
    print(L)
if K>100:
    K=100
#S = [[0 for j in range(3)] for i in range(2)]　2行3列の場合
S = [[0 for j in range(N)] for i in range(K+1)]
 
for i in range(N):
    S[0][i]=T[i]
 
#print(S)
for i in range(K):
    for j in range(N):
        d=S[i][j]
        #print(d)
        for k in range(max(j-d,0),min(j+d+1,N)):
            #print(k,max(j-d,0),min(j+d+1,K+1))
            S[i+1][k]+=1
 
 
#print(S[K])
 
Z=[str(a) for a in S[K]]
Z=" ".join(Z)
print(Z)

Submission status: Time Limit Exceeded

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
import numpy as np

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

    for k in range(K):
        B = np.zeros(N+1, dtype=np.int64)
        for i in range(N):
            di = A[i]
            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 = np.cumsum(B)

    print(*A[:-1])

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

lamp = {}
for i in range(1, N+1):
    lamp[i] = A[i-1]

for k in range(K):
    lamp_next = defaultdict(lambda: 0)
    for i in range(1, N+1):
        l = i - lamp[i]
        if l < 1:
            l = 1
        r = i + lamp[i]
        if r > N:
            r = N
        for j in range(l, r+1):
            lamp_next[j] += 1
    lamp = lamp_next
    if all(lamp[i]==N for i in range(1, N+1)):
        break

ans = [lamp[i] for i in range(1, N+1)]
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import os
import itertools
from collections import deque
import numpy as np

def main():
    if os.getenv("ENV")=='LOCAL':
        sys.stdin = open(os.path.dirname(__file__)+'/input.txt', 'r')

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

    num=np.array([0]*N)
    for i in range(K):
        num=[0]*N
        for n in range(N):
            s = n-A[n] if n-A[n]>=0 else 0
            e = n+A[n]+1 if n+A[n]+1 <= N else N
            # for m in range(s,e):
            #     # print(m)
            #     num[m]+=1
            num[s:e]+=np.array([1]*(e-s))
        # for n in range(N):

        A=num
        if np.min(num)==N:
            break

    # print(A[])
    print(' '.join([str(a) for a in 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()))
for _ in range(min(k,50)):
    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
    A = list(accumulate(c))
print(" ".join(map(str,A)))