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

def resolve():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    B = [0 for i in range(n)]
    for m in range(k):
        B = [1 for i in range(n)]
        for i in range(n):
            for j in range(A[i]):
                if 0 <= i - j - 1:
                    B[i - j - 1] += 1
                if i + j + 1 < n:
                    B[i + j + 1] += 1
        A = copy.deepcopy(B)

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

resolve()

Submission status: Time Limit Exceeded

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

for m in range(0,k):
    temp=[0]*n
    for i in range(0,n):
        d=a[i]
        if d==n:
            temp[i]=n
        elif d !=0 :
            for x in range(i-d, i+d+1):
                if x >= 0 and x < n :
                    temp[x]+=1
        else:
            temp[i]+=1
    a=copy.copy(temp)

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

Submission status: Time Limit Exceeded

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

an = np.array(an)
for _ in range(k):
    d = np.zeros(n, int)
    for i in range(n):
        right = i - an[i]
        left = i + an[i] + 1
        if right < 0:
            right = 0
        if left > n:
            left = n
        d[right : left] += 1
    an = d
    if np.sum(an) == n**2:
        break

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

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
if((n+3)//2+1 <= k):
    c = [str(n)]*n
else:
    for i in range(k):
        b = [0]*n
        p = 0
        for j in range(n):
            if(a[j] == n):
                p += 1
            else:
                for k in range(max(0,j-a[j]),min(n-1,j+a[j])+1):
                    b[k] += 1
            for k in range(n):
                b[k] += p
        a = b
    c = [str(a) for a in b]
print(' '.join(c))

Submission status: Time Limit Exceeded

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

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

for i in range(K):
	A = calc(A)

print(*A)

Submission status: Time Limit Exceeded

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

for k in range(n[1]):
  ans = []
  for i in range(n[0]):
    ans.append(0)
  for i in range(n[0]):
    s1 = (i + 1) - a[i] - 0.5 # x - d - 0.5
    if 1 > s1:
      s1 = 1
    s2 = (i + 1) + a[i] + 0.5 # x + d + 0.5
    if n[0] < s2:
      s2 = n[0]
    s1 = math.ceil(s1)
    s2 = math.floor(s2) + 1
    for j in range(s1, s2):
      ans[j-1] += 1
  a = ans    

print(*a)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
for k in range(K):
   B=[0]*N
   for l in range(N):
      d=A[l]
      for i in range(max(l-d,0),min(l+d+1,N),1):
         B[i]+=1
   A=B
A=[str(a) for a 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=[int(s) for s in a0]
for f in range(k):
    for x in range(n):
        c=0
        for i in range(n):
            if a1[i]-abs(x-i)>=0:
                c=c+1
        a[x]=c
    a1=[int(s) for s in a]
    if sum(a)==n**n:
        break
a=[str(s) for s in a]
a=" ".join(a)
print(a)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
count = K
while count > 0:
  B = [0]*N
  for i in range(N):
    if A[i] == 0:
      B[i] += 1
    else:
      a = i-A[i]
      b = i+A[i]
      if N-1-i < A[i]:
        b = N-1
      if i < A[i]:
        a = 0
      c = list(range(a,b+1))
      for j in range(len(c)):
        B[c[j]] += 1
  else:
    count -= 1
    A = B
print(*B)

Submission status: Time Limit Exceeded

Solution code:
import copy
import numpy as np
# N = int(input())
N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]

for i in range(K):
    B = np.array([0 for k in range(N)])
    for j in range(N):
        L = A[j]
        B[max(j-L, 0): min(j+L+1, N)] += 1
    A = copy.deepcopy(list(B))
    if len(set(A)) == 1 and A[0] == N:
        break
print(*A)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
N,K = [int(x) for x in stdin.readline().rstrip().split()]
A = [int(x) for x in stdin.readline().rstrip().split()]
if N%2 == 0:
    b = N//2
else:
    b = (N//2) +2
if N==1:
    print(1)
    exit()
if K >= 160:
    for i in range(N-1):
        print(N,end=" ")
    print(N)
    exit()

for k in range(K):
    nextgen = [0]*N
    for i in range(N):
        # print("i=",i)
        a = A[i]
        start = i-a
        if i-a <0:
            start = 0
        end = i+a+1
        if i+a+1 <=N-1:
            nextgen[end] += -1
            end = N-1
        # print(start,end)
        nextgen[start] += 1
        # print(nextgen)
    dp = 0
    for i in range(N):
        dp += nextgen[i]
        A[i] = dp
s = ' '.join([str(i) for i in A])
print(s)

Submission status: Time Limit Exceeded

Solution code:
N , K = map(int,input().split())
C = list(map(int,input().split()))
def solve(C,N,K):
  A = C
  B = [0]*N
  for j in range(K):
    d = [0]*(N+1)
    for i in range(N):
      l = max([0 , i - A[i]])
      r = min([N-1 , i+A[i]]) + 1
      d[l] += 1
      d[r] -= 1
    B[0]=d[0]
    for i in range(N-1):
      B[i+1] = B[i] + d[i+1]
    A = B
  return(A)
B = solve(C,N,K)
print(' '.join(map(str, B)))

Submission status: Time Limit Exceeded

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

    flag = False
    for _ in a:
        if _ > 0:
            flag = True
            break

    if flag and k > n: 
        a = [n]*n
    else:
        for _ in range(k):
            num = [0]*n
            for _2 in range(n):
                min = _2 - a[_2] if 0 < _2 - a[_2] - 0.5 else 0
                max = _2 + a[_2] if n > _2 + a[_2] + 0.5 else n-1
                for _3 in range(min, max+1):
                    num[_3] += 1
            if a[0]==n and all(a):
                break
            if a[0]==0 and all(a):
                break


            a = num

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

n, k = map(int, input().split())
a = [int(x) for x in input().split()]
last = [n]*n
for i in range(k):
    temp = [0]*n
    for j in range(n):
        b = a[j]
        temp[j] += 1
        for k in range(1, b + 1):
            if j + k < n:
                temp[j + k] += 1
            if j - k >= 0:
                temp[j - k] += 1
    a = temp[:]
    if a == last:
        print(*a)
        sys.exit()
print(*a)

Submission status: Time Limit Exceeded

Solution code:
import copy
import math
import numpy 

n, k = map(int, input().split())
a = list(map(int, input().split()))
        
lo = int(math.log2(n) * 2 + 2)        

k = min(lo, k)

na = numpy.array(a)

for i in range(k):
    #b = [0] * (n + 2)
    b = numpy.zeros(n + 2,dtype='int')
    
    for m in range(n):
        d = na[m]
        if d > 0:
            if d > m:
                start = 0
            else: 
                start = m - d
                
            if (m + d + 1) > n:
                end = n
            else:
                end = m + d + 1
                
            for j in range(start, end):
                b[j] += 1
        else:
            b[m] += 1
            
        
    na = copy.copy(b)
        
for i in range(n):
    print(na[i], end=" ")

Submission status: Time Limit Exceeded

Solution code:
import math

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

for i in range(k):
    b = [0 for z in range(n)]
    for j in range(n):
        start = math.ceil(j-a[j]-0.5)
        end = math.floor(j+a[j]+0.5)+1
        for lit in range(max([0, start]),min([end, n])):
            b[lit] += 1
    for m in range(n):
       a[m] = b[m]

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

Submission status: Time Limit Exceeded

Solution code:
"""N個の電球　操作K回"""
N, K = map(int, input().split())

arr = list(map(int, input().split()))
count = 0

for _ in range(K):
    next = [0]*N
    for i in range(N):
        for j in range(i-arr[i],i+arr[i]+1,1):
            if 0<=j<=N-1:
                next[j] +=1
    arr = next
    count += 1

    if arr == [N]*N:
        print(*arr)
        exit()

print(*arr)

Submission status: Time Limit Exceeded

Solution code:
#C - Lamps
N,K= map(int,input().split())
A = list(map(int, input().split()))
# DP = [0]*N
# DP2 = [0]*N
DP = [0]*N
DP2 = [[0] *N for p in range(N)]
for _ in range(K):
    for i in range(N):
        for j in range(A[i],-A[i]-1,-1):
            if A[i] == 0:
                DP[i] += 1
            else:
                pass
            if i != i-j and i-j >= 0 and i-j < N and DP2[i-j][i] ==0:
                DP[i-j] += 1
                DP2[i-j][i] = 1

            else:
                pass
    #print(DP)
    for k in range(len(DP)):
        A[k] += DP[k]
    DP = [0]*N
    #print(DP2)
    #print(A)

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

Submission status: Time Limit Exceeded

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

    power_area = [set([i+1]) for i in range(n)]
    power_area, pre_a = get_power_area(n, a, power_area)
    #print("", power_area)
    #print(list(map(len, power_area)))

    for times in range(k-1):
        a = list(map(len, power_area))
        #print(a, pre_a)
        #power_area = get_power_area(n, list(map(len, power_area)), power_area)
        power_area, pre_a = get_power_area2(n, a, power_area, pre_a)
    #print(times, power_area)
    print(" ".join(list(map(lambda x: str(len(x)), power_area))))

def get_power_area(n, a, power_area):
    for i in range(n):
        for x in range(a[i]+1):
            #print(x)
            if i+x<n:
                power_area[i+x].add(i+1)
            if 0<=i-x:
                power_area[i-x].add(i+1)
    return power_area, a

def get_power_area2(n, a, power_area, pre_a):
    for i in range(n):
        diff = a[i] - pre_a[i]
        #print(diff)
        for x in range(diff):
            if i+pre_a[i]+x+1<n:
                power_area[i+pre_a[i]+x+1].add(i+1)
            if 0<=i-pre_a[i]-x-1:
                power_area[i-pre_a[i]-x-1].add(i+1)
    return power_area, a


if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

n, k, *a = map(int, read().split())

if k >= n**0.5 * 2:
    b = [n] * n
    print(*[b[i] for i in range(n)])
    exit()

for q in range(k):
    b = [0] * n
    for i in range(n):
        d = a[i]
        for j in range(i-d, i+d+1):
            if j < 0 or j >= n:
                continue
            b[j] += 1
    
    if b == [n] * n:
        break
    else:
        a = b

print(*[b[i] for i in range(n)])

Submission status: Time Limit Exceeded

Solution code:
def a(Num):
  if Num < 0:
    return 0
  else:
    return 1

def light(li,number):
  lis = []
  for i in range(number):
    n = 0
    for j in range(number):
      n += a(li[j]-abs(i-j))
    lis.append(n)
  li = lis
  return li

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

for x in range(K):
  A = light(A,N)
  
A = [str(a) for a in A]
A = " ".join(A)
print(A)

Submission status: Time Limit Exceeded

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

l_n=list(range(N))
l_k=list(range(K))
_result = [0]*N

for _ in l_k:
    result = _result.copy()
    
    for i in l_n:
        _idx_st = i - A[i]
        idx_st = 0 if _idx_st < 0 else _idx_st
        _idx_end = i + A[i]
        idx_end = N if _idx_end >= N else _idx_end + 1

        result[idx_st:idx_end]=[i+1 for i in result[idx_st:idx_end]]
    A = result.copy()
print(*result)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    n,k = map(int, input().split())
    a = list(map(int, input().split()))
    for i in range(k):
        nxt = [0]*n
        for j in range(len(a)):
            r = min(j + a[j], n-1) #look right
            l = max(j-a[j], 0) #look left
            for m in range(l, r+1):
                nxt[m] = min(nxt[m]+1,n)
        a, nxt = nxt, a
        if a == nxt:
            break
    print(*a)
resolve()

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numba

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

@numba.jit
def answer(N,K,A):
    rireki = []
    for count in range(K):
        newA = [list(itertools.chain.from_iterable([[i2 + 1 for i2 in range(int(i + 1 - v - 0.5),int(i + 1 + v + 0.5))] for i,v in enumerate(A)])).count(i + 1) for i,v in enumerate(A)]
        if newA in rireki:
            amari = K % count
            A = rireki[amari - 1]
            break
        rireki.append(newA)
        if newA == A:
            break
        A = newA
        if len(A) == A.count(len(A)):
            #print("OK")
            break
    return A

A = answer(N,K,A)
print(*A)

Submission status: Time Limit Exceeded

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AtoZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N,K = IL()
A = IL()
if K > 50:
  A = [N for i in range(N)]
  print(*A)
  exit()
  
while True:
  if K == 0:
    break
  SEGLEN = 18
  seg = [0 for i in range(2**(SEGLEN+1))]
  for i in range(N):
    l = max(0,i-A[i])
    r = min(N-1,i+A[i])
    l += 2**SEGLEN
    r += 2**SEGLEN+1
    while l < r:
      if l%2 == 1:
        seg[l] += 1
      if r%2 == 1:
        seg[r-1] += 1
      l = -(-l//2)
      r = r//2
  A = []
  MIN = INF
  for i in range(N):
    i += 2**SEGLEN
    ans = 0
    while i:
      ans += seg[i]
      i //= 2
    A.append(ans)
    MIN = min(MIN,ans)
  K -= 1
  if MIN == N:
    break
  
print(*A)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

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

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

Submission status: Time Limit Exceeded

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

for turn in range(min(n, k)):
    status = [0] * n
    for x in range(n):
      for y in range(max(0, x - a[x]), min(x + a[x] + 1, n)): 
            # if x + 1 - a[x] - 0.5 < y + 1 and y + 1 < x + 1 + a[x] + 0.5:
            # if (-1) * a[x] <= x - y <= a[x]:
            # if abs(x - y) <= a[x]:
            status[y] += 1
    a = status
print(' '.join(str(n) for n in a))

Submission status: Time Limit Exceeded

Solution code:
import copy
N,K = map(int,input().split())
while True:
    try:
        listA=list(map(int,input().split()))
    except:
        break;
        
for iter in range(K):
  lit_list=[0]*N
  for i in range(N):
    lit_list[i]=sum(1 for j,x in enumerate(listA) if abs(i-j)<=x) 
  listA=copy.deepcopy(lit_list)

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

Submission status: Time Limit Exceeded

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

class segtree:
    x_unit=0 # 要素として入れられる最大値
    def __init__(self,N):
        self.n=(1<<len(bin(N-1)[2:]))
        self.x=[self.x_unit]*(2*self.n)

    def build(self, seq):
        for i,j in enumerate(seq, start=self.n):  # n番目からseqをx配列に移していく
            self.x[i] = j
        for i in range(self.n-1, 0, -1):
            self.x[i] = 0
            # セグ木トーナメント表の左右を比較
            # 例えばn=8の時、seq[4]はx[12]に、seq[5]はx[13]に入っている
            # さらにx[14]とx[15]の間に来るのはx[7]、x[12]とx[13]の間に来るのはx[6]

    def fold(self,l,r): # 区間[l, r)値に+1 
        l+=self.n
        r+=self.n-1
        while l<r:
            if l%2==1: # lが奇数
                self.x[l]+=1
                l+=1 # 偶数に調節
            if r%2==0: # rが偶数
                self.x[r]+=1
                r-=1 # 開区間なので1個前は奇数番目の要素
            l //= 2
            r //= 2
        if l==r:
            self.x[l]+=1
        #print(self.x)
    def get(self,i): # seq[i]に対する値を取得 
        i+=self.n
        ret=self.x[i]
        while i>1:
            i //= 2
            ret+=self.x[i]
        return ret

for z in range(min(k,50)):
    seq=[0]*n
    q=[(max(0, i-a[i]), min(n,i+a[i]+1)) for i in range(n)]
    seg=segtree(n)
    seg.build(seq)
    for i in range(n):
        l,r=q[i]
        seg.fold(l,r)
    ans=[]
    for i in range(n):
        ans.append(seg.get(i))
    a=ans+[]
print(*a)

Submission status: Time Limit Exceeded

Solution code:
import math

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

b = [0]*n

for i in range(n):
    i0 = i+1
    if i0 - a0[i] - 0.5 < 1:
        amin = 1
    else:
        amin = math.ceil(i0 - a0[i] - 0.5)
    if i0 + a0[i] + 0.5 > n:
        amax = n
    else:
        amax = math.floor(i0 + a0[i] + 0.5)
    amin = int(amin)
    amax = int(amax)
    for j in range(amin-1,amax):
        b[j] += 1

a = [[0]*n for i in range(k+1)]

for i in range(n):
    a[0][i] = a0[i] 

for i in range(1,k+1):
    for j in range(n):
        a[i][j] = b[j]
    b=[0]*n
    for j in range(n):
        j0 = j+1
        if j0 - a[i][j] - 0.5 < 1:
            amin = 1
        else:
            amin = math.ceil(j0 - a[i][j] - 0.5)
        if j0 + a[i][j] + 0.5 > n:
            amax = n
        else:
            amax = math.floor(j0 + a[i][j] + 0.5)
        amin = int(amin)
        amax = int(amax)
        for l in range(amin-1,amax):
            b[l] += 1

aa = [0]*n
for i in range(n):
    aa[i] = str(a[k][i])

print(' '.join(aa))

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] * N
  for j in range(N):
    under, over = 0, N
    if j-As[j] > 0:
        under = j-As[j]
    if j+As[j] < N:
        over = j+As[j]+1
    for k in range(under, over):
        nextA[k] += 1
  As = nextA

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

Submission status: Time Limit Exceeded

Solution code:
N,K=input().split()
N=int(N)
K=int(K)
A=list(map(int,input().split()))
if K==1:
    B=[0]*N
    j=0
    for j in range(0,N):
        if A[j]>0:
            a=j-A[j]
            b=j+A[j]
            if a<0:
                a=0
            if b>=N:
                b=N-1
            k=a
            for k in range(a,b+1):
                B[k]+=1
                k+=1
        if A[j]==0:
            B[j]+=1
        j+=1
    A=B
i=0
if K>=2:
    for i in range(0,K):
        B=[0]*N
        j=0
        for j in range(0,N):
            if A[j]>0:
                a=j-A[j]
                b=j+A[j]
                if a<0:
                    a=0
                if b>=N:
                    b=N-1
                k=a
                for k in range(a,b+1):
                    B[k]+=1
                    k+=1
            if A[j]==0:
                B[j]+=1
            j+=1
        A=B
        i+=1
print(*A)

Submission status: Time Limit Exceeded

Solution code:
def incr(n):
  return n+1

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

for i in range(K):
  B = [0]*len(A)
  for j in range(len(A)):
    llim = max([0, j-A[j]])
    ulim = min([len(A), j+A[j]+1])
    B[llim:ulim] = list(map(incr, B[llim:ulim]))
  if A==B:
    break
  A=B

print(*A)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
def ligh(li):
  for x in range(k):
    if li==[n]*n:
      return li
    ne=[0]*(n+1)
    zr=[]
    lis=[]
    for (i,a) in zip(range(n),li):
      if a==0:
        zr.append(i)
      else:
        ne[max(0,i-a)]+=1
        ne[min(i+a+1,n)]-=1

    for i in range(1,n):
      ne[i]+=ne[i-1]
    for i in zr:
      ne[i]+=1
    li=ne[:-1]
    #print(li)
  return li

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

Submission status: Time Limit Exceeded

Solution code:
import math
import copy

light_count = 1


def init():
    game_info = input().split(" ")
    light_list = {}

    global light_count
    light_count = int(game_info[0])
    act_count = int(game_info[1])

    for index, value in enumerate(input().split(" ")):
        light_list[index + 1] = int(value)

    return act_count, light_list


def check_min(key, value):
    if math.ceil(key - value - 0.5) < 1:
        return 1

    else:
        return math.ceil(key - value - 0.5)


def check_max(key, value, light_count):
    if math.floor(key + value + 0.5) > light_count:
        return light_count

    else:
        return math.floor(key + value + 0.5)


def check_all(key, value):
    max_value = check_max(key, value, light_count)
    min_value = check_min(key, value)

    if max_value == light_count and min_value == 1:
        return True

    return False


def execute_action(light_list, remain_count):

    result = {}

    for key, value in light_list.items():
        min = check_min(key, value)
        max = check_max(key, value, light_count)

        for x in range(min, max + 1):
            if x in result:
                result[x] = result[x] + 1
            else:
                result[x] = 1

    return result


def main():
    act_count, light_list = init()

    for i in range(act_count):
        if all([check_all(key, value) for key, value in light_list.items()]):
            result_list = [str(light_count)] * light_count
            print(' '.join(result_list))
            return
        else:
            result = execute_action(light_list, act_count - i)
            light_list = copy.deepcopy(result)

    print(' '.join([str(i) for i in result.values()]))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AtoZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N,K = IL()
A = IL()
if K > 100:
  A = [N for i in range(N)]
  print(*A)
  exit()
  
while True:
  if K == 0:
    break
  SEGLEN = 18
  seg = [0 for i in range(2**(SEGLEN+1))]
  for i in range(N):
    l = max(0,i-A[i])
    r = min(N-1,i+A[i])
    l += 2**SEGLEN
    r += 2**SEGLEN+1
    while l < r:
      if l%2 == 1:
        seg[l] += 1
      if r%2 == 1:
        seg[r-1] += 1
      l = -(-l//2)
      r = r//2
  A = []
  MIN = INF
  for i in range(N):
    i += 2**SEGLEN
    ans = 0
    while i:
      ans += seg[i]
      i //= 2
    A.append(ans)
    MIN = min(MIN,ans)
  K -= 1
  if MIN == N:
    break
  
print(*A)

Submission status: Time Limit Exceeded

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

s = [0] * (n+1)

for j in range(k):
    # いもす法の加算処理
    for i, a in enumerate(a_list):
        l = max(0, i-a)
        r = min(n-1, i+a)
        s[l] += 1
        if r+1 != n+1:
            s[r+1] -= 1
    a = 0
    for i in range(n):
        a += s[i]
        s[i] = 0
        a_list[i] = a
for i in range(n):
    print(a_list[i], end=' ')
print()