Problem:


Score : 500 points

Problem Statement

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

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

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

Find the intensity of each bulb after the K operations.

Constraints

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

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

0 \leq A_i \leq N

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 \ldots A_N

Output

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

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

Sample Input 1

5 1
1 0 0 1 0

Sample Output 1

1 2 2 1 2 

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

Sample Input 2

5 2
1 0 0 1 0

Sample Output 2

3 3 4 4 3 



Sample input:
5 1
1 0 0 1 0


Sample output:
1 2 2 1 2

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
c=[n for i in range(n)]
for j in range(k):
    d=[0 for i in range(n+1)]
    for i in range(n):
        d[max(i-a[i],0)]+=1
        d[min(i+a[i]+1,n)]-=1
    e=[d[0]]
    for i in range(n-1):#ちょっと特殊な累積和 普通のものの[1:-1]
        e.append(e[i]+d[i+1])
    #print(d,e,sep='\n')
    #print(e)
    a=e
    if e==c:
        break
print(*a)

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

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

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

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int, input().split())
A_list = [0] + [int(e) for e in input().split()]

steady_state_A_list = [0]+[N for _ in range(1,N+1)]

#そのままやると10**5 **2　でTLE
#自分の座標を通過するまでは、自分の明るさ＝照射範囲は変わらない

#is_lighted[i][j]…iの座標のランプがjを照らすなら1否なら0の行列
#これで照らされる個数をカウントしていけばOK

edge = [[0 for _ in range(N+2)]]
center = [[0] + [0 for _ in range(1,N+1)] + [0] for i in range(N)]
is_lighted = edge + center + edge

def calc_lighted_area():
    for i in range(1,N+1):
        d = A_list[i]
        
        #照射範囲を求める
        if i-d < 0:
            left_side = 0
        else:
            left_side = i-d

        if i+d > N:
            right_side = N+1
        else:
            if d != 0:
                right_side = i+d+1
            else:
                right_side = left_side + 1
        
        is_lighted[i][left_side:right_side] = [1 for i in range(right_side - left_side)]

#for i in range(1,N+1):
#    print(is_lighted[i][1:N+1])

calc_lighted_area()

for j in range(K):
    for i in range(1,N+1):
        Bi = sum([row[i] for row in is_lighted])        
        A_list[i] = Bi
    calc_lighted_area()

    if A_list == steady_state_A_list:
        break

print(' '.join(map(str, A_list[1:N+1])))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(41):
    if i == k:
        break
    imos = [0] * (n + 1)
    for j in range(n):
        l = max(0, j - a[j])
        r = min(n - 1, j + a[j])
        imos[l] += 1
        imos[r + 1] -= 1
    for j in range(n):
        imos[j + 1] += imos[j]
    a = imos[:-1]
print(*a, sep=" ")

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N,K,*A = map(int,open(0).read().split())
na = np.array(A)
K = min(K,100)

for i in range(K):
    if all(na) == N:
        break
    B = [0] * N
    nb = np.array(B)
    for n in range(N):
        L = max(0, n-na[n])
        R = min(N-1 , n + na[n])
        nb[L] += 1
        if R+1 != N:
            nb[R+1] -= 1
      
    na = nb.cumsum()        
 
print(*na,sep=" ")

Submission status: Time Limit Exceeded

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


for k in range(K):
    L=[0]*N
    for i in range(N):
        for j in range(max(i-A[i],0),min(i+A[i]+1,N)):
            L[j]+=1
    if L.count(N)==N:
      print(' '.join(map(str,L)))
      exit(0)
    else:
      A=L
	
 
