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:
#!/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 solveFast(values: List[int], N: int, K: int) -> List[int]:
    result = [0] * N
    for v, i in sorted(((v, i) for i, v in enumerate(values)), reverse=True):
        v = max(v, K)
        for j in range(max(0, i - v), min(N, v + i + 1)):
            n = abs(j - i)
            if n == 0:
                result[j] += 1
            else:
                result[j] += n * (n + 1) // 2
    return result


def solve(values: List[int], N: int, K: int) -> List[int]:
    if K >= N - 1:
        return [N] * N
    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
        if all(v == N for v in values):
            break
    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()))

Z = [N]*N

while K > 0 and A != Z:
    K = K - 1
    B = [0]*(N+1)
    for i in range(N):
        B[max(0,i-A[i])]+=1
        B[min(N-1,i+A[i])+1]-=1
    for i in range(1,N):
        B[i]+=B[i-1]

    A = B[0:N]

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

Submission status: Time Limit Exceeded

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

def f(A):
  D=[0]*(N+1)
  for j in range(N):
    d=A[j]
    mi=max(j-A[j],0)
    ma=min(j+A[j],N-1)
    D[mi]+=1
    D[ma+1]-=1   
  for j in range(1,N):
    D[j]+=D[j-1]
  A=D
  return A 

for i in range(K):
  D=f(A)
  A=D
  if A[:-1]==[N]*(N):
    break
print(*A[:-1])

Submission status: Time Limit Exceeded

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

for count in range(k):
    range_diff = [0] * n
    for pos in range(n):
        candidate_min = pos - a[pos]
        candidate_max = pos + a[pos] + 1
        if pos - a[pos] >= 0:
            min = pos - a[pos]
        else:
            min = 0
        range_diff[min] += 1
        if candidate_max <= n-1:
            range_diff[candidate_max] -= 1
    for i in range(1, n):
        range_diff[i] += range_diff[i-1]
    a = range_diff
    if count >= 43:
        break

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

Submission status: Time Limit Exceeded

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

from itertools import accumulate
    
for _ in range(K):
    ans=[0]*(N+1)
    for i,a in enumerate(A):
        ans[max(0,i-a)]+=1
        ans[min(i+a+1,N)]-=1
    A = list(accumulate(ans))[:-1]
print(*A)

Submission status: Time Limit Exceeded

Solution code:
import sys

def input():
    return sys.stdin.readline()[:-1]


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

for i in range(k):
    b = [0] * n
    for j in range(n):
        l = max(0, j-a_li[j])
        r = min(n-1, j+a_li[j])
        b[l] += 1
        if (r+1<n):
            b[r+1] -= 1
    for j in range(n-1):
        b[j+1] += b[j]
    a_li = b
print(*a_li)

Submission status: Time Limit Exceeded

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

def f(A):
  D=[0]*(N+1)
  for j in range(N):
    d=A[j]
    mi=max(j-A[j],0)
    ma=min(j+A[j],N-1)
    D[mi]+=1
    D[ma+1]-=1   
  for j in range(1,N):
    D[j]+=D[j-1]
  A=D
  return A 

for i in range(K):
  D=f(A)
  A=D
  if A==[N]*(N+1):
    break
print(*A[:-1])

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import numpy as np
def main():
    #入力
    readline=stdin.readline
    n,k=map(int,readline().split())
    a=np.array(list(map(int,readline().split())),dtype=np.int64)

    cnt=0
    while cnt<k:
        s=[0]*n
        for i in range(n):
            x_min=i-a[i]
            x_max=i+a[i]+1
            s[max(0,x_min)]+=1
            if n-1<x_max:
                pass
            else:
                s[x_max]-=1
        a=np.cumsum(s)
        cnt+=1
        
        if a[a==n].size==n:
            break

    print(*a)

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# 累積和
import numpy as np


def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    A = np.array(a, dtype=np.int64)
    for _ in [0] * k:
        B = np.zeros(n + 1, dtype=np.int64)
        for i in range(n):
            left = max(0, i - A[i])
            right = min(n, i + A[i] + 1)
            B[left] += 1
            B[right] -= 1
        A = np.cumsum(B)[:n]
        if np.all(A == n):
            break

    print(*A)


