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,*a=map(int,open(0).read().split())
for _ in range(min(k,99)):
  b=[0]*n
  for i,q in enumerate(a):
    b[max(0,i-q)]+=1
    if (r:=i+q+1)<n:
      b[r]-=1
  for i in range(1,n):
    b[i]+=b[i-1]
  a=b[:]
print(*a)

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,100)):
    A = imos(A)
#    print(_,min(A))

print(*A)

Submission status: Time Limit Exceeded

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

for k in range(K):
  copy=[0]*N
  for i in range(N):
    kido=light[i]
    smin=max(0,i-kido)
    smax=min(N-1,i+kido)
    for j in range(smin, smax+1):
      copy[j]+=1
  light=copy
  if N==min(light):
    break
print(*light)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
li_light = list(map(int, input().split()))
 
def func(tuyosa):
  basho = [0] * n
  # 光が当たっている部分
  for i in range(n):
    min = i + 1 - tuyosa[i]
    max = i + 1 + tuyosa[i]
    a = 0
    while a <= n:
      if 1 <= min <= n:
        basho[min - 1] += 1
      min += 1
      if min > max:
        break
  return basho

if k > 41:
  k = 41
for i in range(k):
  li_light = (func(li_light))
 
for k in li_light:
  print(k, end=" ")

Submission status: Time Limit Exceeded

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

def imo(a):
    imos=np.zeros(n+1,dtype="int64")
#print(arr[0])
    for i in range(n):
        imos[max(0,i-arr[i])]+=1
        imos[min(n,i+arr[i]+1)]-=1
    
    immo=np.zeros(n+1)
    immo=np.cumsum(imos)
    return immo[:n]


for _ in range(min(k,41)):
    arr=imo(arr)
    
print(*arr)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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



for j in range(K):
    Alight=np.array([0]*N)
    for i in range(N):
        fro=i-A[i]
        to=i+A[i]+1
        if fro < 0:
            fro=0
        #for k in range(fro,to):
        Alight[fro:to]+=1
        #print(fro)
        #print(to)
    #print(Alight)
    A=Alight[:]
    if min(Alight) == N:
        break

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

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

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

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

Submission status: Time Limit Exceeded

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

B = [1 for a in A]

K = min(K, 500)

for k in range(K):
    for i in range(N):
        for j in range(1, A[i]+1):
            if i - j >= 0:
                B[i-j] += 1
            if i + j < N:
                B[i+j] += 1
    A = [b for b in B]
    B = [1 for a in A]

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
from functools import lru_cache

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

if k > 41:
    k = 41

@ lru_cache(maxsize=None)
def main():
    global a
    for _ in range(k):
        b = [0]*(n+1)
        for i,j in enumerate(a):
            b[max(0,i-j)] += 1
            b[min(n,i+j+1)] -= 1
        a = list(accumulate(b))
        for i in range(n+1):
            if a[i] >= n:
                a[i] = n
    print(*a[:-1])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def read_input(trans=int):
    return list(map(trans, input().split()))


N, K = read_input()
A = np.array(read_input(), dtype="int")

K = np.minimum(K, 41)

for _ in range(K):
    B = np.zeros(N, dtype="int")
    for i in range(N):
        start = np.maximum(i-A[i], 0)
        end = np.minimum(i+A[i], N-1)

        B[start] += 1
        if end+1 < N:
            B[end+1] -= 1
    B = np.cumsum(B)
    A = B


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

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
 
readline = sys.stdin.readline
 
def loop(n,k,a):
    for j in range(k):
        b = np.zeros(n+1, dtype=np.int64)
        for i in range(n):
            b[max(i-a[i], 0)] += 1
            b[min(i+a[i]+1, n)] -= 1
        a = np.cumsum(b)[:-1]
        if np.all(a==n):
            return(a)
            break
    else:
        return(a)
 
 
n, k = map(int, readline().split())
a = np.array(readline().split(), dtype=np.int64)
 
ans = loop(n,k,a)
print(*ans)

Submission status: Time Limit Exceeded

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

for _ in range(min(K, 100)):
    b = [0]*N
    for i, a in enumerate(A):
        for j in range(max(i-a, 0), min(a+i+1, N)):
            b[j] += 1
    A = b

print(" ".join(str(a) for a in 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)
for _ in range(min(K, (int(math.log2(N))+1))):
    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:
import numpy as np
N, K = map(int, input().split())
A = np.array(list(map(int, input().split())), dtype=np.int64)


def solve(N, K, A):
    # 一度照らされると二度目以降は確実に照らされるはず。
    for i in range(K):
        # j番目の電球を操作
        B = np.zeros(N + 1, dtype=np.int64)
        for j in range(N):
            # 左辺を確認
            B[max(j - A[j], 0)] += 1
            # 右辺を確認(なんで-1?)
            B[min(j + A[j] + 1, N)] -= 1

        A = np.cumsum(B)[:-1]

        if np.all(A == N):
            return A

    else:
        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]=list(map(int,input().split()))
