Problem:


Score : 500 points

Problem Statement

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

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

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

Find the intensity of each bulb after the K operations.

Constraints

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

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

0 \leq A_i \leq N

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 \ldots A_N

Output

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

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

Sample Input 1

5 1
1 0 0 1 0

Sample Output 1

1 2 2 1 2 

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

Sample Input 2

5 2
1 0 0 1 0

Sample Output 2

3 3 4 4 3 



Sample input:
5 1
1 0 0 1 0


Sample output:
1 2 2 1 2

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

a= np.array(a)

def light(a_list):
    outcome= np.array([0]*n)
    for i in range(n):
        outcome[max(0,i-a_list[i]):min(n,i+a_list[i]+1)] += 1
    return outcome

for _ in range(min(41,k)):
    if sum(a) >= n*n:
        break
    a = light(a)

[print(aa,end=' ') for aa in a]

Submission status: Time Limit Exceeded

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

def calc(A):
	B = [0]*N
	for i in range(N):
		a = max(0,i-int(A[i]))
		b = min(N,(i+1)+int(A[i]))
		for j in range(a,b):
			B[j] += 1
	return B

for i in range(min(K,41)):
	A = calc(A)

print(*A)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, K = [int(x) for x in input().split()]
lamp_list = np.array(list(map(int, input().split())))

for x in range(K):
    light = np.zeros(N, dtype=np.int)
    for i, lamp_power in enumerate(lamp_list):
        if lamp_power == 0:
            light[i] += 1
        else:
            lower = i - lamp_power
            if lower < 0:
                lower = 0
            higher = i + lamp_power + 1
            if higher > N:
                higher = N
            light[lower:higher] += 1
    lamp_list = light
    if np.all(light == N):
        break

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

Submission status: Time Limit Exceeded

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

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

new_a = [0 for i in range(n)]
for i in range(k):
    for j in range(n):
        new_a[max(j-a[j], 0)] += 1
        if j+a[j]+1 < n:
            new_a[j+a[j]+1] += -1
    for j in range(n):
        if j > 0:
            new_a[j] += new_a[j-1]
    if new_a == [n for i in range(n)]:
        a = copy.copy(new_a)
        break
    a = copy.copy(new_a)
    new_a = [0 for i in range(n)]

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
def main():
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    zeros=[0 for i in range(n)]

    if min(a)==n:
        print(*a)
        exit()

    for i in range(k):
        x=zeros.copy()
        for j in range(n):
            if a[j]==0:
                l=j
                r=min(j+1,n)
                #print(l,r)
                x[l]+=1
                if r!=n:
                #print(r)
                    x[r]+=-1
                #print(x)
            else:
                l=max(0,j-a[j])
                r=min(j+a[j]+1,n)
                #print(l,r)
                x[l]+=1
                if r!=n:
                    #print(r)
                    x[r]+=-1
                #print(x)
        ruiseki=[0]*n
        ruiseki[0]=x[0]
        a[0]=ruiseki[0]
        for i in range(1,n):
            ruiseki[i]=ruiseki[i-1]+x[i]
            a[i]=ruiseki[i]
 
        #print(*ruiseki)
    print(*a)
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
nums=[int(e) for e in input().split()]
numsA=[int(e) for e in input().split()]
A=[]
count=0
for k in range(nums[1]):
    for i in range(nums[0]):
        for j in range(nums[0]):
            if (j+1)-numsA[j]-0.5<=i+1<=(j+1)+numsA[j]+0.5:
                count=count+1
        A.append(count)
        count=0
    numsA=A
    A=[]

print(*numsA)

Submission status: Time Limit Exceeded

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

cnt = 0
flg = True
while flg and cnt < k:
    res = [0 for _ in range(n)]
    for i in range(n):
        if i - a[i] < 0:
            res[0] += 1
        else:
            res[i-a[i]] += 1

        if i + a[i] + 1 < n:
            res[i+a[i]+1] -= 1

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

    if all(res[i] == n for i in range(n)):
        flg = False

    cnt += 1
    a = res.copy()

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()))
A=np.array(a)
l,r=0,0
for i in range(min(41,k)):
    B=np.zeros(n+1,dtype=np.int64)
    for x,y in enumerate(list(A)):
        l=max(0,x-y)
        r=min(n,x+y+1)
        B[l]+=1
        B[r]-=1
    A=np.cumsum(B[:-1])
