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 sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率

def input(): return sys.stdin.readline()[:-1]
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]

class BIT():#添字は1から始まることに注意
    def __init__(self, max_n):
        self.size = max_n + 1
        self.tree = [0] * self.size
        self.depth = self.size.bit_length()
        
    def initialize(self,seq):
        tree = self.tree
        size = self.size
        for i,x in enumerate(seq,1):
            tree[i] += x
            j = i+(i&(-i))
            if j < size:
                tree[j] += tree[i]
        
    def __repr__(self):
        return self.tree.__repr__()
        
    def get_sum(self,i):
        tree = self.tree
        s = 0
        while i:
            s += tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        tree = self.tree
        size = self.size
        while i < size:
            tree[i] += x
            i += i & -i
    
    def find_kth_element(self,k):#k番目（最小は１）の要素
        tree = self.tree; size = self.size
        x,sx = 0,0
        dx = 1 << (self.depth)
        for i in range(self.depth - 1, -1, -1):
            dx = (1 << i)
            if x + dx >= size:
                continue
            y = x + dx
            sy = sx + tree[y]
            if sy < k:
                x,sx = y,sy
        return x + 1
 
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, K = map(int, input().split())
    A = list(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    bit=BIT(N+2)
    for i,a in enumerate(A):
        i+=1
        left=max(i-a,0)
        right=min(i+a+1,N+1)
        bit.add(left+1,1)
        bit.add(right+1,-1)
    
    for k in range(K):
        update=[0]*N
        nA=copy(A)
        for i in range(N):
            a=A[i]
            na=bit.get_sum(i+2)
            if a!=na:
                nA[i]=na
                update[i]=1


        #print(A)
        if sum(update)==0:
            break

        for i, a in enumerate(A):
            if update[i]==0:
                continue
            na=nA[i]
            i+=1
            
            
            left=max(i-a,0)
            right=min(i+a+1,N+1)
            bit.add(left+1,-1)
            bit.add(right+1,+1)

            left=max(i-na,0)
            right=min(i+na+1,N+1)
            bit.add(left+1,1)
            bit.add(right+1,-1)

        A=nA
    
    print(*nA)

        





if __name__ == "__main__":
    main()

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):
  nextA = [0]*N
  for i in range(1,N+1):
    count = 0
    for x in range(1,N+1):
      kyori = max(i-x, x-i)
      akarusa = A[x-1]
      if akarusa >= kyori:
        count+=1
    nextA[i-1] = count
  A=nextA
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()))

for _ in range(K):
    num=[0]*N
    if A.count(N)==N:
        break
    for i in range(N):
        num[i]+=1
        if A[i]==0:
            continue
        for j in range(max(0,i-A[i]),min(N,i+A[i]+1)):
            if j==i:
                continue
            num[j]+=1
    A=num

print(*A)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int, input().split())
a = list(map(int, input().split()))
check = []
for i in range(n):
    if a[i]:
        check.append([i,0,a[i]])
#print(check)
for i in range(k):
    if i!=0:
        a_next = a[:]
    else:
        a_next = [1 for _ in range(n)]
    change = set()
    for i,pre,now in check:
        for to in range(i+pre+1,i+now+1):
            if to >= n:break
            change.add(to)
            a_next[to] += 1
        for to in range(i-pre-1,i-now-1,-1):
            if to < 0:break
            change.add(to)
            a_next[to] += 1
        #print(a_next)
    check = []
    for to in change:
        check.append([to,a[to],a_next[to]])
    a = a_next

print(*a)

Submission status: Time Limit Exceeded

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

while(True):
    p = 0
    T = [0]*N
    for i in range(N):
        for j in range(max(i-A[i], 0), min(i+A[i]+1, N)):
            T[j] += 1
    c += 1
    if c == K:
        for i in range(N):
            print(T[i], end=" ")
        sys.exit()
    for i in range(N):
        if T[i] <= N:
            p = 1
            break
    if p == 0:
        for i in range(N):
            print(N, end= " ")
        sys.exit()
    A = T[:]

Submission status: Time Limit Exceeded

Solution code:
#c
n,k=map(int, input().split())
a = list(map(int, input().split()))
import numpy as np
a_n = np.array(a)
for i in range(k):
    result = np.array([0]*n, dtype=object)
    for j in range(n):
        count = 0
        
        if a_n[j] == n:
            result[j] =n
            continue
        for l in range(n):
            if l > j:
                if l-a_n[l]-0.5<j:
                    count += 1
            elif l < j:
                if l+a_n[l]+0.5>j:
                    count += 1
            else:
                count += 1
        result[j] =count
    a_n = result