if __name__ == "__main__":
    main()

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.array(A)

def work(lamp_list):
    lamp = [0] * N
    lamp = np.array(lamp)
    for i in range(len(lamp_list)):
        lamp[max(0, i-lamp_list[i])] += 1
        if i+lamp_list[i] + 1 < N:
            lamp[i+lamp_list[i] + 1] -= 1
    lamp = np.cumsum(lamp)
        
    return lamp
lamp_list = A
for _ in range(K):
    tmp = lamp_list
    lamp_list = work(lamp_list)
    if (lamp_list == tmp).all():
        break
for i in lamp_list:
    print(i, end=" ")

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 i in range(N):
    l = max(0, i - A[i])
    r = min(i + A[i] + 1, N)
    B[l] += 1
    if r < N:
      B[r] -= 1

  for j in range(N - 1):
    B[j + 1] += B[j]
  
  if k ** 2 >= N:
    break
  A = B
  
for b in B:
  print(b, end=" ")

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, K = tuple(int(c) for c in input().split(' '))
A = [0]
A.extend(tuple(int(c) for c in input().split(' ')))
A = np.array(A, dtype=np.int64)

for _ in range(K):
    B= np.zeros(N+1, dtype=np.int64)
    for i in range(1, N+1):
        lower = max(1, i-A[i])
        upper = min(N, i+A[i])
        #print(i, lower, upper)
        B[lower:upper+1] += 1
    A = B
    if np.all(A[1:] == N):
        print(' '.join([str(s) for s in A[1:]]))
        exit()
print(' '.join([str(s) for s in A[1:]]))

Submission status: Time Limit Exceeded

Solution code:
def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    dict = {}
    temp = {}
    ruiseki = {}
    for i in range(N):
        dict[i+1] = A[i]
        temp[i+1] = 0
        ruiseki[i+1] = 0

    dict[N+1] = 0
    temp[N+1] = 0
    ruiseki[N+1] = 0

    for j in range(K):
        for m in range(1,N+1):
            if dict[m] < N:
                break
            else:
                if m == N:
                    del(dict[N+1])
                    ans = list(dict.values())
                    ans2 = ' '.join(map(str,ans))
                    return(ans2)
                continue

        for h in range(1,N+1):
            temp2 = dict[h]
            if h - temp2 <= 0:
                temp[1] += 1
            else:
                temp[h - temp2] += 1

            if h+temp2+1 > N:
                temp[N+1] -= 1
            else:
                temp[h+temp2+1] -= 1

        for n in range(1,N+2):
            if n == 1:
                ruiseki[n] = temp[1]
                continue
            ruiseki[n] = ruiseki[n-1] + temp[n]

        for i in range(1,N+2):
            dict[i] = ruiseki[i]
            temp[i] = 0
            ruiseki[i] = 0

    del(dict[N+1])
    ans = list(dict.values())
    ans2 = ' '.join(map(str,ans))
    return(ans2)

print(main())

Submission status: Time Limit Exceeded

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

from itertools import accumulate

if N-min(A) <= K:
    print(*[N]*N)
    exit()
    
ans=[0]*(N+1)
for _ in range(K):
    for i,a in enumerate(A):
        ans[max(0,i-a)]+=1
        ans[min(i+a+1,N)]-=1
    A = list(accumulate(ans))[:-1]
    ans=[0]*(N+1)
    if all(i == N for i in A):
        break
print(*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.array(A)

def work(lamp_list):
    lamp = [0] * N
    lamp = np.array(lamp)
    for i in range(len(lamp_list)):
        lamp[max(0, i-lamp_list[i])] += 1
        if i+lamp_list[i] + 1 < N:
            lamp[i+lamp_list[i] + 1] -= 1
    lamp = np.cumsum(lamp)
        
    return lamp
lamp_list = A
for _ in range(K):
    if (lamp_list == work(lamp_list)).all():
        break
    
    lamp_list = work(lamp_list)
for i in lamp_list:
    print(i, end=" ")

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int,input().split())
A = list(map(int,input().split()))
for t in range(K):
  B=[0]*(N+1)
  for i in range(N):
    B[max(0,i-A[i])]+=1
    B[min(N,i+A[i]+1)]-=1
  for i in range(N-1):
    B[i+1]+=B[i]
  B.pop()
  A=B
