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 = (int(v) for v in input().split(" "))
l = [int(v) for v in input().split(" ")]
cnt = len(l)
for _ in range(k): 
    next_l = [0] * cnt
    for i, v in enumerate(l):
        from_idx = max(i - v, 0)
        to_idx = min(i + v, cnt - 1)
        next_l[from_idx:to_idx+1] = [v+1 for v in next_l[from_idx:to_idx+1]]
    l = next_l
    if set(l) == set([n]):
        break
print(" ".join([str(i) for i in l]))

Submission status: Time Limit Exceeded

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

for _ in range(k):
    lst = [0] * n
    for i in range(n):
        num = a[i]
        if i-num >= 0:
            lst[i-num] += 1
        else:
            lst[0] += 1
        if i+num+1 <= n-1:
            lst[i+num+1] -= 1
    mini = lst[0]
    for i in range(1, n):
        lst[i] += lst[i-1]
        mini = min(mini, lst[i])
    a = lst[:]
    if mini == n:
        break
print(' '.join(map(str, a)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n,k = map(int, input().split())
d = np.array(list(map(int, input().split())))
l = np.arange(n)
ans = np.array([0]*n)
cnt = 0

def func(x_left, x_right):
  for x_l,x_r in zip(x_left,x_right):
      ans[x_l:x_r] += 1

while True:
  if np.all(d==n):
    ans = d
    break

  if cnt == k or cnt==100:
    break

  ans *= 0
  x_left = l-d
  x_left[x_left < 0] = 0
  x_right = l+d+1
  x_right[x_left > n] = n
  func(x_left, x_right)
  cnt += 1
  d = ans.copy()

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

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=np.int64)

@njit(cache=True)
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 np.all(a==b) or step>=K:
        return b
    else:
        step += 1
        return calc(b, step)

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

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=[0]*n
num=[]
if k>41:
    ans=[n]*n
    print(*ans)
else:
    for i in range(k):
        num=[0]*(n+1)
        for j in range(n):
            num[max(0,j-a[j])]+=1
            num[min(n,j+a[j]+1)]-=1
        num5=0
        for j in range(n):
            num5+=num[j]
            ans[j]=num5
        a=ans
        if sum(ans)==n*n:
            break
    print(*a)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import numpy as np


def solve(*args: str) -> str:
    n, k = map(int, args[0].split())
    A = np.array(tuple(map(int, args[1].split())), int)

    cur = A
    for _ in range(k):
        prev = cur
        cur = np.zeros(n, int)
        for x, p in enumerate(prev):
            cur[max(0, x-p)] += 1
            if x+p+1 < n:
                cur[x+p+1] -= 1
        cur = cur.cumsum()
        if all(cur == n):
            break
    return ' '.join(map(str, cur))


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Time Limit Exceeded

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

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

print(" ".join([str(item) for item in work]))

Submission status: Time Limit Exceeded

Solution code:
N,K,*A = map(int, open(0).read().split())

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

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

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=np.int64)

@njit(cache=True)
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] += 1
        if right + 1 < N:
            b[right+1] -= 1
    b = np.cumsum(b)
    
    if step>=K:
        return b
    else:
        step += 1
        return calc(b, step)

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

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

cnt = 1
while cnt <= k and min(a) < n:
    li = [0] * (n + 1)
    for i, e in enumerate(a):
        l = max(0, i - e)
        r = min(n, i + e + 1)
        li[l] += 1
        li[r] -= 1

    a = list(accumulate(li))[:-1]

    cnt += 1

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()))

for _ in range(K):
    _A = np.array([0]*N)
    
    for i, a in enumerate(A):
        idx_st = max(0, i - a)
        idx_end = min(N - 1, i + a)
        _A[idx_st:idx_end+1]+=1

    if np.all(_A == N):
        break
    else:
        A = _A
    
print(*A)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=[0]*n
num=[]
if k>41:
    ans=[n]*n
    print(*ans)