ans=[str(a) for a in a_n]
ans=" ".join(ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    # 区間更新・一点取得の加法BIT
    class BIT():
        def __init__(self, n):
            self.n = n
            self.maxbit = 2**(len(bin(n))-3)
            self.bit = [0]*(n+1)

        # 初期化する
        def make_bit(self, a):
            n, bit = self.n, self.bit
            for i, j in enumerate(a):
                x, y = i+1, i+2
                while x < n+1:
                    bit[x] += j
                    x += x & (-x)
                while y < n+1:
                    bit[y] -= j
                    y += y & (-y)

        # 区間[i:j]に値vを足す
        def add(self, i, j, v):
            x, y, n, bit = i+1, j+1, self.n, self.bit
            while x < n+1:
                bit[x] += v
                x += x & (-x)
            while y < n+1:
                bit[y] -= v
                y += y & (-y)

        # 位置iの値を出力する
        def output(self, i):
            ret, x, bit = 0, i+1, self.bit
            while x > 0:
                ret += bit[x]
                x -= x & (-x)
            return ret

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

    for cnt in range(min(k, 50)):
        ans = []
        bit = BIT(n)
        for i in range(n-1, -1, -1):
            bit.add(max(i-a[i], 0), min(i+a[i]+1, n), 1)
        for i in range(n):
            ans.append(bit.output(i))
        a = ans

    print(*ans)


main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


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


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


for _ in range(K):
    for i in range(N):
        c = coordinate[i]
        B[i] = (A >= np.abs(coordinate - c)).sum()
    A = B.copy()

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

Submission status: Time Limit Exceeded

Solution code:
import copy

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

#作業用の配列
b = [0] * n

#k回操作を繰り返す
for i in range(k):
  
  #N個の電球に対し順に操作する
  for j in range(n):
    
    #明るさの初期化
    d = 0
    
    #座標jを照らしている電球の個数を求める
    for l in range(n):
      
      if l - a[l] - 0.5 <= j and j <= l + a[l] + 0.5:
        d += 1
 
    #電球の明るさを更新
    b[j] = d

  a = copy.deepcopy(b)
    
print(' '.join(list(map(str, a))))

Submission status: Time Limit Exceeded

Solution code:
# ナイーブな解法。厳しいデータだとO(K*N), 2^2 x 10^10 でTLEになるはず

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

ptr = 0
buf = [[a for a in an], [0] * len(an)]
#print(an)
for i in range(k):
    ib = buf[ptr]
    buf[ptr ^ 1] = [0] * len(an)
    ob = buf[ptr ^ 1]
    
    for j in range(n):
        s = ib[j]

        lb = max(j - s, 0)
        ub = min(j + s, len(an) - 1)
        for k_ in range(lb, ub + 1):
            ob[k_] += 1
    #print('k =', i + 1)
    #print(ob)
    ptr ^= 1

print(' '.join(map(str, buf[ptr])))

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
Al = list(map(int, input().split()))
A = {i:Al[i] for i in range(N)}
for _ in range(K):
    B = {i:1 for i in range(N)}
    for i in range(N):
        for j in range(1, A[i]+1):
            if i-j >= 0:
                B[i-j] += 1
            if i+j < N:
                B[i+j] += 1
    A = B

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

Submission status: Time Limit Exceeded

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


def solve(N: int, K: int, A: "List[int]"):
    for _ in range(K):
        B = [0] * N
        for i in range(N):
            d = A[i]
            if d == 0:
                B[i] += 1
                continue

            for j in range(max(0, i-d), min(i+d+1, N)):
                B[j] += 1

        A = B.copy()

    print(*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:
n, k = map(int, input().split())
brightness = list(map(int, input().split()))

for _ in range(k):
  zeros = [0 for _ in range(n)]
  for i, b in enumerate(brightness):
    left = max(0, i-b)
    right = min(n-1, i+b)
    for j in range(left, right+1):
      zeros[j] += 1
  brightness = zeros

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
from sys import stdin,setrecursionlimit
import heapq,bisect,math,itertools,string,queue,datetime,copy
setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, stdin.readline().split()))

N,K = inpl()
Als = inpl()