print(' '.join(map(str,L)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N,K,*A = map(int,open(0).read().split())
na = np.array(A)

for i in range(K):
    if all(na) == N:
        break
    B = [0] * N
    nb = np.array(B)
    for n in range(N):
        L = max(0, n-na[n])
        R = min(N-1 , n + na[n])
        nb[L] += 1
        if R+1 != N:
            nb[R+1] -= 1
      
    na = nb.cumsum()        
 
print(*na,sep=" ")

Submission status: Time Limit Exceeded

Solution code:
import math
n,k = map(int, input().split())
a_array = list(map(int, input().split()))
 
a_tmp = [0] * n
a_range = []*n
#print(a_tmp)
 
for i in range(k):
    for x in range(n):
        # まずは一つ目が照らしている電球を考える
        # 範囲は式通り
        left = math.ceil(x - a_array[x] - 0.5)
        if left < 0:
            left = 0
        right  = math.floor(x + a_array[x] + 0.5)
        if right > n - 1:
            right = n -1
        #a_tmp = [a_tmp[i]+1 if (i>=left and i<right+1) else a_tmp[i] for i in range(0, n)]
        
        a_tmp2 = [0] * n
        a_insert = [1] * (right+1 - left)
        #print(a_insert)
        
        #a_tmp2[left:right-1] = a_insert
        a_tmp2[left:right] = a_insert
        #print(a_tmp2)
        
        a_tmp = [x + y for (x, y) in zip(a_tmp2,a_tmp)]
 
        #for j in range(left, right+1):
            #a_tmp[j] += 1
        
        #print(a_tmp)
    a_array = a_tmp
    a_tmp = [0]*n
 
ans = " ".join(map(str, a_array))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())	
A = list(map(int,input().split()))
B = [0]*N
K = min(K,50)
for _ in range(K):
    for i in range(len(A)):
        if i-A[i] >= 0 and i+A[i]+1 <= N:
            for j in range (i-A[i],i+A[i]+1):
                B[j] += 1
        elif i-A[i] < 0 and i+A[i]+1 <= N:
            for j in range(0,i+A[i]+1):
                B[j] += 1
        elif i-A[i] >= 0 and i+A[i]+1 > N:
            for j in range(i-A[i],N):
                B[j] += 1
        else:
            for j in range(N):
                B[j] +=1
    A = B[:]
    B = [0]*N
ans = ' '.join(map(str,A))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())	
A = list(map(int,input().split()))
B = [0]*N
K = min(K,100)
for _ in range(K):
    for i in range(len(A)):
        if i-A[i] >= 0 and i+A[i]+1 <= N:
            for j in range (i-A[i],i+A[i]+1):
                B[j] += 1
        elif i-A[i] < 0 and i+A[i]+1 <= N:
            for j in range(0,i+A[i]+1):
                B[j] += 1
        elif i-A[i] >= 0 and i+A[i]+1 > N:
            for j in range(i-A[i],N):
                B[j] += 1
        else:
            for j in range(N):
                B[j] +=1
    A = B[:]
    B = [0]*N
ans = ' '.join(map(str,A))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
n, k = map(int, sys.stdin.readline().rstrip().split())
an = list(map(int, sys.stdin.readline().rstrip().split()))


import numpy as np


t= min(k, 45)
from numba.decorators import jit

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

        if i+ a[i]+1 <n:
            bn[i+a[i]+1] -=1
    return np.cumsum(bn)


for k in range(t):
    an = imos(an, n)


print(*an)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,k = map(int, input().split())
a1 = list(map(int, input().split()))
a = np.asarray(a1, dtype=int)
for i in range(k):
    b = np.zeros(n, dtype=int)
    for j in range(n):
        mi = j-a[j]
        ma = j+a[j]
        if mi<0:
            mi = 0
        if ma>=n:
            ma = n-1
        b[mi:ma+1:]+=1
    a = b
    if all([x==n for x in a]):
        break
print(*a)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from itertools import*
n, k, *A = map(int, open(0).read().split())

def imos(l, r):
    B[l] += 1
    if r + 1 != n:
        B[r + 1] -= 1

for _ in [0] * min(k, 41):
    B = [0] * n
    for i, a in enumerate(A):
        imos(max(i - a, 0), min(i + a, n - 1))
    *A, = accumulate(B)