else:
    for i in range(k):
        num=[0]*(n+1)
        for j in range(n):
            num[max(0,j-a[j])]+=1
            num[min(n,j+a[j]+1)]-=1
        num5=0
        for j in range(n):
            num5+=num[j]
            ans[j]=num5
        a=ans
    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):
    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)
        B[left] += 1
        if right + 1 < N:
            B[right+1] -= 1
    for i in range(1, N):
        B[i] += B[i-1]
    A = B
print(" ".join(map(str, A)))

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
N,K = map(int,input().split())
A = list(map(int,input().split()))
if N == 1:
    print(1)
else:
    if True:
        old = A
        for _ in range(K):
            li = [0]*N
            for i in range(N):
                MIN = max(0,i-old[i])
                MAX = min(N-1,i+old[i])
                li[MIN] += 1
                if MAX != N-1:
                    li[MAX+1] -= 1
            old = accumulate(li)
            old = list(old)
            if min(old) == N:
                break
        print(*old)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

for _ in range(K):
    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
    B = list(itertools.accumulate(B))
    A = B.copy()
print(*A)

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np
N, K = map(int, input().split())
A = np.array(list(map(int, input().split())), dtype=np.int64)
K = min(K, 20)
def step(A):
    B = np.zeros(N)
    for i, a in enumerate(A):
        l, r = int(max(0, i-a)), int(min(N, i+a+1))
        B[l] += 1
        if r < N:
            B[r] -= 1
    return np.cumsum(B)
for _ in range(K):
    A = step(A)
print(' '.join(map(str, list(map(int, A)))))

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

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

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

for j in range(k):
    if j > 41:
        break

    b = [0] * n

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

    a = list(accumulate(b))

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(0, min(100,K)):
    work = [0] * N
    for i in range(0, N):
        l = max(0, i - A[i])
        r = min(N - 1, i + A[i])
        work[l] += 1
        if (r + 1 < N):
            work[r + 1] -= 1
    for i in range(1, N):
        work[i] += work[i - 1]
    A = work
    if (all([item == N for item in A])):
        break

print(" ".join([str(item) for item in work]))

Submission status: Time Limit Exceeded

Solution code:
#-------------------------------------------------------------------
#-------------------------------------------------------------------
# import io
# import sys

# _INPUT = """\
# 20 200000
# 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
# """
# sys.stdin = io.StringIO(_INPUT)

#-------------------------------------------------------------------
#-------------------------------------------------------------------
#-------------------------------------------------------------------
import sys
def p(*_a):
  #return
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------

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

A = list( map(int, input().split()) )	# 1 2 3 4 5 ...

from itertools import accumulate

for k in range(K):
  B=[0]*N
  for i,d in enumerate(A):
    l = max(0, i-d)
    r = i+d+1

    B[l]+=1
    if r<N: B[r]-=1

  A = list(accumulate(B))
  if A.count(N)==N: break
  # p("A=",A)
  # p("B=",B)

print(*A)

Submission status: Time Limit Exceeded

Solution code:
from math import log2
def main():
    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):
            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:
import copy
n,k = map(int,input().split())
a = list(map(int,input().split()))

def sim(a):
    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]
    return b

for i in range(min(k,41)):
    a = copy.copy(sim(a))
print(*a)

Submission status: Time Limit Exceeded

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

end = False

def one(list):
    b = [0] * n
    for i in range(n):
        l = max(0, i-list[i])
        r = min(i+list[i], n-1)
        b[l] += 1
        if r + 1 < n:
            b[r+1] -= 1
    ee = True
    if b[0] < n:
        ee = False
    for i in range(1, n):
        b[i] += b[i-1]
        if b[i] < n:
            ee = False
    if ee == True:
        end = True
    return b

for i in range(k):
    a = one(a)
    if end:
        break

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_old = A
    A = [0] * (N)
    for idx_A, a in enumerate(A_old):
        A[max(0, idx_A-a)] += 1
        if idx_A+a+1 < N:
            A[idx_A+a+1] -= 1
    for idx_A in range(1, N):
        A[idx_A] += A[idx_A-1]
    if A_old == A:
        break