print(*A)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
b = [0]*N
def add_lit(i, d):
	for x in range(i-d,i+d+1):
		if x < 0 or x >= N:
			continue
		else:
			b[x] += 1
	return b

def put_list(inlist):
	for i in range(0,N):
		add_lit(i, inlist[i])

for k in range(K):
	if k == 0:
		put_list(A)
	else:
		A = b
		b = [0]*N
		put_list(A)

[print(x) for x in b]

Submission status: Time Limit Exceeded

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

def f(A):
  D=[0]*(N+1)
  for j in range(N):
    d=A[j]
    mi=max(j-A[j],0)
    ma=min(j+A[j],N-1)
    D[mi]+=1
    D[ma+1]-=1   
  ans=0
  C=[]
  for i in D:
    ans+=i
    C.append(ans)
  return C


for i in range(K):
  D=f(A)
  A=D
  if A==[N]*(N+1):
    break
print(*A[:-1])

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
lst = list(map(int, input().split()))
for i in range(min(k,41)):
    lit = [0 for _ in range(n)]
    for _ in range(0, n):
        mx = max(0,_ - lst[_])
        mn = min(n, _ + lst[_] +1)
        lit[mx:mn] = map(lambda x:x+1, lit[mx:mn])
    lst = lit
lst = [str(_) for _ in lst]
ans = ' '.join(lst)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, K = tuple(int(c) for c in input().split(' '))
A = [0]
A.extend(tuple(int(c) for c in input().split(' ')))
A = np.array(A, dtype=np.int64)

for _ in range(K):
    s = [i for i in range(1, N+1) if A[i] > 0]
    t = [i for i in range(1, N+1) if A[i] == 0]
    B= np.zeros(N+1, dtype=np.int64)
    for i in s:
        lower = max(1, i-A[i])
        upper = min(N, i+A[i])
        #print(i, lower, upper)
        B[lower:upper+1] += 1
    B[t] += 1
    A = B
print(' '.join([str(s) for s in A[1:]]))

Submission status: Time Limit Exceeded

Solution code:
import sys

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


def update(a):
    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
    return b


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

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

for q in range(k):
    a = update(a)

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    dict = {}
    temp = {}
    ruiseki = {}
    for i in range(N):
        dict[i+1] = A[i]
        temp[i+1] = 0
        ruiseki[i+1] = 0

    dict[N+1] = 0
    temp[N+1] = 0
    ruiseki[N+1] = 0

    for j in range(K):
        for m in range(1,N+1):
            if dict[m] < N:
                break
            else:
                if m == N:
                    ans = list(dict.values())
                    ans2 = str(ans[0])
                    for i in range(1,N):
                        ans2 += (' ' + str(ans[i]))
                    return(ans2)
                continue

        for h in range(1,N+1):
            temp2 = dict[h]
            if h - temp2 <= 0:
                temp[1] += 1
            else:
                temp[h - temp2] += 1

            if h+temp2+1 > N:
                temp[N+1] -= 1
            else:
                temp[h+temp2+1] -= 1

        for n in range(1,N+2):
            if n == 1:
                ruiseki[n] = temp[1]
                continue

            ruiseki[n] = ruiseki[n-1] + temp[n]

        for i in range(1,N+2):
            dict[i] = ruiseki[i]
            temp[i] = 0
            ruiseki[i] = 0

    ans = list(dict.values())
    ans2 = str(ans[0])
    for i in range(1,N):
        ans2 += (' ' + str(ans[i]))
    return(ans2)

print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy
import numpy as np

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

N, K = map(int, readline().split())
A = np.array(read().split(), np.int64)


if K > 50:
    A = [N]*N