print(*A)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
from numba import njit
 
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
def update(A):
  N = len(A)
  B = np.zeros_like(A)
  for i,x in enumerate(A):
    l = max(0, i-x)
    r = min(N-1, i+x)
    B[l] += 1
    if r + 1 < N:
      B[r+1] -= 1
  B = np.cumsum(B)
  return B
    
    
N,K = map(int, readline().split())
A = np.array(read().split(), np.int64)

for _ in range(K):
  A = update(A)
  if np.all(A==N):
    break
print(' '.join(A.astype(str)))

Submission status: Time Limit Exceeded

Solution code:
import copy
import math
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = [0] * n
if k < 41:
    for _ in range(k):
        for i in range(n):
            light = 0
            for j in range(n):
                if i < j:
                    if (j - a[j] - 0.5) < i:
                        light += 1
                else:
                    if (j + a[j] + 0.5) > i:
                        light += 1
            b[i] = light
        a = copy.deepcopy(b)
else:
    for _ in range(41):
        for i in range(n):
            light = 0
            for j in range(n):
                if i < j:
                    if (j - a[j] - 0.5) < i:
                        light += 1
                else:
                    if (j + a[j] + 0.5) > i:
                        light += 1
            b[i] = light
        a = copy.deepcopy(b)
for i in a:
    print(i, end=' ')

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
for i in range(k):
  C = [0]*(n+1)
  for j in range(n):
    C[max(0, j-A[j])] += 1
    C[min(n-1, j+A[j])+1] -= 1
  v = 1
  for j in range(n):
    C[j+1]=C[j+1]+C[j]
    if C[j]!=n:
      v = 0
  if v:
    break
  A = C
C = [str(c) for c in C[:-1]]
print(' '.join(C))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,k = map(int, input().split())
a1 = list(map(int, input().split()))
a = np.asarray(a1, dtype=int)
for i in range(k):
    b = np.zeros(n, dtype=int)
    for j in range(n):
        mi = j-a[j]
        ma = j+a[j]
        if mi<0:
            mi = 0
        if ma>=n:
            ma = n-1
        b[mi:ma+1:]+=1
    a = b
    if np.sum(a)==n*n:
        break
print(*a)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
from numba import njit
 
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
def update(A):
  N = len(A)
  B = np.zeros_like(A)
  for i,x in enumerate(A):
    l = max(0, i-x)
    r = min(N-1, i+x)
    B[l] += 1
    if r + 1 < N:
      B[r+1] -= 1
  B = np.cumsum(B)
  return B
    
    
N,K = map(int, readline().split())
A = np.array(read().split(), np.int64)
 
K = min(K, 50)
for _ in range(K):
  A = update(A)
print(' '.join(A.astype(str)))

Submission status: Time Limit Exceeded

Solution code:
# wa
import copy
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = [1] * n
for _ in range(k):
    for i in range(n):
        light = 0
        for j in range(n):
            if i < j:
                if (j - a[j] - 0.5) < i:
                    light += 1
            else:
                if (j + a[j] + 0.5) > i:
                    light += 1
        b[i] = light
    a = copy.deepcopy(b)
for i in a:
    print(i, end=' ')

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import accumulate

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def solve():
    n, k = nm()
    a = nl()
    for _ in range(k):
        b = [0]*n
        for i in range(n):
            if i > a[i]:
                b[i-a[i]] += 1
            else:
                b[0] += 1
            if i + a[i] + 1 < n:
                b[i + a[i] + 1] -= 1
        a = list(accumulate(b))
        if min(a) >= n:
            break
    print(*a)
    return

solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
n, k = map(int, sys.stdin.readline().rstrip().split())
an = list(map(int, sys.stdin.readline().rstrip().split()))


import numpy as np


t= min(k, 45)


for k in range(t):
    bn = [0]*n
    for i in range(n):
        bn[max(i - an[i], 0)] += 1

        if i+ an[i]+1 <n:
            bn[i+an[i]+1] -=1

    an = np.cumsum(bn)


print(*an)

Submission status: Time Limit Exceeded