print(*A,sep=' ')

Submission status: Time Limit Exceeded

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

for i in range(max(K, math.log(K))):
    tmp = A[:]
    A = [0 for _ in range(N)]
    for j in range(N):
        a = tmp[j]
        for k in range(max(0, j-a), min(N, j+a+1)):
            A[k] += 1
print(*A)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, K = map(int, input().split())
    a = list(map(int, input().split()))
    cnt = a.count(n)
    for k in range(min(K, 100)):
        an = [0] * n
        for i in range(n):
            if an[i] < n:
                an[i] += 1
            for j in range(1, a[i]+1):
                if i - j >= 0 and an[i-j] < n:
                    an[i-j] += 1
                    if an[i-j] == n:
                        cnt += 1
                if i + j < n and an[i+j] < n:
                    an[i+j] += 1
                    if an[i+j] == n:
                        cnt += 1
        else:
            a = an
            if cnt == n:
                break
    print(*a)
main()

Submission status: Time Limit Exceeded

Solution code:
N,K = [int(v) for v in input().split()]
A = [int(v) for v in input().split()]

N_count = A.count(N)
N_flag = [False for _ in range(N)]

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


for count in range(min(41,K)):
    for i in range(N+1): next_A[i] = 0

    for x,a in enumerate(A):
        if a == 0:
            next_A[x] += 1
            next_A[x+1] -= 1
        else:
            next_A[max(x-a,0)] += 1
            next_A[min(x+a+1,N)] -= 1

    for i in range(N):
        next_A[i+1] += next_A[i]

    A = next_A[:N]
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()))

a= np.array(a)

def light(a_list):
    outcome= np.array([0]*n)
    for i in range(n):
        outcome[max(0,i-a_list[i]):min(n,i+a_list[i]+1)] += 1
    return outcome

for _ in range(k):
    if sum(a) >= n*n:
        break
    a = light(a)

[print(aa,end=' ') for aa in a]

Submission status: Time Limit Exceeded

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

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

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

B = [0] * N

for i in range(K):
    for j in range(N):
        d0 = j - A[j]
        if d0 < 0: d0 = 0
        d1 = j + A[j]
        if d1 >= N: d1 = N - 1

        for k in range(d0, d1 + 1):
            B[k] += 1  

    A = B[:]
    B = [0] * N

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

Submission status: Time Limit Exceeded

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

n, k = map(int, input().split())
A = tuple(map(int, input().split()))
for _ in range(k):
  C = [0]*n
  for i, a in enumerate(A):
    C[max(0, i-a)] += 1
    if i+a < n-1:
      C[i+a+1] -= 1
  A = tuple(accumulate(C))
  if min(A) == n:
    break
print(*A)

Submission status: Time Limit Exceeded

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

count = [0] * N

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

    if count == [N] * N:
        break
    A = count

print(*count)

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict

n,k=map(int,input().split())
l=list(map(int,input().split()))
x=1
for i in range(min(42,k)):

	
	d=defaultdict(lambda:1)
	for j in range(n):
		
		for k in range(1,l[j]+1):
			if(j+k==n):
				break
			
			d[j+k]+=1
		for k in range(1,l[j]+1):
			if(j-k==-1):
				break
			d[j-k]+=1
		
	
	for j in range(n):
		l[j]=d[j]
for i in l:
	print(i,end=" ")

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
life = [[0]*N]*N
#life = [[i==j for i in range(N)] for j in range(N)]
a = list(map(int,input().split()))
for k in range(min(K,50)):
  life = [[-1*a[j]<=j-i and j-i<=a[j] for j in range(N)]for i in range(N)]
  #print(life)
  a = [sum(life[i]) for i in range(N)]
  #print(life[:][1])
  #print(a)
b=[str(i) for i in a]
b=" ".join(b)
print(b)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n,k,*a=map(int,open(0).read().split())
r=range(n)
while(min(a)<n)*k:
 k-=1;b=[0]*n*3
 for i in r:t=a[i];b[max(0,i-t)]+=1;b[i-~t]-=1
 for i in r:b[i+1]+=b[i]
 a=b[:n]
print(*a)

Submission status: Time Limit Exceeded