else:
    for _ in range(K):
        B = np.zeros_like(A)
        for i in range(N):
            l = max(0, i - A[i])
            r = min(N-1, i + A[i])
            B[l] += 1
            if (r+1 < N):
                B[r+1] -= 1
        B = np.cumsum(B)
        A = copy.copy(B)




for _ in A:
    print(_, end=' ')

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, K = tuple(int(c) for c in input().split(' '))
A = [0]
A.extend(tuple(int(c) for c in input().split(' ')))
A = np.array(A, dtype=np.int64)

for _ in range(K):
    B= np.zeros(N+1, dtype=np.int64)
    for i in range(1, N+1):
        lower = max(1, i-A[i])
        upper = min(N, i+A[i])
        #print(i, lower, upper)
        B[lower:upper+1] += 1
    A = B
print(' '.join([str(s) for s in A[1:]]))

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy
import numpy as np

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

N, K = map(int, readline().split())
A = np.array(read().split(), np.int64)


K = min(50, K)
for _ in range(K):
    B = np.zeros_like(A)
    for i in range(N):
        l = max(0, i - A[i])
        r = min(N-1, i + A[i])
        B[l] += 1
        if (r+1 < N):
            B[r+1] -= 1
    B = np.cumsum(B)
    A = copy.copy(B)




for _ in A:
    print(_, end=' ')

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import numba
from numba import jit, njit, prange
# -- numba (jit compile) ------------
@njit
def calc(x, zero, BB):
    for j in range(1, x + 1):
        pp = BB[j - 1]

        if (pp == 0):
            zero[int(j - 1)] += 1
            # print(d)
            continue
        if (pp == x):
            zero += 1
            '''
            if (k - i > (n//2)):
                ans = [str(i) for i in check]
                # print(ans)
                print(' '.join(ans))
                exit()
            # print(d)
            '''
            continue

        left = j - BB[j - 1] - 1
        # print(left)
        if (left < 0):
            left = 0
        right = j + BB[j - 1]
        #print('R: ',right)
        if (right > x - 1):
            right = x
        #print('L&R: ', left, right)

        zero[int(left): int(right)] += 1
        #print(j, d)

    return zero


# ---- read ---------------------------------
n, k = map(int, input().split())
a = list(map(int, input().split()))
bb = np.array(a, dtype=np.int64)
# print(bb)
check = np.full(n, n, dtype=np.int64)
# --- main ----------------------------
for i in range(k):
    #d = [0] * n
    # print(i)
    d = np.zeros(n, dtype=np.int64)
    d = calc(n, d, bb)
    bb = d

    if (all(bb == check)):
        break

# -------------------------------
ans = [str(i) for i in bb]
# print(ans)
print(' '.join(ans))

Submission status: Time Limit Exceeded

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


def read():
    N, K = map(int, input().strip().split())
    A = list(map(int, input().strip().split()))
    return N, K, A


def solve(N, K, A):
    d = [0 for i in range(N+1)]

    for k in range(K):
        for i in range(N):
            d[i] = 0
        
        for i in range(N):
            l = max(0, i-A[i])
            r = min(N, i+1+A[i])
            d[l] += 1
            d[r] -= 1
        
        terminate = True
        v = 0
        for i in range(N):
            v += d[i]
            A[i] = v
            if terminate and A[i] < N:
                terminate = False
        if terminate:
            break         
    print(*[a for a in A])


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Time Limit Exceeded

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

for i in range(k):
    b = [0] * (n + 1)
    for j in range(n):
        b[max(0, j - a[j])] += 1
        b[min(n, j + a[j] + 1)] -= 1
    a = list(accumulate(b))
    if sum(a) == n ** 2:
        a.pop()
        print(*a)
        exit()

