Problem:


Score : 500 points

Problem Statement

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

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

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

Find the intensity of each bulb after the K operations.

Constraints

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

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

0 \leq A_i \leq N

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 \ldots A_N

Output

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

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

Sample Input 1

5 1
1 0 0 1 0

Sample Output 1

1 2 2 1 2 

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

Sample Input 2

5 2
1 0 0 1 0

Sample Output 2

3 3 4 4 3 



Sample input:
5 1
1 0 0 1 0


Sample output:
1 2 2 1 2

Submission status: Time Limit Exceeded

Solution code:
import copy
import sys

def main():
    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):
            l = max(0, j-A[j]) #座標iの電球が照らす範囲の左端
            r = min(n-1, j+A[j]) #座標iの電球が照らす範囲の右端
            B[l] += 1
            if (r+1 < n):
                B[r+1] -= 1 # 後ほど累積和にしたときに、照らす範囲の右端より外には影響が及ばないようにあらかじめ1引いておく

        for j in range(n-1):
            B[j+1] += B[j]

        A = copy.deepcopy(B)
        B = [0] * n

    print(*A)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
n,k = map(int,input().split())
ls = list(map(int,input().split()))
if n >=100 and k >n/5:
    for q in range(len(ls)):
        print(len(ls),end=" ")
    sys.exit()
if k >= len(ls):
    for q in range(len(ls)):
        print(len(ls),end=" ")
    sys.exit()
for _ in range(k):
    new = [0]*n
    for i in range(n):
        p = 0
        for l in range(1,max(n-i,i+1)):
            if i+l >= 0 and i+l <n:
                if ls[i+l] >= l:
                    p += 1
            if i-l >= 0 and i-l <n:
                if ls[i-l] >= l:
                    p += 1
        new[i] = p+1
    ls = new
print(*ls)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

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

current_arr = A
for k 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
    if current_arr == ruiseki[1:]:
        break
    current_arr = ruiseki[1:]
#print(imos)
#print(ruiseki)
#print(*accumulate(imos))
print(*current_arr)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

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

current_arr = A
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 math
import numpy as np

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


for _ in range(k):
    new_a = []
    c = 0
    a_in = [max(i-j,0) for i,j in enumerate(a)]
    a_out = [min(i+j,n) for i,j in enumerate(a)]
    for x in range(n):
        c += a_in.count(x)
        c -= a_out.count(x-1)
        new_a.append(c)
    a = new_a
    if np.all(a==n):
        break

print(" ".join([str(x) for x in a]))

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
dp2=list(map(int,input().split()))
    
k=min(k,41)
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[0]=ims[0]
    for ni in range(1,n):
        dp2[ni]=dp2[ni-1]+ims[ni]
    
for i in range(n):
    print(dp2[i],end=" ")
print()

Submission status: Time Limit Exceeded

Solution code:
def draft(A, K, N):
    for _ in range(1, K+1):# 2 * 10**5
        tmp = [0]*(N+1)
        for i in range(N):# 2 * 10**5
            L = max(0, i - A[i])
            R = min(N, i + A[i]+1)
            tmp[L] += 1
            tmp[R] -= 1
        f = True
        for i in range(N):
            tmp[i+1] += tmp[i]
            A[i] = tmp[i]
            if A[i] != N:
                f = False
        if f:
            break
    for i in range(N):
        print(A[i], end=" ")

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

for k in range(K):
    if all(A) == N:
        break
    B = [0] * N
    for n in range(N):
        L = max(0, n-A[n])
        R = min(N-1 , n + A[n])
        B[L] += 1
        if R+1 != N:
            B[R+1] -= 1
    
    ruiseki = [0] * N
    ruiseki[0] = B[0]
    for i in range(1,N):
        ruiseki[i] = ruiseki[i-1] + B[i]
        
    A = ruiseki[:]
print(*ruiseki,sep=" ")

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np

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


for _ in range(min(k,500)):
    new_a = []
    c = 0
    a_in = [max(i-j,0) for i,j in enumerate(a)]
    a_out = [min(i+j,n) for i,j in enumerate(a)]
    for x in range(n):
        c += a_in.count(x)
        c -= a_out.count(x-1)
        new_a.append(c)
    a = new_a

print(" ".join([str(x) for x in a]))