Solution code:

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import factorial
from collections import Counter
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
import numpy as np
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
MOD = 10**9 + 7

n, k = MAP()
a = LIST()

def update(a):
    b = [0]*n
    for i in range(n):
        for j in range(max(i-int(a[i]), 0), min(n, i+int(a[i])+1)):
            b[j] += 1
    return b
end = [n]*n

for i in range(k):
    if a == end:
        break
    a = update(a)
for i in range(n):
    print(str(int(a[i]))+" ",end = "" )

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

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

for _ in range(K):
    if A == [N] * N:
        break
    B = [0] * (N+1)
    for i, a in enumerate(A):
        start = max(0, i - a)
        end = min(N-1, i + a) + 1
        B[start] += 1
        B[end] -= 1
        A = list(accumulate(B))[:-1]
print(' '.join(map(str, A)))

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
A = [[0]*n for _ in range(k+1)]
temp = list(map(int, input().split()))
for i in range(n):
    A[0][i] = temp[i]
for i in range(1,k+1):
    for j in range(n):
        head = max(0, j-A[i-1][j])
        tail = min(n-1, j+A[i-1][j])
        for l in range(head, tail+1, 1):
            A[i][l] += 1
    for m in range(n):
        if A[i][m] != n:
            break
    else:
        for a in A[i]:
            print(a, end=' ')
            print()
for a in A[-1]:
    print(a, end=' ')
print()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
#sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():
    n, k = geta(int)
    a = tuple(geta(int))

    def update(b):
        r = [0] * n
        for i, bi in enumerate(b):
            i1 = max(0, i - bi)
            i2 = min(n - 1, i + bi)
            r[i1] += 1

            if i2 < n - 1:
                r[i2 + 1] -= 1

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

        return r

    for i in range(k):
        a = update(a)

    print(*a, sep=" ")


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#! /usr/bin/env python3

import sys
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
 
n,k=map(int,input().split())
A=list(map(int,input().split()))
for i in range(min(k,50)):
    P=[]
    M=[]
    cnt=0
    for a in range(n):
        if A[a]==n:
            cnt+=1
            continue
        P.append(a-A[a])
        M.append(a+A[a]+1)
    P.sort()
    M.sort()
    P=deque(P)
    M=deque(M)
    C=[]
    m=n
    for j in range(n):
        if P:
            while P[0]<=j:
                P.popleft()
                cnt+=1
                if not P:
                    break
        if M:
            while M[0]<=j:
                M.popleft()
                cnt-=1
                if not M:
                    break
        C.append(cnt)
        m=min(cnt,m)
    A=C
    if m==n:
        break
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()))

a_list= np.array(a)

def light(a_list):
    outcome= np.array([0]*n)
    for i in range(n):
        outcome[max(0,i-a_list[i]):min(n,i+a_list[i]+1)] += 1
    return outcome

for _ in range(k):
    if sum(a) >= n*n:
        break
    a = light(a)

[print(aa,end=' ') for aa in a]

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
ans = [0]*n
x=[0]*n
for i in range(n):
    d1 = i+1-a[i]
    d2 = i+1+a[i]
    for j in range(d1, d2+1):
        if j <= 0 or j>=n+1:
            continue
        else:
            ans[j-1] += 1
for _ in range(k-1):
    for i in range(n):
        d1 = i-ans[i]
        d2 = i+ans[i]
        for j in range(d1, d2+1):
            if j < 0 or j>=n:
                continue
            else:
                x[j] += 1
    ans = x