akarusa=list(map(int,input().split()))


for i in range(k):
    akarusanext=[0]*n
    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()))
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
  if k>N:
    break
  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()))

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

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

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

Submission status: Time Limit Exceeded

Solution code:
N, K = list(map(int,input().split()))
A =  list(map(int,input().split()))
 
 
for _ in range(K):
  brighted = {}
 
  for i in range(N):
    light_min = max(i + 1 - A[i] - 0.5,0.5)
    light_max = min(i + 1 + A[i] + 0.5,N + 0.5)
    while 1:
      light_min += 1
      ac = int(light_min)
      if light_max >= ac:
        if ac not in  brighted:
          brighted[ac] = 1
        else:
          brighted[ac] += 1
      else:
        break
 
  for key, value in brighted.items():
    A[key-1] = value
    
print(' '.join(map(str, A)))

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

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=list(accumulate(ims))
    
for i in range(n):
    print(dp2[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):
   B=[0]*N
   for l in range(N):
      if A[l]==0:
         B[l]+=1
      else:
         for i in range(max(l-A[l],0),min(l+A[l]+1,N),1):
            B[i]+=1
   A=B
print(*A)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
 
for _ in range(min(K,50)):
  A = [sum([A[nx] >= abs(nx- n) for nx in range(N)]) for n in range(N)]
print(" ".join(map(str,list(map(int,A)))))

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 > 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()))
if K <41:
    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


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

Submission status: Time Limit Exceeded

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

A = A + [0]
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

    A = [0]*N
    A[0] = t[0]
    for i in range(1, N):
        A[i] = A[i-1] + t[i]
    
    if all(a == N for a in A):
        print(*A)
        exit()

print(*A)

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 = np.array(input().split(), dtype=np.int64)
# 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


def read_input(trans=int):
    return list(map(trans, input().split()))


N, K = read_input()
A = np.array(read_input(), dtype="int")
coordinate = np.arange(1, N+1)

K = np.minimum(K, 41)

for _ in range(K):
    B = np.zeros(N, dtype="int")
    for i in range(N):
        end = np.minimum(coordinate[i]+A[i], N)
        start = np.maximum(coordinate[i]-A[i], 1)

        B[start-1] += 1
        if end < N:
            B[end] -= 1
    B = np.cumsum(B)
    A = B.copy()


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

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

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:
def resolve():
        n, k = map(int, input().split())
        a = list(map(int, input().split()))
        bn1 = [0] * n
        bn2 = [0] * n
        s = 0
        t = 0
        check=[0]*n
        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 and check[i]==0:
                    check[i]=1
            if sum(check)==n:
                break
            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:
# tokio marine 2020 C.Lamps
import copy
# N = int(input())
N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]

for i in range(K):
    B = [0 for k in range(N)]
    for j in range(N):
        L = A[j]
        l = max(j-L, 0)
        r = min(j+L, N-1)
        B[l] += 1
        if r + 1 < N:
            B[r+1] -= 1
    for j in range(1, N):
        B[j] += B[j-1]
    A = copy.deepcopy(list(B))
    if len(set(A)) == 1 and A[0] == N:
        break