Submission status: Time Limit Exceeded

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

for _ in range(k):
    r = [0]*(n+1)
    for i in range(n):
        r[max(i-a[i],0)] += 1
        r[min(i+a[i]+1,n)] -= 1
    for i in range(n-1):
        r[i+1] += r[i]
    a = r
    if a.count(n)==n:
        break
print(*a[:-1])

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import deque
from collections import defaultdict
import itertools as it

#自作関数群
def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):#階乗
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):#コンビネーション
	if n<r:
		return 0
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)
def combmod(n,r,mod):
	return (fact(n)/fact(n-r)*pow(fact(r),mod-2,mod))%mod
def printQueue(q):
	r=copyQueue(q)
	ans=[0]*r.qsize()
	for i in range(r.qsize()-1,-1,-1):
		ans[i] = r.get()
	print(ans)
class UnionFind():
	def __init__(self, n):
		self.n = n
		self.parents = [-1]*n

	def find(self, x): # root
		if self.parents[x]<0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self,x,y):
		x = self.find(x)
		y = self.find(y)

		if x==y:
			return

		if self.parents[x]>self.parents[y]:
			x,y = y,x

		self.parents[x]+=self.parents[y]
		self.parents[y]=x

	def size(self,x):
		return -1*self.parents[self.find(x)]

	def same(self,x,y):
		return self.find(x)==self.find(y)

	def members(self,x): # much time
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i)==root]

	def roots(self):
		return [i for i,x in enumerate(self.parents) if x<0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		return {r: self.members(r) for r in self.roots()} # 1~n
def bitArr(n):#ビット全探索
	x = 1
	zero = "0"*n
	ans = []
	ans.append([0]*n)
	for i in range(2**n-1):
		ans.append(list(map(lambda x:int(x),list((zero+bin(x)[2:])[-1*n:]))))
		x+=1
	return ans;
def arrsSum(a1,a2):
	for i in range(len(a1)):
		a1[i]+=a2[i]
	return a1
def maxValue(a,b,v):
	v2 = v
	for i in range(v2,-1,-1):
		for j in range(v2//a+1): #j:aの個数
			k = i-a*j
			if k%b==0:
				return i
	return -1
def copyQueue(q):
	nq = queue.Queue()
	n = q.qsize()
	for i in range(n):
		x = q.get()
		q.put(x)
		nq.put(x)
	return nq
def get_sieve_of_eratosthenes(n):
	#data = [2]
	data = [0,0,0]
	for i in range(3,n+1,2):
		data.append(i)
		data.append(0)
	for i in range(len(data)):
		interval = data[i]
		if interval!=0:
			for j in range(i+interval,n-1,interval):
				data[j] = 0
	#ans = [x for x in data if x!=0]
	ans = data[:]
	return ans

def solve(n,k,a):
	for j 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
		for i in range(1,n):
			b[i]+=b[i-1]
		if a==b:
			break
		a = b[:]

	for i in range(len(b)):
		print(b[i],end=" ")

def main():
	n,k = readInts()
	a = readInts()
	solve(n,k,a)

if __name__=='__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np

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

for _ in range(min(k,500)):
    new_a = np.zeros(n, dtype='int64')
    for j,l in enumerate(a):
        for i in range(-l,l+1):
            if j+i >= 0 and j+i<n:
                new_a[j+i]+=1
    a = new_a

print(" ".join([str(x) for x in a]))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N,K = map(int,input().split())
A = [int(i) for i in input().split()]
loop = min(41,K)
for _ in range(loop):
    B = [0]*N
    for n in range(N):
        l = max(0,n-A[n])
        r = min(N-1,n+A[n])
        #print(l,r)
        B[l]+=1
        if r+1<N:
            B[r+1] -= 1
    #print(B)
    for n in range(1,N):
        B[n] += B[n-1]
    A = B
print(*A)

Submission status: Time Limit Exceeded

Solution code:
#create date: 2020-06-14 10:29

import sys
stdin = sys.stdin
from itertools import accumulate

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    n, k = na()
    a = na()
    def step():
        b = [0] * n
        for i, ai in enumerate(a):
            start, stop = i - ai, i + ai + 1
            if start > 0:
                b[start] += 1
            else:
                b[0] += 1
            if stop < n:
                b[stop] -= 1
        return list(accumulate(b))

    for i in range(k):
        anext = step()
        if sum(a) == sum(anext):
            print(*a)
            quit()
        a = anext
    print(*a)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import deque
from collections import defaultdict
import itertools as it

#自作関数群
def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):#階乗
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):#コンビネーション
	if n<r:
		return 0
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)
def combmod(n,r,mod):
	return (fact(n)/fact(n-r)*pow(fact(r),mod-2,mod))%mod
