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:
from itertools import accumulate


def main():
    n, k = map(int, input().split())
    a = [int(i) for i in input().split()]
    ini = [0] * n
    fin = [n] * n
    for _ in range(k):
        b = ini.copy()
        for i, ai in enumerate(a):
            b[max(i - ai, 0)] += 1
            if i + ai + 1 < n:
                b[i + ai + 1] -= 1
        a = list(accumulate(b))
        if a == fin:
            print(*a)
            return
    print(*a)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# import numpy as np
import sys
import copy


def xnxn(n=0, flag="v"):
    """
    args:
        int n: a number of lows to read
    example:
        input   1
        retrun  1

        input   1 2 3
        return  [1,2,3]
        input   1 2 3
                4 
        return  [[1,2,3],
                [4]]
    """
    if n == 0:
        temp = list(map(int, input().split()))
        if len(temp) == 1:
            if flag == "l":
                return temp
            else:
                return temp[0]
        elif len(temp) > 1:
            return temp
    else:
        temp = [list(map(int, input().split())) for _ in range(n)]
        return temp


def sp_xnxn(n=0):
    """
    args:
        int n: a number of lows to read
    example
        input   1
        retrun  [1]

        input   123
        return  [1,2,3]

        input   123
                4 
        return  [[1,2,3],
                [4]]
    """
    if n == 0:
        return [int(k) for k in xsxs()]
    else:
        return [[int(k) for k in xsxs()] for _ in range(n)]


def xsxs(n=0):
    """
    args:
        int n: a number of lows to read 
    example:
        input   AA
        retrun  AA

        input   A BBB CC
        return  ["A","BBB","CC"]

        input   A BB CCC
                D
        return  [["A","BBB","CC"],
                ["D"]]
    """
    if n == 0:
        temp = list(input().split())
        if len(temp) == 1:
            return temp[0]
        elif len(temp) > 1:
            return temp
    else:
        return [list(input().split()) for _ in range(n)]


def sp_xsxs(n=0):
    """
    args:
        int n: a number of lows to read 
        example:
            input   A
            retrun  ["A"]

            input   ABC
            return  ["A","B","C"]

            input   ABC
                    D
            return  [["A","B","C"],
                    ["D"]]
    """
    if n == 0:
        return [s for s in xsxs()]
    else:
        return [[s for s in xsxs()] for _ in range(n)]


n, k = xnxn()
a = xnxn()
a = [1] + a
for _ in range(k):
    tmp = copy.copy(a)
    for i in range(1, n + 1):
        idx = []
        c = 0
        for k in range(1, n + 1):
            if k - tmp[k] - 0.5 < i < k + tmp[k] + 0.5:
                c += 1
        a[i] = c

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

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
A = list(map(int, input().split()))
def light(A,K):
    ans=[0]*N
    lenl=[0]*N
    if K==0:
        A=[str(a) for a in A]
        p=" ".join(A)
        return print(p)
    else:
        for i in range(N):
            lenl[i]=A[i]+0.5
        for x in range(N):
            for y in range(N):
                if x==y:
                    ans[x]=ans[x]+1
                elif x<y:
                    if y+1-lenl[y]<x+1:
                        ans[x]=ans[x]+1
                else:
                    if y+1+lenl[y]>x+1:
                        ans[x]=ans[x]+1
        return light(ans,K-1)
light(A,K)

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n,k=mp()
a=lmp()
for i in range(k):
    if i%2==0:
        if len(set(a))==1 and a[0]==n:
            print(*a)
            exit()
        b=[0]*n
        for _ in range(n):
            for j in range(max(0,_-a[_]),min(n,_+a[_]+1)):
                b[j]+=1
    else:
        if len(set(b))==1 and b[0]==n:
            print(*b)
        a=[0]*n
        for _ in range(n):
            for j in range(max(0,_-b[_]),min(n,_+b[_]+1)):
                a[j]+=1
if k%2==0:
    print(*a)
else:
    print(*b)

Submission status: Time Limit Exceeded

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

def ope(A):
    B = [0]*N
    for i in range(1,N+1):
        for j in range(1,N+1):
            if i != j:
                if abs(j - i) <= A[j-1]:
                    B[i-1] += 1
                else:
                    pass
            else:
                pass
    BB = list(map(lambda x,y: x+y, B, [1]*N))
    return BB