Solution code:
import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def solve():
    n, k = nm()
    a = nl()
    b = [0]*n
    for _ in range(k):
        for i in range(n):
            if i > a[i]:
                b[i-a[i]] += 1
            else:
                b[0] += 1
            if i + a[i] + 1 < n:
                b[i + a[i] + 1] -= 1
        for i in range(n-1):
            b[i+1] += b[i]
            a[i] = 0
        a[-1] = 0
        b, a = a, b
        if min(a) >= n:
            break
    print(*a)
    return

solve()

Submission status: Time Limit Exceeded

Solution code:
import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def solve():
    n, k = nm()
    if k > 42:
        k = 42
    a = nl()
    b = [0]*n
    for _ in range(k):
        for i in range(n):
            if i > a[i]:
                b[i-a[i]] += 1
            else:
                b[0] += 1
            if i + a[i] + 1 < n:
                b[i + a[i] + 1] -= 1
        for i in range(n-1):
            b[i+1] += b[i]
            a[i] = 0
        a[-1] = 0
        b, a = a, b
    print(*a)
    return

solve()

Submission status: Time Limit Exceeded

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

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

print(*A)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
from numba import njit
 
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def update(A):
  N = len(A)
  B = np.zeros_like(A)
  for i,x in enumerate(A):
    l = max(0, i-x)
    r = min(N-1, i+x)
    B[l] += 1
    if r + 1 < N:
      B[r+1] -= 1
  B = np.cumsum(B)
  return B
    
    
N,K = map(int, readline().split())
A = np.array(read().split(), np.int64)
 
K = min(K, 100)
for _ in range(K):
  A = update(A)
print(' '.join(A.astype(str)))

Submission status: Time Limit Exceeded

Solution code:
import copy

def check(arr, val):
    for i in arr:
        if not i == val:
            return False
    return True

n, k = map(int, input().split())
a = [int(_) for _ in input().split()]

for _ in range(k):
    aa = [0] * n
    for i in range(n):
        aa[max(0, i-a[i])] += 1
        r = i+a[i]+1
        if r < n:
            aa[r] -= 1
    for i in range(1, n):
        aa[i] += aa[i-1]
    a = aa.copy()
    if check(a, n):
        break

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
from numba import njit
 
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
@njit('(i8[::1],)', cache=True)
def update(A):
  N = len(A)
  B = np.zeros_like(A)
  for i,x in enumerate(A):
    l = max(0, i-x)
    r = min(N-1, i+x)
    B[l] += 1
    if r + 1 < N:
      B[r+1] -= 1
  B = np.cumsum(B)
  return B
    
    
N,K = map(int, readline().split())
A = np.array(read().split(), np.int64)
 
k = min(K, 100)
for _ in range(K):
  A = update(A)
print(' '.join(A.astype(str)))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
from numba import njit
 
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
@njit
def update(A):
  N = len(A)
  B = np.zeros_like(A)
  for i,x in enumerate(A):
    l = max(0, i-x)
    r = min(N-1, i+x)
    B[l] += 1
    if r + 1 < N:
      B[r+1] -= 1
  B = np.cumsum(B)
  return B
    
    
N,K = map(int, readline().split())
A = np.array(read().split(), np.int64)
 
k = min(K, 100)
for _ in range(K):
  A = update(A)
print(' '.join(A.astype(str)))

Submission status: Time Limit Exceeded

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


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


def update(A):
  N = len(A)
  B = np.zeros_like(A)
  for i,x in enumerate(A):
    l = max(0, i-x)
    r = min(N-1, i+x)
    B[l] += 1
    if r + 1 < N:
      B[r+1] -= 1
  B = np.cumsum(B)
  return B
    
    
N,K = map(int, readline().split())
A = np.array(read().split(), np.int64)

k = min(K, 100)
for _ in range(K):
  A = update(A)
print(' '.join(A.astype(str)))

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,k=map(int,input().split())
l=list(map(int,input().split()))
if k>42:
    l=[n]*n
    print(*l)
else:
    for _ in range(k):
        countl=[0]*(n+1)
        for i in range(n):
            countl[max(1,i+1-l[i])]+=1
            if i+2+l[i]<=n:
                countl[i+2+l[i]]-=1
            
        l=list(itertools.accumulate(countl))
        l.remove(l[0])
    print(*l)