def printQueue(q):
	r=copyQueue(q)
	ans=[0]*r.qsize()
	for i in range(r.qsize()-1,-1,-1):
		ans[i] = r.get()
	print(ans)
class UnionFind():
	def __init__(self, n):
		self.n = n
		self.parents = [-1]*n

	def find(self, x): # root
		if self.parents[x]<0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self,x,y):
		x = self.find(x)
		y = self.find(y)

		if x==y:
			return

		if self.parents[x]>self.parents[y]:
			x,y = y,x

		self.parents[x]+=self.parents[y]
		self.parents[y]=x

	def size(self,x):
		return -1*self.parents[self.find(x)]

	def same(self,x,y):
		return self.find(x)==self.find(y)

	def members(self,x): # much time
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i)==root]

	def roots(self):
		return [i for i,x in enumerate(self.parents) if x<0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		return {r: self.members(r) for r in self.roots()} # 1~n
def bitArr(n):#ビット全探索
	x = 1
	zero = "0"*n
	ans = []
	ans.append([0]*n)
	for i in range(2**n-1):
		ans.append(list(map(lambda x:int(x),list((zero+bin(x)[2:])[-1*n:]))))
		x+=1
	return ans;
def arrsSum(a1,a2):
	for i in range(len(a1)):
		a1[i]+=a2[i]
	return a1
def maxValue(a,b,v):
	v2 = v
	for i in range(v2,-1,-1):
		for j in range(v2//a+1): #j:aの個数
			k = i-a*j
			if k%b==0:
				return i
	return -1
def copyQueue(q):
	nq = queue.Queue()
	n = q.qsize()
	for i in range(n):
		x = q.get()
		q.put(x)
		nq.put(x)
	return nq
def get_sieve_of_eratosthenes(n):
	#data = [2]
	data = [0,0,0]
	for i in range(3,n+1,2):
		data.append(i)
		data.append(0)
	for i in range(len(data)):
		interval = data[i]
		if interval!=0:
			for j in range(i+interval,n-1,interval):
				data[j] = 0
	#ans = [x for x in data if x!=0]
	ans = data[:]
	return ans

n,k = readInts()
a = readInts()

for j in range(int(min(20,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
	for i in range(1,n):
		b[i]+=b[i-1]
	a = b[:]

for i in range(len(b)):
	print(b[i],end=" ")

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from time import time

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



def a_to_b(A):
    c = [0] * N
    for i, a in enumerate(A):
        lb = max(0, i - a)
        c[lb] += 1
        ub = i + a + 1
        if ub < N:
            c[ub] -= 1
    tmp = 0
    B = []
    for ci in c:
        tmp += ci
        B.append(tmp)
    return B


ans = A
for _ in range(K):
    if time() - t0 > 1.99:
        break
    ans = a_to_b(ans)

print(*ans)

Submission status: Time Limit Exceeded

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

for i in range(min(k, 50)):
    b = [0] * (n + 1)
    for j in range(n):
        l = max(0, j - a[j])
        r = min(n - 1, j + a[j])
        b[l] += 1
        b[r + 1] -= 1
    a = np.cumsum(b)[:-1]
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,int(n**0.5)+10)):
  add_a=[0]*(n+1)
  for i in range(n):
    a[i]
    add_a[max(0,i-a[i])]+=1
    add_a[min(n,i+a[i]+1)]-=1
  tmp=0
  for i in range(n):
    tmp+=add_a[i]
    a[i]=tmp
print(' '.join(map(str,a)))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from itertools import accumulate
from operator import add
n = 0

def main():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    while any(x < n for x in A) and k > 0:
        new = [0] * (n+1)
        for i, a in enumerate(A):
            l = max(0, i-a)
            r = min(n, a+i+1)
            new[l] += 1
            new[r] -= 1

        new.pop()

        A = list(accumulate(new, add))
        k -= 1

    print(*A)



main()

Submission status: Time Limit Exceeded

Solution code:
from numba import njit

@njit
def calc(A):
    B = [0] * len(A)
    for i in range(len(A)):
        B[max(0,i - A[i])] += 1
        if i + A[i] + 1 < len(A):
            B[i + A[i] + 1] -= 1
    for i in range(1,len(B)):
        B[i] = B[i - 1] + B[i]
    return B
  
import sys
readline=sys.stdin.readline
  
N,K = map(int,readline().split())
A = list(map(int,readline().split()))

for i in range(K):
  A = calc(A)
  if len(set(A)) == 1 and A[0] == N:
    break
print(*A)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    N, K = NMI()
    A = NLI()

    for k in range(min(K, 42)):
        tmp = [0] * (N+1)
        for i, a in enumerate(A):
            tmp[max(0, i-a)] += 1
            tmp[min(N, i+a+1)] -= 1
        cum = [0] * (N+1)
        for i, t in enumerate(tmp):
            if i == 0:
                cum[0] = t
                continue
            cum[i] = cum[i-1] + t
        A = cum[:-1]
    print(" ".join(map(str, A)))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
x=input()
x0=x.split()
n=int(x0[0])
k=int(x0[1])
a0=input()
a0=a0.split()
a=[int(s) for s in a0]
a2=list(range(n))
for f in range(k):
    a1=[0]*(n+1)
    for x in range(n):
        y=max(0,x-a[x])
        a1[y]=a1[y]+1    
        z=min(n-1,x+a[x])
        a1[z+1]=a1[z+1]-1
    a2[0]=a1[0]
    for x in range(1,n):    
        a2[x]=a2[x-1]+a1[x]
    if a2==a:
        break
    else:
        a=a2[:]
for i in range(n):
    print(a[i])

Submission status: Time Limit Exceeded

Solution code:
x=input()
x0=x.split()
n=int(x0[0])
k=int(x0[1])
a0=input()
a0=a0.split()
a=[int(s) for s in a0]
for f in range(k):
    a1=[0]*(n+1)
    for x in range(n):
        y=max(0,x-a[x])
        a1[y]=a1[y]+1    
        z=min(n-1,x+a[x])
        a1[z+1]=a1[z+1]-1
    a[0]=a1[0]
    for x in range(1,n):    
        a[x]=a[x-1]+a1[x]
    if a==[n]*n:
        break
for i in range(n):
    print(a[i])

Submission status: Time Limit Exceeded

Solution code:
x=input()
x0=x.split()
n=int(x0[0])
k=int(x0[1])
a0=input()
a0=a0.split()
a=[int(s) for s in a0]
a2=[0]*(n+1)
for f in range(k):
    a1=a2[:]
    for x in range(n):
        y=max(0,x-a[x])
        a1[y]=a1[y]+1    
        z=min(n-1,x+a[x])
        a1[z+1]=a1[z+1]-1
    a[0]=a1[0]
    for x in range(1,n):    
        a[x]=a[x-1]+a1[x]
    if sum(a)==n**2:
        break
for i in range(n):
    print(a[i])

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np

def cal_B(a_list):
    b_list = np.zeros(N, dtype=int)
    for i in range(N):
        temp = np.zeros(N, dtype=int)
        min_x = max(i - a_list[i], 0)
        max_x = min(i + a_list[i], N-1)
        
        temp[min_x : max_x+1] = 1
        b_list += temp
    return b_list

if __name__ == "__main__":
    N, K = map(int, input().split())
    A_list = np.array(list(map(int, input().split())))
    B_list = cal_B(A_list)

    for _ in range(K-1):
        B_list = cal_B(B_list)
        if np.all(B_list == N):
            break

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

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
if N <=K:
    B=np.full(N,N)
elif np.any(A >=N//2+1) and  N//5*4 <=K:
    B=np.full(N,N)
else:
    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:
x=input()
x0=x.split()
n=int(x0[0])
k=int(x0[1])
a0=input()
a0=a0.split()
a=[int(s) for s in a0]
for f in range(k):
    a1=[0]*(n+1)
    for x in range(n):
        y=max(0,x-a[x])
        a1[y]=a1[y]+1    
        z=min(n-1,x+a[x])
        a1[z+1]=a1[z+1]-1
    a[0]=a1[0]
    for x in range(1,n):    
        a[x]=a[x-1]+a1[x]
    if sum(a)==n**2:
        break
for i in range(n):
    print(a[i])

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

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

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
x=input()
x0=x.split()
n=int(x0[0])
k=int(x0[1])
a0=input()
a0=a0.split()
a=[int(s) for s in a0]
a2=list(range(n+1))
a2=[0 for s in a2]
for f in range(k):
    a1=a2[:]
    for x in range(n):
        y=max(0,x-a[x])
        a1[y]=a1[y]+1    
        z=min(n-1,x+a[x])
        a1[z+1]=a1[z+1]-1
    a[0]=a1[0]
    for x in range(1,n):    
        a[x]=a[x-1]+a1[x]
    if sum(a)==n**2:
        break
for i in range(n):
    print(a[i])

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

    for _ in range(K):
        B = [0]*(N+1)
        for i, a in enumerate(A):
            bottom = max(0, i-a)
            top = min(N, i+a+1)
            # B[bottom:top] = list(map(lambda x: x+1, B[bottom:top]))
            B[bottom] += 1
            B[top] -= 1
        for j in range(1, N):
            B[j] += B[j-1]

        if A == B[:-1]:
            A = B[:-1]
            break
        A = B[:-1]

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

for i in range(min(k, 50)):
    b = [0] * n
    b = np.array(b)
    for j in range(n):
        mi = max(0, j-a[j])
        ma = min(n-1, j+a[j])
        b[mi] += 1
        if ma + 1 <= n -1:
            b[ma+1] -= 1
    c = [0] * n
    s = 0
    for k in range(n):
        s += b[k]
        c[k] = s
    a = c

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

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

    for _ in range(K):
        B = [0]*N
        for i, a in enumerate(A):
            bottom = max(0, i-a)
            top = min(N, i+a+1)
            # B[bottom:top] = list(map(lambda x: x+1, B[bottom:top]))
            B[bottom] += 1
            if top < N:
                B[top] -= 1
        for j in range(1, N):
            B[j] += B[j-1]

        if A == B:
            A = B[:]
            break
        A = B[:]

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
x=input()
x0=x.split()
n=int(x0[0])
k=int(x0[1])
a0=input()
a0=a0.split()
a=[int(s) for s in a0]
a1=list(range(n+1))
for f in range(k):
    a1=[0 for s in a1]
    for x in range(n):
        y=max(0,x-a[x])
        a1[y]=a1[y]+1    
        z=min(n-1,x+a[x])
        a1[z+1]=a1[z+1]-1
    a[0]=a1[0]
    for x in range(1,n):    
        a[x]=a[x-1]+a1[x]
    if sum(a)==n**2:
        break
for i in range(n):
    print(a[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))

def solve(n,a):
    table = [0]*(n+1)
    for i,x in enumerate(a):
        table[max(0,i-x)] += 1
        table[min(n-1,i+x)+1] -=1
    return list(itertools.accumulate(table))[:-1]

def main():
    n,k = map(int,sys.stdin.readline().rstrip().split())
    a = LI()
    for _ in range(k):
        a = solve(n,a)
    for rep in a:
        print(rep,end=' ')

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
x=input()
x0=x.split()
n=int(x0[0])
k=int(x0[1])
if k>100:
    k=100
a0=input()
a0=a0.split()
a=[int(s) for s in a0]
a1=list(range(n+1))
for f in range(k):
    a1=[0 for s in a1]
    for x in range(n):
        y=max(0,x-a[x])
        a1[y]=a1[y]+1    
        z=min(n-1,x+a[x])
        a1[z+1]=a1[z+1]-1
    a[0]=a1[0]
    for x in range(1,n):    
        a[x]=a[x-1]+a1[x]
a=[str(s) for s in a]
a=" ".join(a)
print(a)

Submission status: Time Limit Exceeded

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

N,K = map(int,readline().split())
A = list(map(int,readline().split()))
def calc(A):
    B = [0] * len(A)
    for i in range(len(A)):
        B[max(0,i - A[i])] += 1
        if i + A[i] + 1 < len(A):
            B[i + A[i] + 1] -= 1
    for i in range(1,len(B)):
        B[i] = B[i - 1] + B[i]
    return B

for i in range(K):
  A = calc(A)
  if len(set(A)) == 1 and A[0] == N:
    print(*A)
    break
else:
  print(*A)

Submission status: Time Limit Exceeded

Solution code:
x=input()
x0=x.split()
n=int(x0[0])
k=int(x0[1])
a0=input()
a0=a0.split()
a=[int(s) for s in a0]
a1=list(range(n+1))
for f in range(k):
    a1=[0 for s in a1]
    for x in range(n):
        y=max(0,x-a[x])
        a1[y]=a1[y]+1    
        z=min(n-1,x+a[x])
        a1[z+1]=a1[z+1]-1
    a[0]=a1[0]
    for x in range(1,n):    
        a[x]=a[x-1]+a1[x]
    if sum(a)==n**2:
        break
a=[str(s) for s in a]
a=" ".join(a)
print(a)

Submission status: Time Limit Exceeded

Solution code:
x=input()
x0=x.split()
n=int(x0[0])
k=int(x0[1])
a0=input()
a0=a0.split()
a=[int(s) for s in a0]
a1=list(range(n+1))
for f in range(k):
    a1=[0 for s in a1]
    for x in range(n):
        y=x-a[x]
        if y<0:
            y=0
        a1[y]=a1[y]+1    
        z=x+a[x]
        if z>n-1:
            z=n-1
        a1[z+1]=a1[z+1]-1
    a[0]=a1[0]
    for x in range(1,n):    
        a[x]=a[x-1]+a1[x]
    if sum(a)==n**2:
        break
a=[str(s) for s in a]
a=" ".join(a)
print(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()))

    for _ in range(K):
        B = [0]*N
        for i, a in enumerate(A):
            bottom = i - a
            top = i + a + 1
            if bottom < 0:
                bottom = 0
            if top > N:
                top = N
            B[bottom:top] = list(map(lambda x: x+1, B[bottom:top]))
        if A == B:
            A = B
            break
        A = B[:]

    ans = ' '.join(list(map(str, A)))
    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()))

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

  A = nA[:]
  if i >= k:
    break

print(*A)

Submission status: Time Limit Exceeded

Solution code:
x=input()
x0=x.split()
n=int(x0[0])
k=int(x0[1])
a0=input()
a0=a0.split()
a=[int(s) for s in a0]
for f in range(k):
    a1=list(range(n+1))
    a1=[0 for s in a1]
    for x in range(n):
        y=x-a[x]
        if y<0:
            y=0
        a1[y]=a1[y]+1    
        z=x+a[x]
        if z>n-1:
            z=n-1
        a1[z+1]=a1[z+1]-1
    for x in range(n):    
        a[x]=sum(a1[:x+1])
    if sum(a)==n**2:
        break
a=[str(s) for s in a]
a=" ".join(a)
print(a)

Submission status: Time Limit Exceeded

Solution code:
import sys 
from collections import deque
import itertools
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))

def main():
    tmp = deque(LI())
    n,k = tmp.popleft(),tmp.popleft()
    a = LI()
    for _ in range(k):
        table = [0]*(n+1)
        for j in range(n):
            table[max(0,j-a[j])] += 1
            table[min(n-1,j+a[j])+1] -=1
        a = list(itertools.accumulate(table))
    for i in range(n):
        print(str(a[i])+' ',end='')
    return

if __name__=='__main__':
    main()

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

    if min(A) >= N:
        break

print(*A)

Submission status: Time Limit Exceeded

Solution code:
import sys 
from collections import deque
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def R(x):
    r = round(x)
    if r+0.5 <= x:
        r += 1
    return r

def main():
    tmp = deque(LI())
    n,k = tmp.popleft(),tmp.popleft()
    a = LI()
    for _ in range(k):
        table = [0]*n
        for j in range(n):
            left = R(max(0,j-a[j]-0.5))
            right = int(min(n-1,j+a[j]+0.5))
            for u in range(left,right+1):
                table[u] += 1
        a = table[:]
    for i in range(n):
        print(str(a[i])+' ',end='')
    return

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)

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

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

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