up = [0]+ Als
for _ in range(K):
    uup = [0]*(N+1)
    for i,strong in enumerate(up):
        if i != 0:
            a = max(0,i-strong)
            b = min(N+1,i+strong+1)
            for kk in range(a,b):
                uup[kk] += 1
    up = uup
res = ' '.join(map(str,up[1:]))
print(res)

Submission status: Time Limit Exceeded

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

for _ in range(K):
  for i,a in enumerate(A):
    if i==0: continue
    for j in range(max(math.ceil(i-a-0.5),0), min(math.floor(i+a+0.5),N)+1):
      B[j] += 1

  A = B[::]
  B = [0] * (N+1)

print(" ".join(map(str, A[1:])))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math

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

if K > math.sqrt(N):
    A = [N] * N
    print(*A)
    exit()

for i in range(K):
    tmp_A = np.array([0] * N)
    for j in range(N):
        tmp_A[max(0,j-A[j]):min(j+A[j], N-1)+1] += 1
    A = tmp_A

print(*A)

Submission status: Time Limit Exceeded

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

while K > 0 :
    for i in range (N) :
        c = A[i]
        while c >= 0 :
            if i + c < N and c != 0 :
                B[i+c] += 1
            if i - c >= 0 and c != 0 :
                B[i-c] += 1 
            if c == 0 :
                B[i] += 1
            c -= 1
    A = B
    B = [0]*N
    K -= 1

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] * N

if N < K:
    C = [N] * N
    print(' '.join(map(str, C)))
    exit(0)

for k in range(K):
    for i in range(N):
        bright = A[i]
        left = max(0, i - bright)
        right = min(N - 1, i + bright)
        for j in range(left, right + 1):
            B[j] += 1
    A = copy.copy(B)
    if all([a == N for a in A]):
        break
    B = [0] * N

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

Submission status: Time Limit Exceeded

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

def change(arr):
  newAs = [0] * n
  for i, a in enumerate(arr):
    for t in range(max(i - a, 0), min(i + a + 1, n)):
      newAs[t] += 1
  return newAs


for temp in range(k):
  As = change(As)
print(' '.join(map(str, As)))

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
import numpy as np
import copy
for kk in range(k):
  r=[0]*n
  for ii in range(n):
    if a[ii]==0:
      r[ii]+=1
    else:
      for jj in np.arange(max(0,ii-a[ii]),min(n,ii+a[ii]+1)):
          r[jj]+=1
  if a==r:
    print(*a) # * to remove []
    exit()
  #print(kk,a) # test
  a=copy.copy(r)
print(*a) # * to remove []

Submission status: Time Limit Exceeded

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

def solve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    for _ in range(K):
        B = list(0 for _ in range(N))
        for i,d in enumerate(A):
            for j in range(max(i-d,0), min(i+d+1,N)):
                B[j] += 1
        A = B[:]
    return ' '.join(map(str,A))

if __name__ == '__main__':
    print(solve())

Submission status: Time Limit Exceeded

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

for _ in range(k):
    imos = [0 for i in range(n+1)]
    for idx, a in enumerate(al):
        imos[max(idx-a, 0)] += 1
        imos[min(idx+a+1, n)] -= 1
    al = []
    now = 0
    for i in imos:
        now += i
        al.append(now)
    if len(set(al)) == 1 and al[0] == n:
        break

print(*al[:-1])

Submission status: Time Limit Exceeded

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""

n,k = m()

a = l()
dp = [0 for i in range(n)]
ans = [0 for i in range(n)]
for i in range(min(100,k)):
	for j in range(n):
		po = a[j]
		if j - po < 0:
			dp[0] += 1
		else:
			dp[j-po] += 1
		if j + po + 1 <= n-1:
			dp[j+po+1] -= 1
	a[0] = dp[0]
	for j in range(1,n):
		dp[j] += dp[j-1]
		a[j] = dp[j]
	for j in range(n):
		dp[j] = 0

if k <= 100:
	print(jo(a))
	exit()

for j in range(n):
	a[j] += k-101

for j in range(n):
	po = a[j]
	if j - po < 0:
		ans[0] += 1
	else:
		ans[j-po] += 1
	if j + po + 1 <= n-1:
		ans[j+po+1] -= 1
for j in range(1,n):
	ans[j] += ans[j-1]
print(jo(ans))

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))
print(*a[:-1])

Submission status: Time Limit Exceeded