print(' '.join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    A_temp=[0]*N
    for k in range(min(K,41)):
        for i,data in enumerate(A):
            for j in range(max(0,i-data),min(N,i+data+1)):
                A_temp[j]+=1
        A=A_temp
        A_temp=[0]*N
    print(*A)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = input().split()
i_list = list(range(len(a)))
a = [int(a[i]) for i in i_list]
c = [0]*n
d = [0]*n

for i in range(n):
    dum = [i]*n
    d[i] = list(map(lambda y,z: abs(y-z), i_list, dum))

for m in range(k):
    for i in range(n):
        b = list(map(lambda x,y: x-y, a, d[i]))
        c[i] = sum(1 for x in b if x >=0)
    a = []
    a += c
    if a == [n]*n:
        break
a = [str(aa) for aa in a]
print(' '.join(a))

Submission status: Time Limit Exceeded

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

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


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


        

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

A=[int(i) for i in input().split()]
if K > N or K>40:
    output=""
    for i in range(N):
         output+=(str(N)+" ")
    print(output)
else:
    for _ in range(K):
        A_next =[1 for i in range(N)]
        for i in range(N):
            for j in range(A[i]):
                if (i+j+1) < N:
                    A_next[i+j+1]+=1
                if (i-j-1) >= 0:
                    A_next[i-j-1]+=1
        A=A_next
    output=""
    for i in A_next:
        output+=(str(i)+" ")
    print(output)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))  # 整数のリスト

    next_A = [0 for _ in range(N)]

    for k in range(min(K, 41)):
        if sum(A) == N**2:
            break
        for i in range(N):
            for j in range(i-A[i], i+A[i]+1):
                if j >= 0 and j < N:
                    next_A[j] += 1
        A = next_A
        next_A = [0 for _ in range(N)]

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
A = np.array(lr() + [0])
# logNで終了
for _ in range(min(K, 15)):
    next = np.array([0] * (N+1))
    for i in range(N):
        x = A[i]
        next[max(0, i-x)] += 1
        next[min(N-1, i+x)+1] -= 1
    A = next.cumsum()

print(*A[:-1])

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
from copy import deepcopy

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

if k > 41:
    k = 41

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

print(*a[:-1])

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
N,K = [int(x) for x in stdin.readline().rstrip().split()]
A = [int(x) for x in stdin.readline().rstrip().split()]
if N%2 == 0:
    b = N//2
