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
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=15
    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:
import sys
n,k=map(int,input().split())
a=list(map(int,input().split()))

for i in range(k):
  b=[0]*n
  if k-i>n-2:
    for i in range(n):
      a[i]=n
    for i in a:
      print(i,end=' ')
    sys.exit()
  for j in range(n):
    for m in range(j-a[j],j+a[j]+1):
      if 0<=m<=n-1:
        b[m]=b[m]+1
  a=b
for i in a:
  print(i,end=' ')

Submission status: Time Limit Exceeded

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

#aru index wo nanko no denkyuu ga terashiteiruka
def imos(n,a,ban):
  imos_l=[0 for i in range(n)]
#  imos_l=a

  for i in range(n):
    x=i
    x_left=max(x-a[i],0)
    x_right=min(x+a[i],n-1)

    imos_l[x_left]+=1 #適宜加算する値に変える
    if (x_right+1)!=n:
      imos_l[x_right+1]-=1 #適宜加算する値に変える

    #シミュレート(累積和)
  b=[0]
  for i in range(1,n+1):
    b.append(imos_l[i-1]+b[i-1])

#    if i>ban+1:
#      break

#  return(b[1:],b[ban+1])
#  return(b[ban+1])
  return(b[1:])

#ans,t_ans=imos(n,a,0)
#ans=a
#ans=imos(n,a,0)
#print(ans)

for i in range(k):
#  b,bi=imos(n,a,i)
  b=imos(n,a,i)
#  print(b)
#  print(b)
#  a[i]=b
  a=b
#  ans.append(bi)

#  exit()
##print('\n')
#print(6)
print(*a)
#print(ans)

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 i in range(K):
  new_A_beta = []
  new_A_beta.clear()
  for j in range(N):
    from_num = (j+1) - A[j] -0.5
    to_num = (j+1) + A[j] + 0.5
    for k in range(N):
      if from_num <= (k+1) <= to_num:
        new_A_beta.append(k+1)
    new_A =[]
    new_A.clear()
    for l in range(N):
      new_A.append(new_A_beta.count(l+1))
  A.clear()
  for m in new_A:
    A.append(m)
    
print(*new_A)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
#import numpy as np
import re
import math
from collections import defaultdict
from collections import deque
import collections
from fractions import Fraction
import bisect
from queue import PriorityQueue
import itertools
from copy import deepcopy
import random
import time
import os
import sys
import datetime
from functools import lru_cache
from functools import reduce
readline=sys.stdin.readline
sys.setrecursionlimit(2000000)
alphabet="abcdefghijklmnopqrstuvwxyz"
numbers="0123456789"
mod=int(10**9+7)
inf=int(10**19)
class Edge():
    def __init__(self,x,y,val=1):
        self.x=x
        self.y=y
        self.val=val
class unionfind():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(n)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):
            self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def yn(b):
    if b:print("yes")
    else:print("no")
def Yn(b):
    if b:print("Yes")
    else:print("No")
def YN(b):
    if b:print("YES")
    else:print("NO")
def ispow(a,b):
    now=b
    while now<a:
        now*=b
    return now==a