Submission status: Time Limit Exceeded

Solution code:
n,k,*l=map(int,open(0).read().split())
for _ in range(k):
  s=[0]*(n+1)
  for i in range(n):
    s[max(i-l[i],0)]+=1
    s[min(i+l[i]+1,n)]-=1
  for i in range(n):
    s[i+1]+=s[i]
  s.pop()
  if s==l: break
  l=s
print(*l)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
for i in range(k):
  C = [0]*(n+1)
  for j in range(n):
    p = max(0, j-A[j])
    q = min(n-1, j+A[j])
    C[p] += 1
    C[q+1] -= 1
  v = 1
  for j in range(n):
    C[j+1]=C[j+1]+C[j]
    if C[j]!=n:
      v = 0
  if v:
    break
  A = C
C = [str(c) for c in C[:-1]]
print(' '.join(C))

Submission status: Time Limit Exceeded

Solution code:
import sys
n, k = map(int, sys.stdin.readline().rstrip().split())
an = list(map(int, sys.stdin.readline().rstrip().split()))


import numpy as np

t= min(k, 45)


for k in range(t):
    bn = np.zeros(n, dtype=int)
    for i in range(n):
        bn[max(i - an[i], 0)] += 1

        if i+ an[i]+1 <n:
            bn[i+an[i]+1] -=1

    an = np.cumsum(bn)


print(*an)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
for i in range(k):
  C = [0]*(n+1)
  for j in range(n):
    p = max(0, j-A[j])
    q = min(n-1, j+A[j])
    C[p] += 1
    C[q+1] -= 1
  for j in range(n):
    C[j+1]=C[j+1]+C[j]
  if all([v==n for v in C[:-1]]):
    break
  A = C
C = [str(c) for c in C[:-1]]
print(' '.join(C))

Submission status: Time Limit Exceeded

Solution code:
# imos法
# 長さNの1次元配列において、「ある連続する区間に、ある数vを足す」という操作をK回繰り返した結果を高速で求める
# B リスト⇒辞書（その代わり累積和が遅くなる）

# 初期入力

import sys
input = sys.stdin.readline
N,K = (int(i) for i in input().split())
A = list(map(int, input().split()))


l =0
r =N
cumulative_sum =[0]*N
#操作数が電球の数より多いとき
if N <=K:
    A=[N]*N
# imos法
else:
    for j in range(K):
        B ={i:0 for i in range(N+1)}
        for i in range(N):
            index =A[i]
            if i-index <0:
                l=0
            else:
                l =i -index
            if i +index +1 >=N:
                r =N 
            else:
                r =i +index +1
            B[l] +=1 
            B[r] -=1
        #累積和(imos法) 
        cum_sum =[0]*N
        cum_sum[0] =B[0]
        for i in range(N-1):
            cum_sum[i+1] =cum_sum[i] +B[i+1]
        A =cum_sum
        if sum(A) ==N*N:
            print(*A)
            sys.exit(0)
            ##
    
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()))

def imos(A):
    B=np.zeros_like(A)
    for i,x in enumerate(A):
        a=max(0,i-x)
        b=min(i+x,N-1)
        B[a]+=1
        if b+1<=N-1:
            B[b+1]-=1
    B=np.cumsum(B)
    return B

for i in range(K):
    if i>=50:
        break
    A=imos(A)
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):
  b = [0]*(n+1)
  for i in range(n):
    l = max(0,i-a[i])
    r = min(n-1,i+a[i])
    b[l]+=1
    b[r+1]-=1
  changed = False
  for i in range(n):
    if b[i]!=a[i]:
      changed = True
    a[i] = b[i]
    b[i+1] += b[i]
  if not changed:
    break