print(" ".join(map(str, A)))

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
n, K = map(int,input().split())
A = list(map(int,input().split()))
b = [0 for _ in range(n+1)]

for _ in range(min(50, K)):
    for i,a in enumerate(A):
        b[max(0, i-a)] += 1
        b[min(n, i+a+1)] -= 1

    ac = list(accumulate(b))
    A = ac
    b = [0 for _ in range(n+1)]
    
    if sum(ac) == n*n:
        print(*ac[:-1])
        exit()

print(*ac[:-1])

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
ans=list(0 for i in range(N))
ans2=list(N for i in range(N))
for t in range(K):
    temp=A
    for j in range(N):
        ans[j]+=1
        for s in range(1,temp[j]+1):
            if  j+s<=N-1:
                ans[j+s]+=1
            if 0<=j-s:
                ans[j-s]+=1   
    if t!=K-1:
        A=ans
        ans=list(0 for i in range(N))
    if t>=35 and ans==ans2:
       break
       
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from itertools import accumulate

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

light_intensity = A

for k in range(K):
    new_light_intensity = [0 for i in range(N)]
    # 累積和で求める
    for i in range(N):
        left = max(0, i-light_intensity[i])
        right = min(i+light_intensity[i], N)
        new_light_intensity[left] += 1
        if right+1 < N:
            new_light_intensity[right+1] -= 1
    
    light_intensity = list(accumulate(new_light_intensity))
    
    if k > 41:
        print(" ".join(map(str, light_intensity)))
        exit(0)

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

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
imos=[0]*(n+1)
for _ in range(min(k,41)):
    imos=[0]*(n+1)
    for i in range(n):
        imos[max(0,i-a[i])]+=1
        imos[min(n-1,i+a[i])+1]-=1
    for i in range(n-1):
        imos[i+1]+=imos[i]
    for i in range(n):
        a[i]=imos[i]
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):
    flag = True
    for a in A:
        if a != N: flag = False
    if flag: break

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

for a in A[:N]:
    print(a, end=" ")
print()

Submission status: Time Limit Exceeded

Solution code:
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))

n,k = iim()
A = iil()
'''
A = [0]*200000
上記でtryしても41回で全て明るさ200000になる
'''

def imos(l):
    n = len(l)
    tmp = [0]*n
    for i,item in enumerate(l):
        l = max(0,i-item)
        r = min(n-1,i+item)
        tmp[l] += 1
        if r+1 < n:
            tmp[r+1] -= 1
    for i in range(1,n):
        tmp[i] += tmp[i-1]
    return tmp

for _ in range(min(k,50)):
    A = imos(A)
#    print(_,min(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):
  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:
n,k=map(int,input().split())
l=list(map(int,input().split()))
from itertools import accumulate
def update(a):
    ret=[0]*len(a)
    for i,x in enumerate(a):
        ret[max(i-x,0)]+=1
        r=min(n-1,i+x)
        if r==n-1:continue
        ret[r+1]-=1
    return list(accumulate(ret))
for i in range(min(50,k)):
    l=update(l)
print(*l)

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np
N, K = map(int, input().split())
A = np.array(list(map(int, input().split())), dtype=np.int64)
K = min(K, 20)
def step(A):
    B = np.zeros(N)
    for i in range(N):
        a = A[i]
        l, r = int(max(0, i-a)), int(min(N-1, i+a))
        B[l] += 1
        if r < N-1:
            B[r+1] -= 1
    return np.cumsum(B)
for _ in range(K):
    A = step(A)
print(' '.join(map(str, list(map(int, A)))))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
from numba import njit,i8


@njit(i8[:](i8,i8,i8[:],i8,i8))
def loop(N,K,A,left,right):
    for j in range(K):
        B = np.zeros_like(A)
        for i in range(N):
            left = i - A[i]
            right = i + A[i] + 1
            if left < 0:
                left = 0
            if right > N:
                right = N
            B[left:right] += 1
        A = B
    return A


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

    if K >= 41:
        M = 41
    else:
        M = K

    res = loop(N,M,A,0,0)

    print(*res)