Solution code:
#-------------------------------------------------------------------------------
# Name:        module3
# Purpose:
#
# Author:      user
#
# Created:     13/06/2020
# Copyright:   (c) user 2020
# Licence:     <your licence>
#-------------------------------------------------------------------------------

def main():
    n,k = map(int,input().split())
    delighted_counter1 = list(map(int,input().split()))
    delighted_counter2 = [0] * n
    for i,light in enumerate(delighted_counter1):
        left = max(0,i-light)
        right = min(n,i+light+1)
        for j in range(left,right):
            delighted_counter2[j] += 1

    #print(delighted_counter2)


    for _ in range(k):
        #print(delighted_counter1)
        delighted_counter1 = list(delighted_counter2)
        delighted_counter2 = [0] * n
        for i,light in enumerate(delighted_counter1):
            left = max(0,i-light)
            right = min(n,i+light+1)
            for j in range(left,right):
                delighted_counter2[j] += 1

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


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
na = [0] * n

for c in range(k):
    for i in range(n):
        b[i] = 0
    for i in range(n):
        for j in range(n):
            if abs(i - j) <= (a[j] + 0.5):
                b[i] += 1
        na[i] = b[i]
    for i in range(n):
        a[i] = na[i]

ans = ""
for i in range(n):
    ans += str(b[i]) + " "

print(ans[: 2 * n - 1])

Submission status: Time Limit Exceeded

Solution code:
from math import floor

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

for _ in range(k):
  b = [0 for _ in a]
  for i in range(len(a)):
    d = a[i]
    r_min = max(floor(i - d - 0.5) + 1, 0)
    r_max = min(floor(i + d + 0.5), n - 1)
    for j in range(r_min, r_max + 1):
      b[j] += 1
  a = b
  
print(*a)

Submission status: Time Limit Exceeded

Solution code:
a,b=map(int,input().split())
l=list(map(int,input().split()))
for i in range(min(b,1000)):
  now=[0]*a
  for j in range(a):
    x=l[j]
    for k in range(max(0,j-x),min(a,j+x+1)):
      now[k]+=1
  l=now
for i in range(a):
  now[i]=min(now[i],a)
print(*now)

Submission status: Time Limit Exceeded

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


for cnt in range(K):
    X = [0] * N
    for i in range(N):
        d = A[i]
        for x in range(-1 * d, d + 1):
            if i + x >= 0 and i + x < N:
                X[i + x] += 1
    for i in range(N):
        A[i] = X[i]

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

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:
# coding: utf-8
# Your code here!
def LI():return list(map(int,input().split()))
def yes():print("YES")
def no():print("NO")

n,k=LI()
a=LI()

if k>=n:
    ans=[n]*n
    print(*ans)
    exit()


for _ in range(k):
    b=[0]*n
    for i in range(n):
        q=a[i]
        for j in range(i-q,i+q+1):
            if 0<=j<=n-1:
                b[j]+=1
    a=b[:]
    # print(_,a)
print(*a)

Submission status: Time Limit Exceeded

Solution code:
def main():
    number, operations = [int(x) for x in input().split()]
    dists = [int(x) for x in input().split()]

    for _ in range(operations):
        dists_new = [0] * number
        for i, d in enumerate(dists):
            start = max(0, i - d)
            end = min(i + d, number - 1)
            for j in range(start, end + 1):
                dists_new[j] += 1

        dists = dists_new[0:]

    print(*dists)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

for k in range(K):
  list = []
  for i in range(N):
    num = 0
    for j in range(N):
      if i ==j:
        num += 1
      elif A[j] >= abs(i-j):
        num += 1
    list.append(num)
  A = list
  
for l in range(N):
  print(A[l], end=" ")

Submission status: Time Limit Exceeded

Solution code:
n,k=[int(j)for j in input().split()]
a=[int(j)for j in input().split()]
if n<=k:
    print(*[n]*n)
    exit()
import copy
for _ in range(k):
    table=[0]*n
    for i in range(n):
        table[max(i-a[i],0)]+=1
        if i+a[i]+1<n:
            table[i+a[i]+1]-=1
    for i in range(1,n):
        table[i]+=table[i-1]
    a=copy.deepcopy(table)
print(*a)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import functools
import heapq
import itertools
import logging
import math
import os
import random
import string
import sys
from argparse import ArgumentParser
from collections import defaultdict, deque
from copy import deepcopy
from io import BytesIO, IOBase
from typing import Dict, List, Optional, Set, Tuple


