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:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

##### dict の for文 #####
# for k, v in d.items():
#     print(k, v)

##### 進数の変換 #####
# bin_str = bin(i)[2:]
# oct_str = oct(i)[2:]
# hex_str = hex(i)[2:]

##### とても大きな数 と 小数の計算誤差 #####
# 「Decimal」は計算誤差を 0にできる。必要に応じて粒度を設定せよ。
# getcontext().prec = 100
#
# tmp = Decimal(i)
# A,B = map(Decimal, input().split())
# ans = A * B

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N,K = inputMap()
	A = inputList()

	T = [0 for i in range(N)]

	for j in range(K):
		T = [0 for i in range(N)]
		for i,val in enumerate(A):
			#print(T)
			tmp_min = max(0,i-val)
			T[tmp_min] += 1

			if i+val+1 > N-1:
				continue
			tmp_max = min(N-1,i+val+1)
			T[tmp_max] -= 1

		for i,val in enumerate(T):
			if i == 0:
				continue
			T[i] += T[i-1]

		A = T

	print(*A)



def segfunc(x, y):
    return 0

ide_ele = float('inf')

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# 2分検索のリバース
def bisect_left_reverse(a, x):
    if a[0] <= x:
        return 0
    if x < a[-1]:
        return len(a)
    # 二分探索
    ok = len(a) - 1
    ng = 0
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if a[mid] <= x:
            ok = mid
        else:
            ng = mid
    return ok

def bisect_right_reverse(a, x):
    if a[0] < x:
        return 0
    if x <= a[-1]:
        return len(a)
    # 二分探索
    ok = len(a) - 1
    ng = 0
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if a[mid] < x:
            ok = mid
        else:
            ng = mid
    return ok

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# 2分検索
# 存在しない場合: None 存在する場合: その値
def binary_search(list, item):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) //2
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid -1
        else:
            low = mid + 1
    return None

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# N 個のボールを K グループに分ける場合のパターン数
def sunuke(N, K, mod=10**9+7):
	if N < K or K-1 < 0:
		return 0
	else:
		return combination(N-1, K-1, mod)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# dfs のサンプル
def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	C
# CreatedDate:  2020-06-13 21:20:41 +0900
# LastModified: 2020-06-13 21:53:45 +0900
#


import os
import sys
import numpy as np
#import pandas as pd


def main():
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    a.insert(0,0)
    a = np.array(a,dtype=np.int64)
#    print(a)
    for _ in range(k):
        mask = np.zeros(n+1,dtype=np.int64)
        for zhyo in range(1,n+1):
            sub = a[zhyo]
            mask[zhyo]+=1
            if sub+zhyo<=n:
                mask[zhyo+1:sub+zhyo+1]+=1
            else:
                mask[zhyo+1:n+1]+=1
            if zhyo-sub>=1:
                mask[zhyo-sub:zhyo]+=1
            else:
                mask[1:zhyo]+=1
        a=mask
    
    for i in range(1,n+1):
        print("{} ".format(a[i]),end="")
    print()


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#import sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math
from collections import deque
import itertools
import heapq
#import bisect
from fractions import Fraction
import copy
from functools import lru_cache
from collections import defaultdict
import pprint


def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]

def ret(a):
    c=[None]*(len(a)-1)
    if len(a)==1:
        return a[0]
    elif len(a)==0:
        return 0
    for i in range(1,len(a)):
        c[i-1]=abs(a[i]-a[i-1])
    return ret(c)

def soinsubunkai(n):
    a = []
    i = 1
    while i*i <= n:
        if n % i == 0 and i!=1:
            a.append(i)
            n=n//i

        if n% i !=0 or i==1:
            i += 1
    nokori=[n]
    return a + nokori

def main():
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    b=[[0 for j in range(n)] for i in range(k+1)]
    for i in range(n):
        b[0][i]=a[i]