main()

Submission status: Time Limit Exceeded

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

diff_list = [0 for num in range(n)]
diff_list[0] = a_in[0]
for i in range(1, n):
    diff_list[i] = a_in[i] - a_in[i-1]

itr = k
if k > 41:
    itr = 41
for i in range(itr):
    new_list = [0 for num in range(n)]
    d_sum = 0
    for j, d in enumerate(diff_list):
        d_sum += d
        if j-d_sum > 0:
            new_list[j-d_sum] += 1
        else:
            new_list[0] += 1
        if d_sum+j+1 < n:
            new_list[j+d_sum+1] -= 1
    # print(new_list)
    diff_list = new_list.copy()

ans = 0
for d in diff_list:
    ans += d
    print(ans, end= ' ')

Submission status: Time Limit Exceeded

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

for i in range(k):
    new = [0] * n
    for j in range(n):
        distance = j - alist[j]
        if distance < 0:
            distance = 0
        last =  j + alist[j]
        if last > n-1:
            last = n-1
        new[distance]+=1
        if last+1 < n:
            new[last+1]-=1
    for j in range(1,n):
        new[j] += new[j-1]
    alist = new.copy()
    if new.count(n) == n:
        break
print(*alist)

Submission status: Time Limit Exceeded

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

for k in range(0, K):
    work = [0] * N
    for i in range(0, N):
        l = max(0, i - A[i])
        r = min(N - 1, i + A[i])
        work[l] += 1
        if (r + 1 < N):
            work[r + 1] -= 1
    for i in range(1, N):
        work[i] += work[i - 1]
    A = work
    if (all([item == N for item in A])):
        break

print(" ".join([str(item) for item in work]))

Submission status: Time Limit Exceeded

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

for i in range(k):
    new = [0] * n
    for j in range(n):
        distance = j - alist[j]
        if distance < 0:
            distance = 0
        last =  j + alist[j]
        if last > n-1:
            last = n-1
        new[distance]+=1
        if last+1 < n:
            new[last+1]-=1
    for j in range(1,n):
        new[j] += new[j-1]
    alist = new.copy()
    if new.count("n") == n:
        break