for k in range(1,K+1):
    A = ope(A)

print(*A)

Submission status: Time Limit Exceeded

Solution code:
x=list(map(int, input().split()))
A=list(map(int, input().split()))
a=0
import copy


for p in range(x[1]):
    tmp=copy.deepcopy(A)
    for i in range(x[0]):
        for j in range(x[0]):
            if abs(j-i)<=A[j]:
                a+=1
        tmp[i]=a
        a=0
    A=tmp
    
    
L=[str(a) for a in A]
L=' '.join(L)
print(L)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, K = mapint()
now = list(mapint())
from math import sqrt
import numpy as np
iteration = min(N.bit_length()*2, K)
for k in range(iteration):
    nx = np.array([0]*N)
    for i, a in enumerate(now):
        nx[max(0, i-a):min(i+a+1, N)] += 1
    now = list(nx)
print(*now)

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)

print(" ".join([str(v) for v in Intensity]))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
@author: H_Hoshigi
"""

def simulation(N, K, A_list):
    for k in range(K):
        next_A_list = [0 for i in range(N)]
        for i in range(N):
            d = A_list[i]
            for j in range(i-d, i+d+1):
                if j >= 0 and j <= N-1:
                    next_A_list[j] += 1
        A_list = next_A_list[:]
        #print(" ".join([ str(i).zfill(2) for i in A_list]))
    return A_list

def main():
    N, K = map(int, input().split())
    A_list = list(map(int, input().split()))
    print(" ".join([ str(i) for i in simulation(N, K, A_list)]))

if __name__ == "__main__":
    main()
    """
    N = 11
    K = N
    A_list = [0 for i in range(N)]
    A_list[N//2] = 1
    print(" ".join([ str(i).zfill(2) for i in A_list]))
    simulation(N, K, A_list)
    """

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


@lru_cache(None)
def solve(s, N):
    lamps = [int(i) for i in s.strip().split()]
    dp = [0] * N
    for idx, l in enumerate(lamps):
        for j in range(idx - l, idx + l + 1):
            if j >= 0 and j < N:
                dp[j] += 1
    return " ".join([str(i) for i in dp])


def main():
    N, K = [int(i) for i in input().strip().split()]
    lamps = input().strip()

    for _ in range(K):
        lamps = solve(lamps, N)

    return lamps


if __name__ == "__main__":
    print(main())

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(k):
    b = [0] * n
    for j in range(n):
        mini = (j + 1) - a[j]
        if mini < 1:
            mini = 1
        maxi = (j + 1) + a[j]
        if maxi > n:
            maxi = n
        for l in range(mini, maxi + 1):
            b[l - 1] += 1
    else:
        a = b
for i in range(n):
    print(b[i],end=" ")

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())))
B0 = np.array([0] * N)
for k in range(K):
    B = B0.copy()
    # print(N, K, A, B)
    for i in range(N):
        a = A[i]
        left = max(i - a, 0)
        right = min(i + a + 1, N)
        # print(i, left, right)
        for j in range(left, right):
            B[j] += 1
    for i in range(N):
        A[i] = B[i]
# print(N, K, A, B)
print(" ".join(map(str, B)))

Submission status: Time Limit Exceeded

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

for _ in range(k):
    ranges = [(i-a-0.5, i+a+0.5) for i, a in enumerate(A, start=1)]
    B = []
    for i in range(n):
        count = 0 
        for r in ranges[:i]:
            if r[1] >= i+1:
                count += 1
        for r in ranges[i:]:
            if r[0] <= i+1:
                count += 1
        B.append(count)
    if A == B:
        A = B
        break
    A = B
print(' '.join(map(str, A)))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
A = lr()
# ある回数から先は全ての電球にNを足す
for _ in range(min(K, 40)):
    next = [0] * N
    for i in range(N):
        x = A[i]
        for j in range(max(0, i-x), min(N-1, i+x)+1):
            next[j] += 1
    A = next

print(*A)

Submission status: Time Limit Exceeded

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

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

    a = l[:]
    
    if min(a) == n:
        break

a = list(map(str, a))
print(" ".join(a))

Submission status: Time Limit Exceeded

Solution code:
n, K = map(int, input().split())
a = list(map(int, input().split()))
cnt = a.count(n)
for k in range(K):
    an = [cnt] * n
    for i in range(n):
        an[i] += 1
        for j in range(1, a[i]+1):
            if i - j >= 0 and an[i-j] < n:
                an[i-j] += 1
            if i + j < n and an[i+j] < n:
                an[i+j] += 1
    else:
        for i in range(n):
            if an[i] > n:
                an[i] = n
        a = an
        cnt = a.count(n)
        if cnt == n:
            break
print(*a)

Submission status: Time Limit Exceeded

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

for i in range(k):
    tmpa = a[:]
    b = [0] * n
    for j in range(n):
        for k in range(-tmpa[j], tmpa[j] + 1):
            if 0 <= j + k < n:
                b[j + k] += 1
    a = b[:]
    if sum(a) == n ** 2:
        break

print(*b)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = input().split()#string
A = list(map(int, A))
B = [0 for i in range(N)]
for i in range(K):
  B = [0 for i in range(N)]
  for j in range(N):
    tmp_low = j - A[j] 
    tmp_high = j + A[j] 
    if tmp_low <= 0:
      tmp_low = 0
    if tmp_high >= N-1:
      tmp_high = N-1
    for k in range(tmp_low, tmp_high+1, 1):
      B[k] = B[k] + 1
  A = B
print(' '.join(map(str, A)))

Submission status: Time Limit Exceeded

Solution code:
import sys

n, k = map(int, sys.stdin.readline().split())
a = list(map(int, sys.stdin.readline().split()))
lena = len(a)
shift = [0] * lena
b = [0] * lena

for _i in range(k):
    cur_shift = 0
    for i, lamp in enumerate(a):
        if i + lamp < lena:
            shift[i + lamp] += 1
        b[i] = 1 + cur_shift
        cur_shift += 1 - shift[i]
        shift[i] = 0

    # print(b)

    cur_shift = 0
    for i in range(lena - 1, -1, -1):
        lamp = a[i]
        if i - lamp >= 0:
            shift[i - lamp] += 1
        a[i] = b[i] + cur_shift
        cur_shift += 1 - shift[i]
        shift[i] = 0

    # print(a)

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

light = [0]*N
last_light = A
for j in range(K):
    for i in range(N):
        if i-last_light[i] < 0:
            start = 0
        else:
            start = i-last_light[i]
        if i+last_light[i] > N:
            last = N
        else:
            last = i+last_light[i]
        light = light[:start] + list(map(lambda x:x+1,light[start:last+1])) + light[last+1:]
    last_light = copy.copy(light)
    light = [0]*N

for i in range(N):
    last_light[i] = str(last_light[i])
print(' '.join(last_light))

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy

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

for _ in range(k):
    if sum(As) == n * n:
        break
    As_next = [0] * n
    for i in range(n):
        for j in range(max(0, i - As[i]), min(n, i + As[i] + 1)):
            As_next[j] += 1
    As = deepcopy(As_next)

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

Submission status: Time Limit Exceeded

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

x = A[:]

for _ in range(K):
    y = [0] * (N + 1)
    for i in range(N):
        y[max(0, i - x[i])] += 1
        y[min(N, i + x[i] + 1)] -= 1
        
    for i in range(N):
        y[i + 1] += y[i]
        
    x = y[:]
        
    
print(*x[:-1])

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
ans=list(0 for i in range(N))

for t in range(K):
    temp=A
    for j in range(N):
        ans[j]+=1
        for s in range(1,temp[j]+1):
            if  j+s<=N-1:
                ans[j+s]+=1
            if 0<=j-s:
                ans[j-s]+=1   
    if t!=K-1:
        A=ans
        ans=list(0 for i in range(N))
   
       
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
def update(a):
    b = [0] * len(a)
    for i, v in enumerate(a):
        strength = v # 2とか
        # print("strength:", strength)
        start = max(i - strength, 0) # 0 - 2 = -2
        end = i + strength + 1 # 0 + 2 + 1 = +3
        b[start:end] = [ 1+n for n in b[start:end]]
        # print("b:",b)
    return b

n, k = (int(n) for n in input().split())
a = [int(n) for n in input().split()]
# print(n, k)
# print(a)
for i in range(k):
    a = update(a)

# print(a)
result = ""
for v in a:
    result += str(v) + " "
result = result[:-1]
print(result)

Submission status: Time Limit Exceeded

Solution code:
import collections
n,k = map(int, raw_input().split(' '))
ais = map(int ,raw_input().split(' '))
for _ in range(k):

	h = collections.Counter()
	for i,d in enumerate(ais):
		u = i+1
		h[max(1, u - d)] += 1
		h[u + d + 1] -= 1

	cumul = 0
	for u in range(1, n+1):
		cumul += h[u]
		ais[u - 1] = cumul

for e in ais:print e,

Submission status: Time Limit Exceeded

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


for i in range(k):
  B=[0 for i in range(n)]
  for j in range(n):
    d=A[j]
    mi=j-d
    ma=j+d
    if mi<=0:
      mi=0
    if ma>=n:
      ma=n-1
    while mi<=ma:
      B[mi]=B[mi]+1
      mi=mi+1
  A=B
for i in range(int(len(A))):
  print(A[i],end="")
  if i!=int(len(A)):
    print(" ",end="")

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
    for i, a in enumerate(A):
        bottom = i - a
        top = i + a + 1
        if bottom < 0:
            bottom = 0
        if top > N:
            top = N
        B[bottom:top] = list(map(lambda x: x+1, B[bottom:top]))
    A = B[:]

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

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

    if operations >= number - 1:
        print(*([number] * number))
        return

    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
        if min(dists) == number:
            # すべての光が両端まで届く，変化しなくなる。
            break

    print(*dists)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
l1= input().split(' ')
n= int(l1[0])
k= int(l1[1])

start= input().split(' ')

def f(ar, n):
	new= []
	for _ in range(n):
		new.append(0)
	for index in range(n):
		d= int(start[index])
		if index-d<0:
			if index+d>len(ar)-1:
				for k in range(0, n):
					new[k]+=1
			else:
				for k in range(0, index+d+1):
					new[k]+=1
		elif index+d>len(ar)-1:
			for k in range(index-d, n):
				new[k]+=1
		else:
			for k in range(index-d, index+d+1):
				new[k]+=1
	return new


for _ in range(0,k):
	start= f(start, n)
print(*start, sep=' ')

Submission status: Time Limit Exceeded

Solution code:
import copy

def updaetAd(Ad, index, d):
    light_range =list(i for i in range(-d+index,d+index+1,1))
    for j in light_range:
        try:
            if j >= 0:
                Ad[j] += 1
        except:
            continue


def main():
    N, K = map(int,input().split(' '))
    A = list(map(int,input().split(' ')))
    for _ in range(K):
        Ad = [0] * N
        for i in range(N):
            updaetAd(Ad, i, A[i])
        A = copy.copy(Ad)

    ans = ''
    for i in A:
        ans += str(i) + ' '
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = [0 for _ in range(n)]

for i in range(k):
  for j in range(n):
    for r in range(j-a[j], j+a[j]+1):
      if(0<=r and r<n):
        b[r] += 1
  a = b[:]
  if(min(a) == n):
    break
  b = [0 for _ in range(n)]
  
ans = ""
for i in range(n):
  ans += str(a[i]) + " "
print(ans[:-1])

Submission status: Time Limit Exceeded

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

for k in range(k):
  result = [0] * n
  for i in range(n):
    for j in range(a[i]+1):
      if j == 0:
        result[i] += 1
      else:
        if i-j >= 0:
          result[i-j] += 1
        if i+j <= n-1:
          result[i+j] += 1
  a = result
print(" ".join(map(lambda n: str(n), result)))

Submission status: Time Limit Exceeded

Solution code:
import sys
#import copy
#import math
#import bisect
import numpy as np
#import itertools
#import collections
#from collections import deque
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
#from scipy.sparse import csr_matrix
#import functools

sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
#read = sys.stdin.buffer.read

def main():
    N, K = map(int, readline().split())
    A = np.array(readline().split(), dtype=np.int64)
    for i in range(K):
        B = np.zeros(N, dtype=np.int64)
        for j in range(N):
            st = max(0, j - A[j])
            ed = j + A[j] + 1
            B[st:ed] += 1
        #print(B)
        if np.all(B == N):
            A = B
            break
        A = B
    print(*A)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=[0]*n
ans=[0]*n
a=list(map(int,input().split()))

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

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

Submission status: Time Limit Exceeded

Solution code:
#import math
#=input()
#=int(input())
n,k=map(int,input().split())
a=list(map(int,input().split()))
#=[list(map(int,input().split())) for _ in range()]

for i in range(k):
    b = [1 for _ in range(n)]
    for j in range(n):
        w = a[j]
        if w != 0:
            for m in range(max(0,j-w),min(n,j+w+1)):
                b[m] += 1
            b[j] -= 1
    if a == b:
        break
    else:
        a = b
for __ in b:
    print(__, end = " ")

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
B=A[:]
for i in range(K):
    C = [0]*N
    for j in range(N):
        m=max(0,j-B[j])
        M=min(j+B[j], N-1)
        for k in range(m, M+1):
            C[k]+=1
    B=C[:]
    pas=True
    for k in range(0,N):
        if B[k] != N:
            pas=False
            break
    if pas:
        break
print(*B)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, k = list(map(int, input().split()))
    A = list(map(int, input().split()))
    C = [set(range(n)) for _ in range(n)]
    if k >= n:
        print(' '.join([n] * n))
    else:
        for _ in range(k):
            for i in range(n):
                rm = set()
                for j in C[i]:
                    if A[j] >= abs(i - j):
                        rm.add(j)
                C[i] -= rm
            A = [n - len(C[i]) for i in range(n)]
        print(' '.join(list(map(str, A))))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def light(A):
	B = [0]*N
	C = [0]*N

	for i in range(1,N+1):
		B[i-1] = i + (A[i-1] + 0.5)
		C[i-1] = i - (A[i-1] + 0.5)

	D = []
	for i in range(N):
		D.append([j for j in range(int(C[i]),int(B[i]))])
	D2 = list(itertools.chain.from_iterable(D))

	#A2 = [0]*N
	for i in range(N):
		A[i] = D2.count(i)

	return(A)

for i in range(K):
	light(A)

print(*A)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

a = deque(map(int, input().split()))
ad = {}
for i in range(n):
    ad[i] = a.popleft()

def makea(ad):
    newa = {}
    for i in range(n):
        newa[i] = 0
    for i in range(n):
        if i - ad[i] >= 0:
            if i + ad[i] <= n-1:
                for j in range(i-ad[i], i+ad[i]+1):
                    newa[j] += 1
            else:
                for j in range(i-ad[i], n):
                    newa[j] += 1
        elif i + ad[i] <= n-1:
            for j in range(i+ad[i]+1):
                newa[j] += 1
        else:
            for j in range(n):
                newa[j] += 1
    return newa

for _ in range(k):
    ad = makea(ad)

for i in ad.values():
    print(i, end=" ")

Submission status: Time Limit Exceeded

Solution code:
import sys
import os
import itertools
from collections import deque

def main():
    if os.getenv("ENV")=='LOCAL':
        sys.stdin = open(os.path.dirname(__file__)+'/input.txt', 'r')

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

    num=[0]*N
    for i in range(K):
        num=[0]*N
        for n in range(N):
            s = n-A[n] if n-A[n]>=0 else 0
            e = n+A[n]+1 if n+A[n]+1 <= N else N
            for m in range(s,e):
                # print(m)
                num[m]+=1
        A=num

    # print(A[])
    print(' '.join([str(a) for a in A]))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
A = lr()
# ある回数から先は全ての電球にNを足す
for _ in range(min(K, 10 ** 2)):
    next = [0] * N
    for i in range(N):
        x = A[i]
        for j in range(max(0, i-x), min(N-1, i+x)+1):
            next[j] += 1
    A = next

print(*A)

Submission status: Time Limit Exceeded

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

for k in range(K):
    newLight = [0] * N
    for i in range(N):
        light = d[k][i]
        for j in range(2 * light + 1):
            loc = i - light + j
            if(loc >= 0 and loc < N):
                newLight[loc] += 1
    d.append(newLight)

dk = d[K]
res = str(dk[0])
for i in range(1, N):
    res += " " + str(dk[i])
print(res)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import numpy as np


def solve(*args: str) -> str:
    n, k = map(int, args[0].split())
    A = np.array(tuple(map(int, args[1].split())), int)

    cur = A
    for _ in range(k):
        prev = cur
        cur = np.zeros(n, int)
        for i, p in enumerate(prev):
            cur[max(0, i-p):min(n, i+p+1)] += 1

    return ' '.join(map(str, cur))


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
a = list(map(int, input().split()))
b = []

for k in range(K):
    b = [0 for _ in range(N)]
    for i in range(N):
        for j in range(max(i-a[i], 0), min(i+a[i]+1, N)):
            b[j] += 1
        
    a = b
    
ans = ""
for i in range(N):
    ans += str(a[i])
    if i != N-1:
        ans += " "
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
N,K = map(int,input().split())
light = list(map(int,input().split()))
next_light = [0] * N

for _ in range(K):
    for i in range(N):
        now_l = light[i]
        for ii in range(now_l+1):
            if(i+ii<N):
                next_light[i+ii] += 1;

        for ii in range(now_l):
            if(i-1-ii>=0):
                next_light[i-1-ii] += 1;
    light = copy.copy(next_light)
    next_light = [0] * N



for s in light:
    print(s,end='')
    print(" ",end='')

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:
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
DP = [[0 for _ in range(N)] for _ in range(K+1)]
for i in range(N):
    DP[0][i] = A[i]

for i in range(1, K+1,1):
    for j in range(N):
        pl, mi = min(j + DP[i-1][j], N-1), max(j - DP[i-1][j], 0)
        for k in range(mi, pl+1, 1):
            DP[i][k] += 1

print(" ".join(map(str, DP[K])))

Submission status: Time Limit Exceeded

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

for i in range(K):
  ans=[0]*N
  for j in range(N):
    num=A[j]
    for k in range(max([j-num,0]),min([j+num+1,N])):
      ans[k]+=1
    #print(ans,max([j-num,0]),min([j+num,N-1]))
  A=ans
print(' '.join(map(str, ans)))

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
print(*a)

Submission status: Time Limit Exceeded

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


def updata(A, i):
    count = 0
    for j in range(N):
        if j < i:
            if j + A[j] + 0.5 >= i:
                count += 1
        elif j == i:
            count += 1
        else:
            if j - A[j] - 0.5 <= i:
                count += 1
    return count


for k in range(K):
    B = []
    for i in range(N):
        B.append(updata(A, i))
    A = B

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

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
dp=[[0]*n for i in range(k+1)]

for i in range(n):
    dp[0][i]=a[i]
    
for ki in range(1,k+1):
    for ni in range(n):
        for j in range(ni-dp[ki-1][ni],ni+dp[ki-1][ni]+1):
            if j>=0 and j<n:
                dp[ki][j]+=1
           
for i in range(n):
    print(dp[k][i],end=" ")
print()

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)

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

Submission status: Time Limit Exceeded

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

for i in range(k):
    b = [0] * n;

    for p in range(n):
        for q in range(max(p-a[p],0),min(p+a[p]+1,n)):
            b[q] += 1;
        
    for v in range(n):
        a[v] = b[v];

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

Submission status: Time Limit Exceeded

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

for i in range(k):
  temp=[0]*n
  for j in range(n):
    temp[max(0,j-a[j]):min(n+1,j+a[j]+1)] = map(lambda x: x + 1 , temp[max(0,j-a[j]):min(n+1,j+a[j]+1)])
    #print(temp)
  a=temp

a=[str(i) for i in a]

print(" ".join(a))

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

data = list(map(int, input().split()))

for x in range(K):
#	print(data)
	raise_queue = []
	down_queue = []
	for i, d in enumerate(data):
		heapq.heappush(raise_queue, (i - d, i + d))
	
	new_data = [0] * N
	height = 0
	ended = 0
	for i in range(N):
		while len(raise_queue) > 0 and raise_queue[0][0] <= i:
			height += 1
			heapq.heappush(down_queue, raise_queue[0][1])
			heapq.heappop(raise_queue)
		while len(down_queue) > 0 and down_queue[0] < i:
			height -= 1
			heapq.heappop(down_queue)
		
		new_data[i] = height
		if height == N:
			ended += 1
	
	data = new_data
	if ended == N:
		#print(x)
		break
	
print(*data)