a.pop()
print(*a)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    dict = {}
    temp = {}
    ruiseki = {}
    for i in range(N):
        dict[i+1] = A[i]
        temp[i+1] = 0
        ruiseki[i+1] = 0

    dict[N+1] = 0
    temp[N+1] = 0
    ruiseki[N+1] = 0

    for j in range(K):
        for m in range(1,N+1):
            if dict[m] < N:
                break
            else:
                if m == N:
                    ans = list(dict.values())
                    ans2 = str(ans[0])
                    for i in range(1,N):
                        ans2 += (' ' + str(ans[i]))
                    return(ans2)
                continue

        for h in range(1,N+1):
            temp2 = dict[h]
            if h - temp2 <= 0:
                temp[1] += 1
            else:
                temp[h - temp2] += 1

            if h+temp2+1 > N:
                temp[N+1] -= 1
            else:
                temp[h+temp2+1] -= 1

        for n in range(1,N+2):
            for k in range(1,n+1):
                ruiseki[n] += temp[k]


        for i in range(1,N+2):
            dict[i] = ruiseki[i]
            temp[i] = 0
            ruiseki[i] = 0

    ans = list(dict.values())
    ans2 = str(ans[0])
    for i in range(1,N):
        ans2 += (' ' + str(ans[i]))
    return(ans2)

print(main())

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):
    S = [0] * (N + 1)
    for i, a in enumerate(A):
        l = min(N-1, max(0, i-a))
        r = min(N-1, i+a)
        S[l] += 1
        S[r+1] -= 1
    t = 0
    for i in range(N):
        t += S[i]
        A[i] = t
    if sum(A) == N**2:
        break
print(*A)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))  # 整数のリスト
    B = [0] * N

    for j in range(K):
        for i in range(N):
            l = max(0, i-A[i])
            r = min(N-1, i+A[i])
            B[l] += 1
            if r+1 < N: B[r+1] -= 1
        for i in range(1,N):
            B[i] += B[i-1]
        A = B
        B = [0] * N

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

import numpy as np

t= min(k, 45)
bn = np.zeros((t,n), dtype=int)

for k in range(t):
    if k==0:
        for i in range(n):
            for j in range(max(i - an[i], 0), min(n, i + an[i] + 1)):
                bn[k][j] += 1
    else:
        for i in range(n):
            for j in range(max(i - bn[k - 1][i], 0), min(n, i + bn[k - 1][i] + 1)):
                bn[k][j] += 1