else:
    b = (N//2) +2
if N==1:
    print(1)
    exit()
if K >= 40:
    for i in range(N-1):
        print(N,end=" ")
    print(N)
    exit()
nextgen2 = [0]*N
for k in range(K):
    nextgen = nextgen2.copy()
    for i in range(N):
        # print("i=",i)
        a = A[i]
        start = i-a
        if start <0:
            start = 0
        end = i+a+1
        if end <=N-1:
            nextgen[end] += -1
        # print(start,end)
        nextgen[start] += 1
        # print(nextgen)
    dp = 0
    for i in range(N):
        dp += nextgen[i]
        A[i] = dp
s = ' '.join([str(i) for i in A])
print(s)

Submission status: Time Limit Exceeded

Solution code:
N,K = list(map(int,input().split()))
A = list(map(int,input().split()))
if K >= 40:
    ans = [N]*N
    print(*ans)
else:
    for i in range(K):
        CA = [0]*N
        for j in range(N):
            CA[max(0,j-A[j]):min(j+A[j]+1,N)] = map(lambda x: x+1,CA[max(0,j-A[j]):min(j+A[j]+1,N)])
        A = [CA[i] for i in range(N)]
    print(*A)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
*A, = map(int, input().split())
for _ in range(K):
    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
    end = True
    for i in range(1, N):
        B[i] += B[i-1]
        if B[i] != N: end = False
    A = B
    if end: break
print(*A)

Submission status: Time Limit Exceeded

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

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
A = np.array(lr() + [0])
# logNで終了
for _ in range(min(K, 21)):
    next = np.array([0] * (N+1))
    for i in range(N):
        x = A[i]
        next[max(0, i-x)] += 1
        next[min(N-1, i+x)+1] -= 1
    A = next.cumsum()

print(*A[:-1])

Submission status: Time Limit Exceeded

Solution code:
import collections

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

for x in range(k):
    b = []
    for i,j in enumerate(a):
        b.extend(range(max(i-j,0),min(i+j+1,n)))
    a = collections.Counter(b).values()
    if len(b) == n*n:
        break
    
print(" ".join([str(x) for x in 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):
    a01 = [0] * (n + 1)
    for i, ai in enumerate(a):
        l, r = max(0, i - ai), min(i + ai + 1, n)
        a01[l] += 1
        a01[r] -= 1
    a = list(accumulate(a01))
    if all(i == n for i in a):
        break
print(*a[:-1])

Submission status: Time Limit Exceeded

Solution code:
def solve():
    ans = 0
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    for j in range(K):
        check = [0]*(N+1)
        for i in range(N):
            check[max(0,i-A[i])] += 1
            check[min(N,i+A[i]+1)] -= 1
        A = [check[0]]*N
        for i in range(1,N):
            A[i] = A[i-1]+check[i]
        if A==[N]*N:
            break
    return A
print(*solve())

Submission status: Time Limit Exceeded

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

def imo(a):
    imos=[0]*(n+1)

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

    return immo[:n]

for i in range(min(k,41)):
    a=imo(a)
    
print(*a)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
readline = sys.stdin.buffer.readline
def main():
  n,k=map(int,readline().split())
  a=np.array(list(map(int,readline().split())))
  if k>41:
    k=41
  nums=np.array(range(n))
  leftdis=nums-a-0.5
  rightdis=nums+a+0.5
  for j in range(k):
    for i in range(n):
      a[i]=np.count_nonzero(np.logical_and(leftdis<i,rightdis>i))
    #leftdis[i]=a_i-i-0.5
    #rightdis[i]=a_i+i+0.5
    leftdis=nums-a-0.5
    rightdis=nums+a+0.5
  print(" ".join((str(x) for x in a)))
main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import numpy as np


def solve(N: int, K: int, A: "List[int]"):
    for n in range(41 if K>=41 else K):
        L = [0] * N
        for i in range(N):
            for j in range(A[i]+1):
                if j!=0:
                    if i-j>=0:
                        L[i-j] += 1
                    if i+j<N:
                        L[i+j] += 1
                else:
                    L[i+j] += 1
        if A==L:
            A = L
            break
        if sum(A)==N*N:
            A = L
            break
        A = L
 
    print(' '.join(map(str,A)))
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

new_a = [0 for i in range(n)]
for i in range(k):
    for j in range(n):
        new_a[max(j-a[j], 0)] += 1
        if j+a[j]+1 < n:
            new_a[j+a[j]+1] += -1
    for j in range(n):
        if j > 0:
            new_a[j] += new_a[j-1]
    if new_a == [n for i in range(n)]:
        break
    a = copy.copy(new_a)
    new_a = [0 for i in range(n)]

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

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

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

note = [[0 for _ in range(N)] for _ in range(K+1)]
note[0] = l

for i in range(K):
    cnt = 0
    for j in range(N):
        for k in range(max(0,j-note[i][j]),min(N-1,j+note[i][j])+1):
            note[i+1][k] += 1
            if note[i+1][k] == N:
                cnt += 1
    if cnt == N:
        print(*note[i])
        exit()
print(*note[-1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[3]:


import numpy as np


# In[57]:


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


# In[61]:


light = A
for k in range(K):
    mylist = []
    for n in range(N):
        tmp = [0]*N
        tmp[max(0,n-light[n]):min(N, n+light[n])+1] = [1]*((min(N-1, n+light[n])+1-max(0,n-light[n])))
        mylist.append(tmp)
    light = np.sum(np.array(mylist), axis=0)
    if light.tolist() == [N]*N:
        break
print(*light)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
B=[0]*N

sousa=0
kaisuu=min(K,42)

while sousa<kaisuu:
    for i in range(N):
        ma=i+A[i]+1
        if ma>N:
            ma=N
        mi=i-A[i]
        if mi<0:
            mi=0
        for j in range(mi,ma):
            B[j]+=1
    A=list(B)
    B=[0]*N
    sousa+=1

A=[str(k) for k in A]
print(" ".join(A))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

def main():
    import sys
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    A_temp=[0]*N
    for k in range(min(K,41)):
        for i,data in enumerate(A):
            for j in range(max(0,i-data),min(N,i+data+1)):
                A_temp[j]+=1
        A=A_temp
        A_temp=[0]*N
    print(*A)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
 
N, K = map(int, input().split())
An = list(map(int, input().split()))
th = [N for i in range(N)]
 
#Sn = np.array([[0 for i in range(N)] for i in range(N)])
#for i in range(N):
#    Sn[i][max(0,i - An[i]): min(i + An[i] + 1, N)] = 1
#print(Sn)
buf = np.array(range(N))
 
for i in range(K):
    Hn = buf + An#np.array([ i + An[i] for i in range(N)])
    Ln = buf - An#np.array([ i - An[i] for i in range(N)])
    #print(Hn)
    #print(Ln)
    An = [sum((Ln<=i)&(i<=Hn)) for i in range(N)]
    if An == th: break
    
 
print(*An)