def solve(values: List[int], N: int, K: int) -> List[int]:
    for _k in range(K):
        prev = values.copy()
        values = [0] * N
        for i, v in enumerate(prev):
            for j in range(max(0, i - v), min(N, v + i + 1)):
                values[j] += 1
    return values


def do_job(stdin, stdout):
    "Do the work"
    LOG.debug("Start working")
    # first line is number of test cases
    N, K = map(int, stdin.readline().split())
    values = list(map(int, stdin.readline().split()))
    # values = []
    # for _ in range(N):
    #     values.append(stdin.readline().split())
    result = solve(values, N, K)
    print(*result, file=stdout)


def print_output(testcase: int, result, stdout) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result), file=stdout)
    # 6 digits float precision {:.6f} (6 is the default value)
    # print("Case #{}: {:f}".format(testcase + 1, result), file=stdout)


BUFSIZE = 8192


class FastIO(IOBase):
    # pylint: disable=super-init-not-called, expression-not-assigned
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    # pylint: disable=super-init-not-called
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def configure_log() -> None:
    "Configure the log output"
    log_formatter = logging.Formatter("L%(lineno)d - " "%(message)s")
    handler = logging.StreamHandler(IOWrapper(sys.stderr))
    handler.setFormatter(log_formatter)
    LOG.addHandler(handler)


LOG = None
# for interactive call: do not add multiple times the handler
if not LOG:
    LOG = logging.getLogger("template")
    configure_log()


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    parser = ArgumentParser()
    parser.add_argument(
        "-v",
        "--verbose",
        dest="verbose",
        action="store_true",
        default=False,
        help="run as verbose mode",
    )
    args = parser.parse_args(argv)
    if args.verbose:
        LOG.setLevel(logging.DEBUG)
    stdin = IOWrapper(sys.stdin)
    stdout = IOWrapper(sys.stdout)
    do_job(stdin, stdout)
    stdout.flush()
    for h in LOG.handlers:
        h.flush()
    return 0


if __name__ == "__main__":
    sys.exit(main())

Submission status: Time Limit Exceeded

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

while min(a) < n and k > 0:
  mark = [0] * (n + 1)
  for i in range(n):
    mark[max([0, i - a[i]])] += 1
    mark[min([n, i + a[i] + 1])] -= 1
  a = [mark[0]]
  for i in range(1, n):
    a.append(a[-1] + mark[i])
  k -= 1

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

Submission status: Time Limit Exceeded

Solution code:
import copy

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

for i in range(k):
    b = [0] * (2 * n + 10)
    
    for m in range(n):
        d = a[m]
        if d > 0:
            for j in range(m - d, m + d + 1):
                b[j] += 1
        else:
            b[m] += 1
        
    a = copy.copy(b)
        
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()))
A2 = [0] * n

for l in range(k):
  for j in range(n):
    for i in range(n):
      if A[i] >= abs(i-j):
        A2[j] += 1
  A = A2
  A2 = [0] * n
print(*A)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
 
import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, k = LI()
a = LI()
for _ in range(k):
    lst = [0]*(n+1)
    for i in range(n):
        lst[max(i - a[i], 0)] += 1
        lst[min(i + a[i] + 1, n)] -= 1
    a = list(accumulate(lst))[:-1]

print(*list(accumulate(lst))[:-1])

Submission status: Time Limit Exceeded

Solution code:
import math


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

    for i in range(k):
        a = solve(a)
    return a


def solve(a):
    b = [0 for i in range(len(a))]

    for i, a_i in enumerate(a):
        for j in range(max(0, math.ceil(i - a_i - 0.5)), min(len(b), int(i + a_i + 0.5) + 1)):
            b[j] += 1
    return b


if __name__ == '__main__':
    result = main()
    print(" ".join([str(i) for i in result]))

Submission status: Time Limit Exceeded

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

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

    for l in range(k):
        a_new = [0 for _ in range(n)]
        for i in range(n):
            left = max(i-a[i], 0)
            right = min(i+a[i]+1, n)
            for j in range(left, right):
                a_new[j] += 1
        a = a_new[:]

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

count = 0

for t in range(K):
    for i in range(N):  # i番目の電球の明るさを決定する
        for j in range(N):  # 各電球jが、電球iを照らしているかを確認する
            if j - A[j] - 0.5 <= i <= j + A[j] + 0.5:
                count += 1
        tmp[i] = count
        count = 0
    for l in range(N):
        A[l] = tmp[l]

print(*A)