print(*A)

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 >= 50:
    K = 50
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:
"""
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,50)):
    A = update(A)
 
print(*A)

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 > 50:
        print(" ".join(map(str, light_intensity)))
        exit(0)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
import copy
from itertools import accumulate
input=sys.stdin.readline
def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    ans = copy.deepcopy(A)
    for _ in range(K):
        cumsum = [0]*N
        for i,a in enumerate(ans):
            l = max(0,i-a)
            r = min(N-1,i+a)
            cumsum[l] += 1
            if r+1 < N:
                cumsum[r+1] -= 1
        ans = list(accumulate(cumsum))
        if ans[0] == N:
            break
    print(*ans)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
if K <41:
    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:
n,k = map(int,input().split())
A = list(map(int,input().split()))

for j in range(min(k,45)):
  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 sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
s_readline = sys.stdin.readline


def solve():

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

    #N, K = 2 * (10**5), 10000000
    #A = [0] * N

    for k in range(K):

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

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

        A = B

        if s == N * N:
            print(' '.join(map(str, A)))
            exit()

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


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import math

N, K = map(int, input().split())
K = min(41, K)
A = list(map(int, input().split()))
A.insert(0, 0)
ans = [N] * N

def operation():
  global A, N
  B = [0] * (N+1)
  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]
  return B


operation()

#print(A)
#print(B)

for _ in range(K):
  A = operation()

print(*A[1:])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
# 初期入力
import sys
input = sys.stdin.readline
N,K = (int(i) for i in input().split())
A = list(map(int, input().split()))
#B =np.zeros(N)
A =np.array(A,dtype=np.int64)
#
l =0
r =N
for j in range(K):
    B =np.zeros(N,dtype=np.int64)
    for i in range(N):
        index =A[i]
        if i-index <0:
            l=0
        else:
            l =i -index
        if i +index >N:
            r =N 
        else:
            r =i +index +1
        B[l:r] +=1 
        if np.all(B >=N):
            print(*B)
            sys.exit(0)
    A =B
    
print(*B)

Submission status: Time Limit Exceeded

Solution code:
import itertools
def main():
    n,k = tuple([int(t)for t in input().split()])

    a = tuple([int(t)for t in input().split()])

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

    print(*a)



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
li_light = list(map(int, input().split()))
 
def func(tuyosa):
  basho = [0] * n
  # 光が当たっている部分
  for i in range(n):
    min = i + 1 - tuyosa[i]
    max = i + 1 + tuyosa[i]
    a = 0
    while a <= n:
      if 1 <= min <= n:
        basho[min - 1] += 1
      min += 1
      if min > max:
        break
  return basho
 
for i in range(k):
  li_light = (func(li_light))
  if li_light.count(n) == n:
    break
 
for k in li_light:
  print(k, end=" ")

Submission status: Time Limit Exceeded

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

def r(i,a):
    x1=i+1-a
    x2=i+2+a
    return [l for l in range(x1,x2) if(l>0 and l-1<N)]

for k in range(K):
    if(A==[N]*N):
        break
    B=[0]*N
    for i in range(N):
        for m in r(i,A[i]):
            B[m-1]+=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 _ 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

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

Submission status: Time Limit Exceeded

Solution code:
l = input().split()
N = int(l[0])
K = int(l[1])

A = [int(x) for x in input().split()]

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

for i in range(K):
    for j in range(N):
        # dp[i+1][j] += dp[i][j]
        # if dp[i][j] == 0:
        dp[i+1][j] += 1
            
        
        left = j-dp[i][j]
        right = j+dp[i][j]
        if left<0:
            left = 0
        if right > N-1:
            right = N-1
        
        for k in range(left, j):
            dp[i+1][k] += 1
            # print("left:", end="")
            # print(i, k)
            # if i>0:
                # print("{} と {}",i, k)
        for k in range(j+1, right+1):
            dp[i+1][k] += 1
            # print("right:", end="")
            # print(i, k)
            # if i>0:
                # print("{} と {}",i, k)
        
        # for k in range(left, right+1):
        #     if k != j:
        #         dp[i+1][k] += 1
        

print(*dp[K])
# print(*dp)

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 set(light_intensity) == set([N]):
        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())
li = list(map(int,input().split()))

for num in range(min(k,41)):
    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

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))
        elif N > 20 and N/2 < 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 math

N, K = map(int, input().split())
# if K >= 1000 and N / 2 + 1 < K:
#     K = int(math.sqrt(N))
if K >= 100:
    K = 100
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())
T=list(map(int,input().split()))
if K==0:
    print(T)
    exit()
 
if N<=K:
    L=[N]*N
    print(L)
if K>30:
    K=30
#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)
        A=max(j-d,0)
        B=min(j+d+1,N)
        for k in range(A,B):
            #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:
import math
n, k = map(int, input().split())
a = list(map(int, input().split()))

limit = math.log(n)

if k >= n:
    for i in range(n-1):
        print(n, end=" ")
    print(n)
    exit()

for _ in range(k):
    list = [1]*n
    for i, d in enumerate(a):
        if d == 0:
            continue
        for j in range(-d, d+1):
            if j == 0:
                continue
            if i+j >= 0:
                try:
                    list[i+j] += 1
                    # print(i, j)
                except:
                    pass
    if _ > limit:
        break
    a = list.copy()
for i in range(n-1):
    print(a[i], end=" ")
print(a[-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def read_input(trans=int):
    return list(map(trans, input().split()))


N, K = read_input()
A = np.array(read_input(), dtype="int")
coordinate = np.arange(1, N+1)

for _ in range(K):
    B = np.zeros(N, dtype="int")
    for i in range(N):
        end = np.minimum(coordinate[i]+A[i], N)
        start = np.maximum(coordinate[i]-A[i], 1)
        
        B[start-1] += 1
        if end < N:
            B[end] -= 1
    B = np.cumsum(B)
    A = B.copy()
    
    if (A==N).sum()==N:
      break

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