print(*alist)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
@author: H_Hoshigi
"""

def simulation(N, K, A_list):
    for k in range(min(K, 100)):
        next_A_list = [0 for i in range(N)]
        for i in range(N):
            d = A_list[i]
            for j in range(i-d, i+d+1):
                if j >= 0 and j <= N-1:
                    next_A_list[j] += 1
        A_list = next_A_list[:]
        #print(" ".join([ str(i).zfill(2) for i in A_list]))
    return A_list

def main():
    N, K = map(int, input().split())
    A_list = list(map(int, input().split()))
    print(" ".join([ str(i) for i in simulation(N, K, A_list)]))

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()))
b = [0 for _ in range(n+1)]

for k in range(K):
    for i,a in enumerate(A):
        b[max(0, i-a)] += 1
        b[min(n, i+a+1)] -= 1

    ac = list(accumulate(b))
    A = ac
    b = [0 for _ in range(n+1)]

print(*ac[:-1])

Submission status: Time Limit Exceeded

Solution code:
[n,k]=list(map(int,input().split()))
akarusa=list(map(int,input().split()))


for i in range(k):
    imos=[0]*n
    for j in range(n):
        kagen=max(j-akarusa[j],0)
        jogen=min(j+akarusa[j],n-1)
        imos[kagen]+=1
        if jogen+1<n:
            imos[jogen+1]-=1
    akarusanext=[imos[0]]
    for j in range(1,n):
        akarusanext.append(akarusanext[-1]+imos[j])
    
    akarusa=akarusanext
    if min(akarusa)==n:
        break

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

Submission status: Time Limit Exceeded

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

for _ in range(k):
    if all([e == n for e in a]):
        break

    imos = [0] * (n + 1)
    for i in range(n):
        imos[max(0, i - a[i])] += 1
        imos[min(n, i + a[i] + 1)] -= 1

    a[0] = imos[0]
    for i in range(1, n):
        a[i] = a[i - 1] + imos[i]

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

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,q in enumerate(a):
    b[max(0,i-q)]+=1
    if i+q+1<n:
      b[i+q+1]-=1
  for i in range(1,n):
    b[i]+=b[i-1]
  if a==b:
    break
  a=b[:]
print(*a)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
        n, k = map(int, input().split())
        a = list(map(int, input().split()))
        bn1 = [0] * n
        bn2 = [0] * n
        s = 0
        t = 0
        chec=0
        for _ in range(k):
            for i in range(n):
                b1 = max(i - a[i], 0)
                b2 = min(i + a[i], n - 1)
                bn1[b1] += 1
                bn2[b2] += 1
            for i in range(n):
                s += bn1[i]
                a[i] = s
            s = 0
            for i in range(1, n):
                t += bn2[i - 1]
                a[i] -= t
                if a[i]==n:
                    chec+=1

            if chec==n:
                break
            chec=0
            t = 0
            bn1 = [0] * n
            bn2 = [0] * n
        c = [str(x) for x in a]
        L = " ".join(c)
        print(L)
resolve()

Submission status: Time Limit Exceeded

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

@njit(cache=True)
def light(As,N):
    A0 = np.array([0] * N)
    for i in range(N):
        lp = As[i]
        lmin = max(0, i - lp)
        lmax = min(N - 1, i + lp)
        A0[lmin:lmax + 1] += 1
    return A0

for i in range(K):
    As = light(As, N)
    if sum(As) == N * N:
        break
print(*As,sep=" ")

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
# import numpy as np

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N, K = LI()
A = LI()

"""
明るさが一定値を超えると計算しなくて良い
一定？d > math.floort(N/2)
"""

# lamps = [[0] * N] * (K + 1)
lamps = [[0 for i in range(N)] for j in range(K + 1)]
lamps[0] = A

# lamps = np.array(lamps)

if K > 40:
    b = [str(N)] * N
    print(" ".join(b))
    sys.exit()

for i in range(K):
    tmps = [0 for i in range(N)]
    for j in range(N):
        w = lamps[i][j]
        tmps[max(0, j - w)] += 1
        r = min(N-1, j + w)
        if r + 1 < N:
            tmps[r + 1] -= 1
    hoge = 0
    for j in range(N):
        hoge += tmps[j]
        lamps[i + 1][j] = hoge
ans = lamps[-1]
ans = map(str, ans)
print(" ".join(ans))

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 in range(N):
            imos[min(N,i+A[i]+1)] -= 1
            imos[max(0,i-A[i])] += 1
        
        A[0] = imos[0]
        for i in range(1,N):
            A[i] = A[i-1] + imos[i]
    
    print(*A)

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N, K = map(int, input().split())
A = list( map(int, input().split()))

light_intensity = A

for k in range(K):
    new_light_intensity = [0 for i in range(N)]
    # 累積和で求める
    for i in range(N):
        left = max(0, i-light_intensity[i])
        right = min(i+light_intensity[i], N)
        new_light_intensity[left] += 1
        if right+1 < N:
            new_light_intensity[right+1] -= 1
    
    for i in range(N):
        if i != 0:
            new_light_intensity[i] += new_light_intensity[i-1]

    light_intensity = new_light_intensity
    
    if k > 21:
        print(" ".join(map(str, light_intensity)))
        exit(0)

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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
input = stdin.readline

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

for _ in range(K):
    B = [0 for _ in range(N)]
    end = True

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

        B[left] += 1
        if right + 1 < N:
            B[right + 1] -= 1

    for i in range(N):
        if i > 0:
            B[i] += B[i - 1]
        if B[i] != N:
            end = False

    A = B

    if end:
        break

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

print()

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np
N, K = map(int, input().split())
A = np.array(list(map(int, input().split())), dtype=np.int64)
K = min(K, 20)
for _ in range(K):
    B = A
    A = np.zeros(N)
    for i in range(N):
        b = B[i]
        l, r = int(max(0, i-b)), int(min(N-1, i+b))
        A[l] += 1
        if r < N-1:
            A[r+1] -= 1
    A = np.cumsum(A)
print(' '.join(map(str, list(map(int, A)))))

Submission status: Time Limit Exceeded

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


for i in range(1, k+1):
    tmp_list = [0 for i in range(n)]
    counter = 0
    for j in range(n):
        #tmp_list[j] += 1
        a = a_list[j]
        if a == n:
            counter += 1
        start_k = 0
        end_k = n
        if j - a < 0:
            start_k = 0
        else:
            start_k = j - a
        if j + a > n - 1:
            end_k = n
        else:
            end_k = j + a + 1
        for k in range(start_k, end_k):
            if tmp_list[k] < n:
                tmp_list[k] += 1
    a_list = tmp_list
    if counter == n:
        break
    #print(tmp_list)
print(' '.join(map(str, a_list)))

Submission status: Time Limit Exceeded

Solution code:
import math

def plus(x):
    return x+1

n,k=map(int,input().split())
A=list(map(int,input().split()))
for j in range(min(int(math.log2(n))+1,k)):
    B=[0]*n
    for i in range(n):
        B=B[0:max(0,i-A[i])]+list(map(plus,B[max(0,i-A[i]):min(n,i+A[i]+1)]))+B[min(n,i+A[i]+1):n]
    A=B.copy()

for i in range(n):
    B[i]=str(B[i])

print(' '.join(B))

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
B=[0 for i in range(N)]
#print(B)
for i in range(K):
    for j in range(N):
        for k in range(1,N):
            if j+k<=N-1:
                if A[j+k]>=k:
                    B[j]+=1
                    #print(j,k)
                    #print("22")
            if j-k>=0:
                if A[j-k]>=k:
                    B[j]+=1
                    #print(j,k)
                    #print("33")
        B[j]+=1
    A=B
    B=[0 for i in range(N)]
ans=[str(a) for a in A]
ans=" ".join(ans)
print(ans)

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):
  B=[0]*n
  for j in range(n):
    x = max(0,j-A[j])
    y = min(n,j+A[j]+1)
    for k in range(x,y):
      B[k] += 1
  A = copy.copy(B)
  if A==[n]*n:
    print(*A)
    exit()
print(*A)

Submission status: Time Limit Exceeded

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

diff_list = [0 for num in range(n)]
diff_list[0] = a_in[0]
for i in range(1, n):
    diff_list[i] = a_in[i] - a_in[i-1]

itr = k
if k > 10*math.log(n):
    itr = int(10*math.log(n))
for i in range(itr):
    new_list = [0 for num in range(n)]
    d_sum = 0
    for j, d in enumerate(diff_list):
        d_sum += d
        if j-d_sum > 0:
            new_list[j-d_sum] += 1
        else:
            new_list[0] += 1
        if d_sum+j+1 < n:
            new_list[j+d_sum+1] -= 1
    # print(new_list)
    diff_list = new_list.copy()

ans = 0
for d in diff_list:
    ans += d
    print(ans, end= ' ')

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
tmp = input().split(' ')
A = []
for i in range(N):
    A = A + [int(tmp[i])]

while K > 0 and A.count(N)!=N:
    K = K - 1
    B = [0]*N
    for i in range(N):
        for j in range(N):
            if A[j] >= abs(j-i):
                B[i] = B[i]+1
    A = B

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(0, K):
    work = [0] * N
    for i in range(0, N):
        l = max(0, i - A[i])
        r = min(N - 1, i + A[i])
        work[l] += 1
        if (r + 1 < N):
            work[r + 1] -= 1
    for i in range(1, N):
        work[i] += work[i - 1]
    A = work

print(" ".join([str(item) for item in work]))