print(*bn[t-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit

b_n, i_k = map(int, input().split())
lamps = np.array([int(x) for x in input().split()])
act = np.zeros(b_n, dtype=np.int64)
one = np.ones(b_n, dtype=np.int64)

@njit
def loop(n, k, lamps, act, one):
    init = lamps
    for i in range(k):
        act[:] = 0
        for i in range(n):
            # if init[i] == 0:
            #     continue
            dmin = max(0, i - int(init[i]))
            dmax = min(n-1, i + int(init[i]))
            # if dmin < 0:
            #     dmin = 0
            # if dmax > n-1:
            #     dmax = n-1
            act[dmin:dmax+1] += 1
            act[i] -= 1
        init = act + one
    return init
result = loop(b_n, i_k, lamps, act, one)
ans = list(map(str,result.tolist()))
print(" ".join(ans))

Submission status: Time Limit Exceeded

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

def loop(a,k):
  if k>41:
    ans=np.ones(N)*N
  else:
    ans=a
    for j in range(k):
      B=np.zeros(N+1)
      for i in range(N):
        B[max(0,i-int(ans[i]))] +=1
        B[min(N,i+int(ans[i])+1)] -=1
      ans=np.cumsum(B)[:N]
  return ans

for i in loop(A,K):
  print(int(i))

Submission status: Time Limit Exceeded

Solution code:
def get_lump(target_list, num):
    result_list = [0] * num
    for target_num in range(len(target_list)):
        min_range = target_num - target_list[target_num] - 0.5
        max_range = target_num + target_list[target_num] + 0.5
        for result_num in range(len(result_list)):
            if min_range < result_num < max_range:
                result_list[result_num] += 1
    if target_list == result_list:
        return False, target_list
    else:
        return True, result_list


def main():
    total = list(map(int, input().split()))
    akarusa = list(map(int, input().split()))

    flg = True
    for i in range(total[1]):
        if flg:
            flg, akarusa = get_lump(akarusa, total[0])
        else:
            break

    kaitou = ''
    for j in range(len(akarusa)):
        if kaitou == '':
            kaitou = str(akarusa[j])
        else:
            kaitou = kaitou + ' ' + str(akarusa[j])

    print(kaitou)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,k,*l = map(int,open(0).read().split())

import copy
import numpy as np
import sys

def loop(n,k,l):
    for i in range(k):
        ll = np.array([0] * n)
        for j, e in enumerate(l):
            ll[max(0,j-e):min(n,j + e+1)] += 1

        l =copy.deepcopy(ll)

        if np.all(l == n):
            break
    
    return l

l =  loop(n,k,l)

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

Submission status: Time Limit Exceeded

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

import numpy as np

t= min(k, 45)
bn = np.zeros((t,n), dtype=int)

for k in range(t):

    for i in range(n):
        if k==0:
            for j in range(max(i - an[i], 0), min(n, i + an[i] + 1)):
                bn[k][j] += 1
        else:
            for j in range(max(i-bn[k-1][i],0), min(n, i+bn[k-1][i]+1)):
                bn[k][j] += 1

#print(bn)

print(*bn[t-1])

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):
        d = a[j] + 0.5
        for l in range(int(d)):
            if j + l + 1 < n:
                b[j + l + 1] += 1
            if j - l - 1 >= 0:
                b[j - l - 1] += 1
    #print('ans')
    #print(list(x + y for x, y in zip([1] * n, b)))
    a = list(x + y for x, y in zip([1] * n, b))
print(*a, sep=' ')

Submission status: Time Limit Exceeded

Solution code:
N, K= map(int,input().split())
A = list(map(int,input().split()))
p=0
while p<K:
  B=[0]*(N+1)
  for i in range(N):
    l = max(i-A[i],0)
    r = min(i+A[i]+1,N)
    B[l] +=1
    B[r] -=1
  for i in range(N):
    A[i] = sum(B[0:i+1])
  p +=1        
  if min(A)==N:
    break
print(*A)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import numba

b_n, i_k = map(int, input().split())
lamps = np.array([int(x) for x in input().split()])
act = np.zeros(b_n, dtype=np.int64)

@numba.jit
def loop(n, k, lamps, act):
    one = np.ones(n, dtype=np.int64)
    init = lamps
    for i in range(k):
        act[:] = 0
        for i in range(n):
            if init[i] == 0:
                continue
            dmin = i - int(init[i])
            dmax = i + int(init[i])
            if dmin < 0:
                dmin = 0
            if dmax > n-1:
                dmax = n-1
            act[dmin:dmax+1] += 1
            act[i] -= 1
        init = act + one
    return init
result = loop(b_n, i_k, lamps, act)
ans = list(map(str,result.tolist()))
print(" ".join(ans))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, K = map(int, input().split())
A = list(map(int, input().split()))
foo = np.ones((42, N), dtype = "int64")
for k in range(len(A)):
    foo[0][k] = A[k]
if K <42:
    for q in range(K):
        unko = np.zeros(N, dtype = "int64")
        for k in range(N):
            if k + foo[q][k]+1 < N:
                unko[k + foo[q][k]+1] -=1
            unko[max(k - foo[q][k], 0)] +=1
        unchi = 0
        for k in range(N):
            unchi += unko[k]
            foo[q+1][k] = unchi
        #print(unko)
        #print(foo[q+1])
        count =0
        for l in range(N):
            if foo[q+1][l] < N:
                break
            else:
                count +=1
        
        if count == N:
            break
        
                        
        #print(foo)
    print(" ".join(map(str, foo[q+1])))

     
else:
    print((str(N)+" ")*(N-1)+str(N))

Submission status: Time Limit Exceeded

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

#print([0] *n)
import numpy as np

bn = np.zeros((42,n), dtype=int)

t= min(k, 45)


for k in range(t):

    for i in range(n):
        if k==0:
            for j in range(max(i - an[i], 0), min(n, i + an[i] + 1)):
                bn[k][j] += 1
        else:
            for j in range(max(i-bn[k-1][i],0), min(n, i+bn[k-1][i]+1)):
                bn[k][j] += 1


print(*bn[t-1])