#    print(b)
    boarder=10**2
    if k<=boarder:
        tempk=k
    else:
        tempk=boarder
    for i in range(1, tempk + 1):
        for j in range(n):
            for l in range(n):
                if b[i - 1][j] >= abs(j - l):
                    b[i][l] += 1
    for i in range(n):
        b[k][i]=b[tempk][i]

    print(*b[k])






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(min(-(-n//2)+1,k)):
  b=[0]*n
  for j in range(n):
    b[j] = sum([1 for h in range(n) if a[h]-abs(h-j)>=0])
  a=b
  if a[0]==n and a[-1]==n:
    break
print(*a)

Submission status: Time Limit Exceeded

Solution code:
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
for i in range(k):
  tmp = [0 for i in range(n)]
  for j in range(n):
    left = j-a[j] if j-a[j] >= 0 else 0
    right = j+a[j] if j+a[j] <= n-1 else n-1
    for l in range(left, right+1):
      tmp[l] += 1
  a = tmp
for i in a:
  print(i, end=' ')

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

for _ in range(K):
    counterlist = np.array([0 for _ in range(N)])
    for i in range(N):
        d = A[i]
        u = max(0,i-d)
        v = min(N-1,i+d)
        counterlist[u:v+1]+=1
    A = counterlist

print(*A)

Submission status: Time Limit Exceeded

Solution code:
[n,k] = list(map(int, input().split()))
inList = list(map(int, input().split()))
for i in range(k):
    pos = 1
    newList = []
    for k in range(n):
        newList.append(0)
    for j in inList:
        start = pos - j
        finish = pos + j
        if pos-1<j:
            start = 1
        if n-pos<j:
            finish = n
        for k in range(start - 1, finish):
            newList[k] += 1
        pos += 1
    inList = newList

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

Submission status: Time Limit Exceeded

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

for kai in range(k): 
    b = [0 for _ in range(n)]
    for i in range(n):
        for j in range(max(0, i-a[i]), min(i+a[i] + 1, n)):
            b[j] += 1
    a = b

L = [str(q) for q in b]
print(" ".join(L))

Submission status: Time Limit Exceeded

Solution code:
N,K= map(int,input().split())
A = list(map(int,input().split()))
T = [0 for _ in range(N)]
for t in range(K):
    for i in range(N):
        for j in range(i-A[i],i+A[i]+1):
            if j>=0 and j<=N-1:
                T[j] += 1
    for i in range(N):
        A[i]=T[i]
        T[i]=0
A=[str(a) for a in A]
A=' '.join(A)
print(A)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from sys import setrecursionlimit
import numpy as np

setrecursionlimit(10 ** 7)

n,k = map(int,stdin.readline().rstrip().split())
a = list(map(int,stdin.readline().rstrip().split()))
a = np.array(a,dtype=np.int64)
lamp= np.zeros(n,dtype=np.int64)

for i,j in enumerate(a):
    lamp[max(0,i-j):min(n+1,i+j+1)] += 1

if k == 1:
    print(*lamp)
    exit()

for _ in range(min(k-1,20)):
    b = np.zeros(n,dtype=np.int64)
    for i,j in enumerate(lamp):
        b[max(0,i-j):min(n+1,i+j+1)] += 1
    lamp = b.copy()

lamp[lamp>n] = n

print(*lamp)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int,input().split())
A = list(map(int,input().split()))
tmp = [0]*n
for _ in range(k):
    for i in range(n):
        for j in range(i-A[i],i+A[i]+1):
            if j >=0 and j < n:
                tmp[j] += 1
    A = list(tuple(tmp))
    tmp = [0]*n

print(" ".join(str(i) for i in 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 _ in range(K):
  B= [0 for _ in range(N)]
  C=0
  for i in A:
    for j in range(C-i,C+i+1):
        if(j>=0 and j<N):
          B[j]+=1
    C+=1
  A = copy.copy(B)
print(*B)

Submission status: Time Limit Exceeded

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

for i in range(k):
    b = a.copy()
    a = [0 for i in range(n)]
    for j in range(n):
        a[j] += 1
        for k in range(b[j]):
            if j-k-1 >= 0:
                a[j-k-1] += 1
            if j+k+1 < n:
                a[j+k+1] += 1
s = ""
for i in a:
    s = s + str(i) + " "

print(s[:-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

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

ans = a[:]

for i in range(k):
	for j in range(n):
		tmp = 1
		for k in range(n):
			if k<j and k+ans[k]>=j:
				tmp+=1
			elif k>j and k-ans[k]<=j:
				tmp+=1
		a[j] = tmp
	ans = a[:]

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

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
test = [n] * n

for i in range(k):
    tmp = [0] * n
    for j in range(n):
        for k in range(j - a[j], j + a[j] + 1):
            if k < 0 or n <= k:
                continue
            
            tmp[k] += 1
            
    a = tmp
    
    if a == test:
        print(i)
        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 i in range(min(K, 100)):
    B = [0] * N
    for j in range(N):
        cnt = 0
        for k in range(N):
            if k - A[k] - 0.5 <= j <= k + A[k] + 0.5:
                cnt += 1
        B[j] = cnt
    A = B[:]
print(*A)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys
import math
from decimal import Decimal, ROUND_DOWN


debug = False

def log(text):
    if debug:
        print(text)

def parse_input(lines_as_string = None):

    global debug
    lines = []
    if lines_as_string is None:
        debug = False
        # for line in sys.stdin:
        #     lines.append(line)
        lines.append(input())
        lines.append(input())
    else:
        debug = True
        lines = [e for e in lines_as_string.split("\n")][1:-1]

    (n, k) = [int(e) for e in lines[0].split(' ')]
    a = [int(e) for e in lines[1].split(' ')]

    return (n, k, a)


def solve(n, k, a):

    current = a.copy()
    next = [0 for i in range(n)]
    for _ in range(k):
        for i in range(n):
            strength = current[i]
            for j in range(max(i - strength, 0), min(i + strength + 1, n)):
                next[j] = next[j] + 1
        
        #current = next.copy()
        current = next
        next = [0 for i in range(n)]

    return ' '.join([str(e) for e in current])
    


def main():
    # 出力
    result = solve(*parse_input())
    if isinstance(result, list):
        for r in result:
            print("%s" % r, sep='')
    else:
        print("%s" % result, sep='')

if __name__ == '__main__':

    main()

Submission status: Time Limit Exceeded

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

for k in range(K):
    B = [0]*N
    for i in range(N):
        for j in range(N):
            if A[j] >= abs(j-i):
                B[i] = B[i]+1
    A = B

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

Submission status: Time Limit Exceeded

Solution code:
a,b=map(int,input().split())
import numpy as np
l=np.array(list(map(int,input().split())))
for i in range(min(b,int(a**0.5)+4)):
  now=np.zeros(a,dtype=np.int)
  for j in range(a):
    x=l[j]
    y=np.zeros(a,dtype=np.int)
    y[max(0,j-x):min(a,j+x+1)]=1
    now+=y
  l=now
for i in range(a):
  now[i]=min(now[i],a)
print(*now)

Submission status: Time Limit Exceeded

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

import math


for i in range(K):
  count_list = [0] * N
  #何個光ってるか
  for j in range(N):
    first = math.floor(j+1 - A_list[j] - 0.5)+1
    last = math.floor(j+1 + A_list[j] + 0.5)
    if(first<1):
      first = 1
    if(last<1):
      last = 1
    if(first>N):
      first = N
    if(last>N):
      last = N
    for k in range(first-1,last):
      count_list[k] = count_list[k]+1
  #print(count_list)
  A_list = count_list
  
A_list=[str(a) for a in A_list]
A_list=' '.join(A_list)
print(A_list)

Submission status: Time Limit Exceeded

Solution code:
#import sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math
from collections import deque
import itertools
import heapq
#import bisect
from fractions import Fraction
import copy
from functools import lru_cache
from collections import defaultdict
import pprint


def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]

def ret(a):
    c=[None]*(len(a)-1)
    if len(a)==1:
        return a[0]
    elif len(a)==0:
        return 0
    for i in range(1,len(a)):
        c[i-1]=abs(a[i]-a[i-1])
    return ret(c)

def soinsubunkai(n):
    a = []
    i = 1
    while i*i <= n:
        if n % i == 0 and i!=1:
            a.append(i)
            n=n//i

        if n% i !=0 or i==1:
            i += 1
    nokori=[n]
    return a + nokori

def main():
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    b=[[0 for j in range(n)] for i in range(k+1)]
    for i in range(n):
        b[0][i]=a[i]
#    print(b)
    boarder=10**3
    if k<=boarder:
        tempk=k
    else:
        tempk=boarder
    for i in range(1, tempk + 1):
        for j in range(n):
            for l in range(n):
                if b[i - 1][j] >= abs(j - l):
                    b[i][l] += 1
    for i in range(n):
        b[k][i]=b[tempk][i]

    print(*b[k])






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 + 2)
    for i in range(n):
        b[max(0, i - a[i])] += 1
        b[min(n + 1, i + a[i] + 1)] -= 1
    a[0] = b[0]
    cnt = 1 if a[0] == n else 0
    for i in range(1, n):
        a[i] = a[i - 1] + b[i]
        if a[i] == n:
            cnt += 1

    if cnt == n:
        break

print(*a)

Submission status: Time Limit Exceeded

Solution code:
from copy import copy
N, K = map(int, input().split())
a = list(map(int, input().split()))
for x in range(K):
    b = [0] * N
    for y in range(N):
        for z in range(-1 * a[y], a[y] + 1, 1):
            if y + z >= 0 and y + z < N:
                b[y + z] += 1

    a = copy(b)
print(" ".join(map(str, a)))

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import accumulate
def input(): return sys.stdin.readline().rstrip()

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

    for _ in range(K):
        new_A = [0] * (N)
        for i, a in enumerate(A):
            s = i - a
            if s < 0:
                s = 0
            f = i + a + 1
            new_A[s] += 1
            if f < N:
                new_A[f] -= 1
        A = list(accumulate(new_A))
    print(*A)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
import numpy as np
n, k = map(int, input().split())
a_list = np.array(list(map(int, input().split())))

for i in range(0, k):
    new_a_list = np.array([0] * n)
    for j in range(0, n):
        start = j - a_list[j]
        if start < 0:
            start = 0
        end = j + a_list[j] + 1
        if n < end:
            end = n
        new_a_list[start:end] += 1

    a_list = np.copy(new_a_list)
for a in a_list:
    print(a, end=" ")

Submission status: Time Limit Exceeded

Solution code:
n, k =map(int, input().split())
light = list(map(int, input().split()))
             
def sousa(list):
  new_list = [0]*len(list)
  for i,a in enumerate(list):
#    print('i:{},a:{}'.format(i, a))
    for j in range(i-a, i+a+1):
#      print('j:{}'.format(j))
      if j >= 0 and j <= len(list)-1:
        new_list[j] += 1
  return new_list

for _ in range(k):
  light = sousa(light)
  
ans = ' '.join([str(a) for a in light])
print(ans)

Submission status: Time Limit Exceeded

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

class BIT:
    def __init__(self, size):
        self.bit = [0] * (size + 1)
        self.size = size

    def sum(self, i):
        i += 1
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.bit[i] += x
            i += i & -i

class RangeBIT:
    def __init__(self, size):
        self.bit0 = BIT(size)
        self.bit1 = BIT(size)

    def sum(self, i):
        return self.bit0.sum(i) * i + self.bit1.sum(i)

    # end points are inclusive
    def add(self, l, r, x):
        self.bit0.add(l, x)
        self.bit0.add(r+1, -x)
        self.bit1.add(l, -x*(l-1))
        self.bit1.add(r+1, x*r)


N, K = map(int, input().split())
A = list(map(int, input().split()))
while K > 0 and not all(a == N for a in A):
    rb = RangeBIT(N)
    for i, a in enumerate(A):
        rb.add(max(0, i - a), min(N - 1, i + a), 1)
    for i in range(N):
        A[i] = rb.sum(i) - (rb.sum(i-1) if i > 0 else 0)
    K -= 1
print(*A)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
# Calculate intensity
N, K = [int(v) for v in input().split(" ")]
A_arr = np.array([int(v) for v in input().split(" ")])
step = np.arange(len(A_arr)) 
def Luminate(A_arr, i):
  isLuminated = np.abs(step - i) < A_arr
  return isLuminated

def get_Intensity(A_arr):
  return np.array([np.sum(Luminate(A_arr, i)) for i in range(len(A_arr))])

Intensity = A_arr
for i in range(K):
  Intensity = get_Intensity(Intensity+1)
  if np.sum(Intensity) == N**2:
    break
print(" ".join([str(v) for v in Intensity]))

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
f=0
limit=[n]*n
while f<k:
    b=[0]*n
    for i in range(n):
        for j in range(i-a[i],i+a[i]+1):
            if 0<=j<=n-1:
                b[j]+=1
    a=b
    f+=1
    if a==limit:
        break
print(*a)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from sys import setrecursionlimit
import numpy as np

setrecursionlimit(10 ** 7)

n,k = map(int,stdin.readline().rstrip().split())
a = list(map(int,stdin.readline().rstrip().split()))
a = np.array(a,dtype=np.int64)
lamp= np.zeros(n,dtype=np.int64)

for i,j in enumerate(a):
    lamp[max(0,i-j):min(n+1,i+j+1)] += 1
    
if k == 1:
    print(*lamp)
    exit()

for _ in range(min(k-1,100)):
    b = np.zeros(n,dtype=np.int64)
    for i,j in enumerate(lamp):
        b[max(0,i-j):min(n+1,i+j+1)] += 1
    lamp = b.copy()

lamp[lamp>n] = n

print(*lamp)

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 + 2)
    for i in range(n):
        b[max(0, i - a[i])] += 1
        b[min(n + 1, i + a[i] + 1)] -= 1
    a[0] = b[0]
    cnt = 0
    for i in range(1, n):
        a[i] = a[i - 1] + b[i]
        if a[i] == n:
            cnt += 1

    if cnt == n:
        break

print(*a)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

dp = np.zeros(shape=N + 1, dtype=np.int64)

if 2 * K > N:
    A = [N for _ in range(N)]
else:
    for k in range(K):
        for i in range(N):
            dp[max(0, i - A[i])] += 1
            dp[min(N, i + A[i] + 1)] -= 1
        A = dp.cumsum()[:-1]
        if np.all(A >= N):
            break
        dp *= 0

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