for i in range(n):
  print(a[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):
  b = [0]*(n+1)
  for i in range(n):
    l = max(0,i-a[i])
    r = min(n-1,i+a[i])
    b[l]+=1
    b[r+1]-=1
  changed = False
  for i in range(n):
    if b[i]!=a[i]:
      changed = True
    b[i+1] += b[i]
    a[i] = b[i]
  if not changed:
    break
for i in range(n):
  print(a[i],end=' ')

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
prev = -1
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
  pre = 0
  changed = False
  for i in range(n):
    pre += b[i]
    b[i] = pre
    if b[i]!=a[i]:
      changed = True
    a[i] = b[i]
  if not changed:
    break
for i in range(n):
  print(a[i],end=' ')

Submission status: Time Limit Exceeded

Solution code:
# imos法
# 長さNの1次元配列において、「ある連続する区間に、ある数vを足す」という操作をK回繰り返した結果を高速で求める

# 初期入力

import sys
input = sys.stdin.readline
N,K = (int(i) for i in input().split())
A = list(map(int, input().split()))


l =0
r =N
cumulative_sum =[0]*N
#操作数が電球の数より多いとき
if N <=K:
    A=[N]*N
# imos法
else:
    for j in range(K):
        B =[0]*(N+1)
        for i in range(N):
            index =A[i]
            if i-index <0:
                l=0
            else:
                l =i -index
            if i +index +1 >=N:
                r =N 
            else:
                r =i +index +1
            B[l] +=1 
            B[r] -=1
        #累積和(imos法) 
        from itertools import accumulate
        del B[-1]
        A =list(accumulate(B))
        if sum(A) ==N*N:
            print(*A)
            sys.exit(0)
    
print(*A)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
prev = -1
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
  pre = 0
  changed = False
  for i in range(n):
    pre += b[i]
    b[i] = pre
    a[i] = b[i]
  if prev==-1:
    prev=b.copy()
  else:
    if prev==b:
    	break
    else:
      prev = b.copy()
for i in range(n):
  print(a[i],end=' ')

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
tu=0
td=0
if k>=40:
  a=[n]*n
else:
  for j in range(k):
    temp=[0]*n
    for i in range(n):
      td=max(i+1-a[i],1)
      temp[td-1]=temp[td-1]+1
      tu=min(i+1+a[i],n)
      if tu!=n:
        temp[tu]=temp[tu]-1
    a[0]=temp[0]
    for i in range(1,n):
      a[i]=a[i-1]+temp[i]
L=[str(t) for t in a]
L=" ".join(L)
print(L)

Submission status: Time Limit Exceeded

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

n,k=map(int,input().split())
dp2=list(map(int,input().split()))
    
k=min(k,41)
for _ in range(1,k+1):
    ims=[0]*(n+1)
    for ni, dp2i in enumerate(dp2):
        if ni<dp2i:
            ims[0]+=1
        else:
            ims[ni-dp2i]+=1
        if n>ni+dp2i:
            ims[ni+dp2i+1]-=1

    dp2[0]=ims[0]
    for ni in range(1,n):
        dp2[ni]=dp2[ni-1]+ims[ni]
    
print(' '.join(map(str,dp2)))

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
tu=0
td=0
if k>=50:
  a=[n]*n
else:
  for j in range(k):
    temp=[0]*n
    for i in range(n):
      td=max(i+1-a[i],1)
      temp[td-1]=temp[td-1]+1
      tu=min(i+1+a[i],n)
      if tu!=n:
        temp[tu]=temp[tu]-1
    a[0]=temp[0]
    for i in range(1,n):
      a[i]=a[i-1]+temp[i]
L=[str(t) for t in a]
L=" ".join(L)
print(L)

Submission status: Time Limit Exceeded

Solution code:
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
  pre = 0
  changed = False
  for i in range(n):
    pre += b[i]
    b[i] = pre
    a[i] = b[i]
    if b[i]!=n:
      changed = True
  if not changed:
    break
for i in range(n):
  print(a[i],end=' ')

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
n,k = map(int, input().split())
As = list(map(int, input().split()))
for i in range(k):
    imos = [0] * (n+1)
    for i,a in enumerate(As):
        l = max(0, i-a)
        r = min(n, i+a+1)
        imos[l] += 1
        imos[r] -= 1
    acc = list(accumulate(imos))
    # 指数関数的に増えるので、capする
    if acc[:-1] == As:
        print(*As)
        exit()
    As = acc[:-1]
print(*As)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
tu=0
td=0
for j in range(k):
  temp=[0]*n
  for i in range(n):
    td=max(i+1-a[i],1)
    temp[td-1]=temp[td-1]+1
    tu=min(i+1+a[i],n)
    if tu!=n:
      temp[tu]=temp[tu]-1
  a[0]=temp[0]
  for i in range(1,n):
    a[i]=a[i-1]+temp[i]
  if sum(a)==n**2:
    break
L=[str(t) for t in a]
L=" ".join(L)
print(L)

Submission status: Time Limit Exceeded

Solution code:
import math

N, K = map(int, input().split())
if K > int(math.log(N)):
    K = int(math.log(N))*2
# 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):
        if i - A_list[i] <= 0:
            A_New_list[0] += 1
        else:
            A_New_list[i - A_list[i]] += 1
        if i + A_list[i] + 1 < N:
            A_New_list[i + A_list[i] + 1] -= 1
    for i in range(1,N):
        A_New_list[i] += A_New_list[i-1]
    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
from numba import njit


n, k = map(int, input().split())
a = np.array(list(map(int, input().split())))
def update(a):
    b = np.zeros_like(a)
    for i, x in enumerate(a):
        l = max(0, i - x)
        r = min(n - 1, i + x)
        b[l] += 1
        if r + 1 < n:
            b[r + 1] -= 1
    b = np.cumsum(b)
    return b
k = min(k, 100)
for i in range(k):
    a = update(a)
print(' '.join(a.astype(str)))

Submission status: Time Limit Exceeded

Solution code:
# 幅優先探索（行きがけ）
import collections
import sys
import copy


def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())