def getbin(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def getfacs(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod_>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def nextcomb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:return num
def getprimes(n):
    if n==0:return []
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    ret=[]
    for a in range(n+1):
        if(A[a]):ret.append(a)
    return ret
def isprime(num):
    if(num<=1):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def ifelse(bbool,ret1,ret2):
    if bbool:return ret1
    else:return  ret2
def join(A,c=" "):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s
def factorize(n):
    b = 2
    ret=defaultdict(int)
    while b * b <= n:
        while n % b == 0:
            n //= b
            ret[b]+=1
        b+=1
    if n > 1:ret[n]+=1
    return ret
def pm(x):
    return x//abs(x)
def inputintlist(): 
    return list(map(int,input().split()))
def inputfloatlist(): 
    return list(map(float,input().split()))
def tozero(A):
    ret=[None]*len(A)
    for a in range(len(A)):
        ret[a]=A[a]-1
    return ret
def istanchouzouka(A):
    f=True
    prev=min(A)-1
    for a in A:
        if prev>=a:
            f=False
        prev=a
    return f
def istanchouhigensyou(A):
    f=True
    prev=min(A)-1
    for a in A:
        if prev>a:
            f=False
        prev=a
    return f
def getallsum(A):
    s=sum(A)
    dp=defaultdict(int)
    dp[0]=1
    for a in range(0,len(A)):
        for b in range(s,-1,-1):
            if b-A[a]>=0:
                dp[b]+=dp[b-A[a]]
    return dp
def yuukoutomukou(edges):
    ret=deepcopy(edges)
    for edge in edges:
        if not edge.x==edge.y:
            ret.append(Edge(edge.y,edge.x,edge.val))
    return ret
def dijkstra(edges,V,start):
    mincost=[inf]*V
    G=[[] for a in range(V)]
    for edge in edges:
        G[edge.x].append([edge.val,edge.y])
    Q=PriorityQueue()
    Q.put([0,start])#[cost,x]
    while not Q.empty():
        nowcost,nowx=Q.get()
        if mincost[nowx]==inf:
            mincost[nowx]=nowcost
            for cost,y in G[nowx]:
                newcost=nowcost+cost
                Q.put([newcost,y])
    return mincost
def warshallfloyd(edges,V):
    mincost=[[inf for b in range(V)] for a in range(V)]
    for a in range(V):mincost[a][a]=0
    for edge in edges:
        mincost[edge.x][edge.y]=min(mincost[edge.x][edge.y],edge.val)#x→yが複数ある場合のためにmin()する
    for k in range(V):
        for s in range(V):
            for t in range(V):
                if mincost[s][k]==inf or mincost[k][t]==inf:continue
                mincost[s][t]=min(mincost[s][t],mincost[s][k]+mincost[k][t])
    return mincost
def bellemanford(edges,V,start):
    mincost=[inf]*V
    mincost[start]=0
    for _ in range(V):
        for edge in edges:
            if mincost[edge.x]==inf:continue
            mincost[edge.y]=min(mincost[edge.y],mincost[edge.x]+edge.val)
    return mincost
def ruisekiwa(A):
    ret=[0]*(len(A)+1)
    for a in range(len(A)):
        ret[a+1]=ret[a]+A[a]
    return ret
def getmd(x1,y1,x2,y2):
    return abs(x1-x2)+abs(y1-y2)
def geted(x1,y1,x2,y2):
    return math.sqrt((x1-x2)**2+(y1-y2)**2)
class fordfulkerson():
    def __init__(self,edges,V,s,t):
        self.V=V
        self.used=[False]*V
        self.G=[[] for a in range(V)]
        self.s=s
        self.t=t
        for edge in edges:
            self.G[edge.x].append({"x":edge.x,"y":edge.y,"cap":edge.val,"rev":len(self.G[edge.y])})
            self.G[edge.y].append({"x":edge.y,"y":edge.x,"cap":0,"rev":len(self.G[edge.x])-1})
    def dfs(self,v,t,f=inf):
        if v==t:return f
        self.used[v]=True
        for a in range(len(self.G[v])):
            x=self.G[v][a]["x"]
            y=self.G[v][a]["y"]
            cap=self.G[v][a]["cap"]
            rev=self.G[y][self.G[x][a]["rev"]]
            if self.used[y] or cap==0:continue
            f2=self.dfs(y,t,min(f,cap))
            if f2>0:
                self.G[v][a]["cap"]-=f2
                rev["cap"]+=f2
                return f2
        return 0
    def maxflow(self):
        flow=0
        while True:
            self.used=[False]*V
            zouka=self.dfs(self.s,self.t)
            if zouka==0:break
            flow+=zouka
        return flow
def heron(a,b,c):
    s=(a+b+c)/2
    S=s(s-a)(s-b)(a-c)
    S=math.sqrt(S)
    return S
def getAreaOfTriangle(x1,y1,x2,y2,x3,y3):
    a=geted(x1,y1,x2,y2)
    b=geted(x2,y2,x3,y3)
    c=geted(x3,y3,x1,y1)
    return heron(a,b,c)






######################################################################################################



N,K=inputintlist()
A=inputintlist()
for k in range(min(20,K)):
    imos=[0]*(N+1)
    for a in range(len(A)):
        mmin=max(a-A[a],0)
        mmax=min(a+A[a],N-1)
        imos[mmin]+=1
        imos[mmax+1]-=1
    B=[0]*N
    B[0]=imos[0]
    for a in range(1,N):
        B[a]=imos[a]+B[a-1]
    A=B[:]
print(join(A))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import math

def cal_area(x_list):
    areas = []
    for i in range(N):
        min_x = max(math.ceil(i - x_list[i] - 0.5), 0)
        max_x = math.floor(i + x_list[i] + 0.5)
        areas.append((min_x, max_x))

    return areas

def cal_B(x_list):
    b_list = [0]*len(x_list)*2

    for temp in x_list:
        min_x = temp[0]
        max_x = min(temp[1], len(x_list))

        for j in range(min_x, max_x+1):
            b_list[j] += 1
    
    return b_list

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

    A = cal_area(A_list)
    B = cal_B(A)

    for _ in range(K - 1):
        A = cal_area(B)
        B = cal_B(A)

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

Submission status: Time Limit Exceeded

Solution code:
[N, K] = list(map(int, input().split()))
A = list(map(int, input().split()))
B = [0]*N
for i in range(K):
    for j in range(N):
        rmin = max(0, j-A[j])
        rmax = min(j+A[j]+1, N)
        for k in range(rmin, rmax):
            B[k] += 1
    for j in range(N):
        A[j] = B[j]
    B = [0]*N
map_result = map(str, A)
result = ' '.join(map_result)
print(result)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

for _ in range(K):
    f = []
    for i, e in enumerate(A):
        sp = range(max(0, i - e), min(N, i + e + 1))
        f.append([1 if j in sp else 0 for j in range(N)])
        A = np.sum(np.array(f), axis=0)


print(*A)

Submission status: Time Limit Exceeded

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

for k in range(K):
  B=np.zeros(N,dtype=np.int)
  for i in range(N):
    if A[i]==0:
      B[i]+=1
    else:
      for j in range(max(i-A[i],0),min(i+A[i]+1,N)):
        B[j]+=1
  A=B
print(*B)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
array = list(map(int, input().split()))
Array = [0]*n
def plusone(n):
    return n + 1

for j in range(k):
    for i in range(n):
        ai = array[i]
        Array[max(i-ai, 0):min(i+ai+1,n+1)] = map(plusone, Array[max(i-ai, 0):min(i+ai+1,n+1)])
        answer = Array
    array = Array
    Array = [0] * n

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

Submission status: Time Limit Exceeded

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

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


for i in range(k):
    nw=[0]*n
    for x,d in enumerate(a):
        l=x-d-0.5
        r=x+d+0.5
        for p in range(n):
            if p>=l and p<=r:
                nw[p]+=1
    
    a[:]=nw

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

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()
    zeros = [0 for i in range(n)]
    next = zeros.copy()
    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 = zeros.copy()

    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())
A = [int(i) for i in input().split()]
three_hold_list = [0] *(3*N)
ans = ans = [N] * N
if K >= N :
    print(*ans)
else:
    for i in range(K):
        Accum = [0] *(3*N)
        for j in range(N):
            Accum[N+j-A[j]] += 1
            Accum[N+j+A[j]+1] -= 1
        num = 0
        for l in range(3*N):
            num += Accum[l]
            three_hold_list[l] = num
        if three_hold_list[N:2*N] == ans:
            break
        else:
            A = three_hold_list[N:2*N]
    print(*three_hold_list[N:2*N])

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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



    xxxx = 0
    while True:
        xxxx += 1
        imos = [0] * (N + 2)
        if xxxx == 100 or xxxx == K + 1:
            break
        for i, a in enumerate(A):
            imos[max(0, i + 1 - a)] += 1
            imos[min(N + 1, i + 1 + a + 1)] -= 1

        ruiseki = [0] * (N + 2)
        for i in range(N + 2):
            ruiseki[i] = imos[i] + ruiseki[i - 1]

        for i, v in enumerate(ruiseki[1:N + 1]):
            A[i] = v

    print(*ruiseki[1:N + 1])



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

for i in range(K):
  nextA = [0 for _ in range(N)]
  for j in range(N):
    lamps = [int(max(0,j-As[j])<=k<=j+As[j]) for k in range(N)]
    nextA = [x+y for x, y in zip(nextA, lamps)]
  As = nextA

ans = ''
for A in As:
    ans += str(A) + ' '
print(ans.strip())

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=30
    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:
from collections import defaultdict
from math import gcd
import time
import sys
from collections import Counter
import itertools
import math
from decimal import *
import numpy as np
# read = sys.stdin.buffer.read
# readline = sys.stdin.buffer.readline
# readlines = sys.stdin.buffer.readlines
input = sys.stdin.readline

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


lcount = np.zeros(N, dtype=int)
for k in range(K):
    for i in range(N):
        minind = i-A[i] if i-A[i] > 0 else 0
        maxind = i+A[i] if i+A[i] < N else N-1
        lcount[minind:i+A[i]+1] += 1
    A = lcount
    lcount = np.zeros(N, dtype=int)


print(" ".join(list(A.astype("unicode"))))

Submission status: Time Limit Exceeded

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

def calc(a):
    for t in range(k):
        b = [0] * n
        for i in range(n):
            for j in range(n):
                if a[j] >=  abs(j - i):
                    b[i] += 1

        for i in range(n):
            if(max(n-i,i) > b[i]):
                break
            print("oh")
            for j in range(n):
                a[j] += n *(k-t)
            return a
        a = b
    return a

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy
from collections import deque
stdin = sys.stdin

mod = 10**9+7

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, k = na()
a = na()

def calc_lux(a):
    res = [1 for _ in range(len(a))]
    for i in range(len(a)):
        light = a[i]
        for j in range(light):
            le = i - (j+1)
            ri = i + (j+1)
            if le >= 0:
                res[le] += 1
            if ri < n:
                res[ri] += 1
    return res

for _ in range(k):
    # calc lux from a
    lux = calc_lux(a)

    if a==lux:
        a = lux
        break

    # overwrite a
    a = lux

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()
A = LIST()

class LazyBit():
    """区間加算、区間取得クエリをそれぞれO(logN)で答える
    add: 区間[l, r)にvalを加える
    get_sum: 区間[l, r)の和を求める
    l, rは0-indexed
    """
    def __init__(self, n):
        self.n = n
        self.bit0 = [0] * (n + 1)
        self.bit1 = [0] * (n + 1)
    def _add(self, bit, i, val):
        i = i + 1
        while i <= self.n:
            bit[i] += val
            i += i & -i
    def _get(self, bit, i):
        s = 0
        while i > 0:
            s += bit[i]
            i -= i & -i
        return s
    def add(self, l, r, val):
        """区間[l, r)にvalを加える"""
        self._add(self.bit0, l, -val * l)
        self._add(self.bit0, r,  val * r)
        self._add(self.bit1, l,  val)
        self._add(self.bit1, r, -val)
    def get_sum(self, l, r):
        """区間[l, r)の和を求める"""
        return self._get(self.bit0, r) + r * self._get(self.bit1, r) \
               - self._get(self.bit0, l) - l * self._get(self.bit1, l)

for _ in range(K):
	bit = LazyBit(N)
	for i, a in enumerate(A):
		bit.add(max(0, i-a), min(N, i+a+1), 1)
	for i in range(N):
		A[i] = bit.get_sum(i, i+1)
	if all(x==N for x in A):
		break

print(*A)

Submission status: Time Limit Exceeded

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

a = [0] * N
for k in range(K):
    if a[0] >= N:
        break
    a = [0] * N
    for i in range(N):
        a[max(0, i - A[i])] += 1
        if N - 1 >= (A[i] + i + 1):
            a[A[i] + i + 1] -= 1
    for j in range(N):
        A[j] = A[j - 1] if j > 0 else 0
        A[j] += a[j]
    # print("k=", k, A)


for i in range(N):
    print(A[i], end="")
    if i < N - 1:
        print(" ", end="")
print()