def main():
    N, K = LI()
    aArray = LI()

    for i in range(K):
        bArray = [0]*(N)
        for j in range(N):
            minx = max(0, j-aArray[j])
            maxx = min(N-1, j+aArray[j])
            bArray[minx] += 1
            if maxx < N-1:
                bArray[maxx+1] -= 1
        for k in range(N-1):
            bArray[k+1] += bArray[k]
        aArray = bArray
        if sum(aArray) == N**2:
            break

    print(*aArray)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit

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

fin = np.array([N] * N, dtype=np.int64)


@njit(cache=True)
def calc_b(a):
    b = np.zeros(N, dtype=np.int64)
    for i in range(N):
        l = max(0, i - a[i])
        r = min(N - 1, i + a[i])

        b[l:r+1] += 1
    return b


for k in range(K):
    a = calc_b(a)

    if np.all(a == fin):
        break

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import accumulate

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

current_arr = A
if K > 41:
    print(*([N]*N))
else:
    for _ in range(K):
        imos = [0] * N
        ruiseki = [0] * (N+1)
        for i, ai in enumerate(current_arr):
            imos[max([0, i-ai])] += 1
            if i+ai+1 < N:
                imos[i+ai+1] -= 1
        for j, im in enumerate(imos):
            ruiseki[j+1] = ruiseki[j] + im
        current_arr = ruiseki[1:]
#print(imos)
#print(ruiseki)
#print(*accumulate(imos))
    print(*current_arr)

Submission status: Time Limit Exceeded

Solution code:
import sys
n, k = map(int, sys.stdin.readline().rstrip().split())
an = list(map(int, sys.stdin.readline().rstrip().split()))


import numpy as np

t= min(k, 45)
bn = np.zeros((t,n), dtype=int)

for k in range(t):
    if k==0:
        for i in range(n):
            for j in range(max(i - an[i], 0), min(n, i + an[i] + 1)):
                bn[k][j] += 1
    else:
        for i in range(n):
            for j in range(max(i - bn[k - 1][i], 0), min(n, i + bn[k - 1][i] + 1)):
                bn[k][j] += 1

print(*bn[t-1])