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:
# -*- 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 > 39:
  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(map(int,input().split()))

def r(i,a):
    x1=i+1-a
    x2=i+2+a
    return [l for l in range(x1,x2) if(l>0)]

for k in range(K):
    B=[0]*N
    for i in range(N):
        for m in r(i,A[i]):
            n=m-1
            if(n<N):
                B[n]+=1
    A=B
print(' '.join(map(str, A)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

# = int(input())
N, K = map(int, input().split())
A = np.array(list(map(int, input().split())))
length = len(A)
# = [int(input()) for i in range(N)]
# = [list(map(int, input().split())) for i in range(N)]

if K >= N/2 + 1:
    L=[str(length) for a in range(N)]
    L=" ".join(L)
    print(L)
    exit()
else:
    for i in range(K):
        count = 0
        zero = np.array([0]*N)
        for j in range(N//2):
            if A[j] >= length-(j+1):
                zero += 1
            else:
                count += 1
                if j + A[j] + 1 >= length:
                    zero[j:] += 1
                else:
                    zero[j:A[j]+j+1] += 1
                if j - A[j] - 1 < 0:
                    zero[:j] += 1
                else:
                    zero[j-A[j]:j] += 1
        for j in range(N//2, N):
            if A[j] >= j:
                zero += 1
            else:
                count += 1
                if j + A[j] + 1 >= length:
                    zero[j:] += 1
                else:
                    zero[j:A[j]+j+1] += 1
                if j - A[j] - 1 < 0:
                    zero[:j] += 1
                else:
                    zero[j-A[j]:j] += 1
        if count == 0:
            break
        else:
            A = zero

    L=[str(a) for a 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(' ')))

maximized = [False] * N

for k in range(K):
    B = [0] * N

    # 全玉maxになったとき
    if all(maximized):
        break

    for i in range(N):
        # 強さはN超にはならない
        if A[i] == N:
            B[i] = A[i]
            maximized[i]= True
        else:
            # 照らせる範囲
            l = max(0, i - A[i])
            r = min(N - 1, i + A[i])

            for j in range(l, r + 1):
                B[j] += 1
    A = B

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

lamp = {}
for i in range(1, N+1):
    lamp[i] = A[i-1]

for k in range(K):
    lamp_next = defaultdict(lambda: 0)
    for i in range(1, N+1):
        l = i - lamp[i]
        if l < 1:
            l = 1
        r = i + lamp[i]
        if r > N:
            r = N
        for j in range(l, r+1):
            lamp_next[j] += 1
    lamp = lamp_next

ans = [lamp[i] for i in range(1, N+1)]
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    bn1=[0]*n
    bn2 = [0] * n
    s=0
    t=0
    for _ in range(k):
        for i in range(n):
            b1=max(i-a[i],0)
            b2=min(i+a[i],n-1)
            bn1[b1]+=1
            bn2[b2]+=1
        for i in range(n):
            s+=bn1[i]
            a[i]=s
        s=0
        for i in range(1,n):
            t+=bn2[i-1]
            a[i]-=t
        t=0
        bn1 = [0] * n
        bn2 = [0] * n
    c = [str(x) for x in a]
    L=" ".join(c)
    print(L)
resolve()

Submission status: Time Limit Exceeded

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

    dp = [[0]*n for _ in range(k+1)]
    for i in range(n):
        dp[0][i] = A[i]

    flag = False
    for i in range(1,k+1):
        pos = [0]*n
        neg = [0]*n

        for j in range(n):
            pwr = dp[i-1][j]
            pos[max(0,j-pwr)]+=1
            neg[min(n-1,j+pwr)]+=1

        ac_pos = 0
        ac_neg = 0
        for j in range(n):
            ac_pos += pos[j]
            ac_neg += neg[j]
            pos[j] = ac_pos
            neg[j] = ac_neg

        if pos[0]==n and neg[n-2]==0:
            flag = True
            break

        dp[i][0] = pos[0]
        for j in range(1,n):
            dp[i][j] = pos[j] - neg[j-1]

    
    if flag:
        for j in range(n-1):
            print(n, end=" ")  
        print(n)

    else:
        for j in range(n-1):
            print(dp[i][j], end=" ")
        print(dp[i][n-1])
main()

Submission status: Time Limit Exceeded

Solution code:
def get_range(index,power, N) :
    lower = index - power
    if (lower < 0) :
        lower = 0
    
    upper = index + power
    if (N-1 < upper) :
        upper = N-1
    
    return range(lower,upper+1)

def main() :

    N,K = map(int,input().split())
    current = [int(i) for i in input().split()]

    # TLEなんだろうなあ
    next_light = [0] * N
    for i in range(K) :
        for m in range(len(current)) :
            # print(m,get_range(m, current[m], N))
            for idx in get_range(m, current[m], N) :
                next_light[idx] += 1
        current = next_light[::]
        next_light = [0] * N

    out_str = ""
    for s in current :
        out_str += str(s) + " "
    print(out_str)
    # print(current)



main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
import copy

def input():
    return sys.stdin.readline()


def resolve():
    n, k = map(int, input().split())
    a_list = list(map(int, input().split()))


    next_list = [0] * n
    one_list = [0] * n

    for num in range(k):
        lamped_list = [0] * n
        # 照らされたランプ
        for i, strength in enumerate(a_list):
            l_range_minus = i - strength
            l_range_plus = i + strength
            if l_range_minus < 0:
                l_range_minus = 0
            if l_range_plus >= n:
                l_range_plus = n - 1

            if strength != 0:
                one_list[i] = 1

            for j in range(l_range_minus, l_range_plus+1):
                if i==j:
                    continue
                lamped_list[j] += 1
                one_list[j] = 1

            #print(lamped_list)

        # ここから最終的な光の強さを算出
        index = 0
        for i, j in zip(lamped_list, one_list):
            next_list[index] = i + j
            index += 1
        a_list = copy.deepcopy(next_list)

    print(*next_list)









if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

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


class RAQ():
    
    def __init__(self, size):
        """初期化"""
        self.size = size
        n = 2 ** ((size-1).bit_length())
        treesize = n * 2
        st = [0] * treesize
        self.st = st
        self.offset = len(st) // 2

    @classmethod
    def from_array(cls, a):
        st = cls(len(a))
        for i, x in enumerate(a):
            st.add(i, i+1, x)
        return st

    def _add_topdown(self, a, b, value, k=1, l=0, r=-1):
        """区間[a, b) に対する加算
        k: 着目しているノード (1-indexed)
        l: 探索区間 st[l, r) の左端 (0-indexed)
        r: 探索区間 st[l, r) の右端 (0-indexed)
        """
        if r == -1:
            r = self.offset
        if r <= a or b <= l:
            return
        if l == r - 1:
            self.st[k] += value
            return
        if a <= l and r <= b:
            self.st[k] += value
            return
        mid = (l + r) // 2
        self._add(a, b, value, k * 2, l, mid)
        self._add(a, b, value, k * 2 + 1, mid, r)

    def _add_bottomup(self, a, b, value):
        """区間[a, b) に対する加算
        """
        a += self.offset
        b += self.offset - 1
        while a < b:
            if a & 1:
                self.st[a] += value
                a += 1
            a >>= 1
            if not b & 1:
                self.st[b] += value
                b -= 1
            b >>= 1
        if a == b:
            self.st[a] += value

    def add(self, a, b, value):
        """区間[a, b) に対する加算"""
        if a > b:
            raise ValueError("a must be less than equal b.")
        return self._add_bottomup(a, b, value)

    def get(self, key):
        """値の取得"""
        offset = len(self.st) // 2
        k = offset + key
        v = self.st[k]
        k >>= 1
        while k > 0:
            v += self.st[k]
            k >>= 1
        return v


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):
    KL = N.bit_length() * 2 + 10
    if K > KL:
        print(*([N] * N))
        return
    raq = RAQ.from_array(A)
    a = [0 for i in range(N)]

    for k in range(min(K, KL)):
        for i in range(N):
            a[i] = raq.get(i)
            raq.add(i, i+1, -a[i])
        for i in range(N):
            l = max(0, i-a[i])
            r = min(N, i+1+a[i])
            raq.add(l, r, 1)
    print(*[raq.get(i) for i in range(N)])


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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N, K = map(int, input().split())
A = input().split()
AK = [[0 for j in range(N)] for i in range(2)]
for l in range(N):
  AK[0][l] = int(AK[0][l]) + int(A[l])

for m in range(1,K+1,1):
  for o in range(N):
    for x in range(N):
      if((o-AK[0][o]+0.5) < (x+1)) and ((x+1) < (o+AK[0][o]+1.5)):
        AK[1][x] = int(AK[1][x]) +1
  AK[0] = AK[1]
  AK[1] = [0] * N
print(*AK[0])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

num_of_lamps, num_of_operation = map(int, input().split())
intensitys = np.array(list(map(int, input().split())))

coordinates = np.arange(1, len(intensitys) + 1)

intensity_area_min = []
intensity_area_max = []

for o in range(num_of_operation):
    intensity_area_min = coordinates - intensitys - 0.5
    intensity_area_max = coordinates + intensitys + 0.5

    # i + 1が自分の座標
    for i in range(num_of_lamps):
        if intensitys[i] < num_of_lamps:
            # 自分より大きい（自分除く）の座標indexのminリストの中から自分の座標より小さいものを探してカウント
            min_count = np.count_nonzero(intensity_area_min[i+1:] <= i + 1)
            # 自分より小さい（自分除く）の座標indexのmaxリストの中から自分の座標より大きいものを探してカウント
            max_count = np.count_nonzero(intensity_area_max[:i] >= i + 1)

            # + 1は自分
            intensitys[i] = min_count + max_count + 1

    if np.all(intensitys >= num_of_lamps):
        break

out = ",".join(map(str, intensitys))
print(out.replace(',', ' '))

Submission status: Time Limit Exceeded

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

mod = 10**9+7

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

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

def calc_lux(a):
    res = [0 for _ in range(len(a))]
    cnt = 0
    for i in range(len(a)):
        light = a[i]
        if light==len(a) or (i <= light and n-1-i <= light):
            cnt += 1
            continue
        for j in range(max(0, i-light), min(n-1, i+light)+1, 1):
            res[j] += 1
    for i in range(len(res)):
        res[i] += cnt
    return res

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

    if a==lux:
        a = lux
        break

    # overwrite a
    a = lux
    # print(lux)

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

Submission status: Time Limit Exceeded

Solution code:
from copy import copy
def solve():
    ans = 0
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    for j in range(K):
        check = [0]*(N+1)
        for i in range(N):
            check[max(0,i-A[i])] += 1
            check[min(N,i+A[i]+1)] -= 1
        B = [check[0]]*N
        for i in range(1,N):
            B[i] = B[i-1]+check[i]
        A = copy(B)
        if A==[N]*N:
            break
    return A
print(*solve())

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())))
if K >= N:
    print(" ".join([str(N)]*N))
else:
    for _ in range(K):
        B = np.zeros(N, dtype=int)
        for i in range(N):
            B += np.hstack([np.zeros(max(i-A[i], 0), dtype=int), np.ones(min(A[i],i), dtype=int), [1], np.ones(min(A[i],N-i-1), dtype=int), np.zeros(max(N-i-1-A[i], 0), dtype=int)])
        if (A == B).all():
            break
        A = B

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

Submission status: Time Limit Exceeded

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

for k in range(K):
  llist = []
  B = [0] * N
  for i, a in enumerate(A):
    L = list(range(i-a+1, i+a+2))
    for l in L:
      if 1 <= l <= N:
        B[l-1] += 1
  A = B

print(*A)

Submission status: Time Limit Exceeded

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

N_count = A.count(N)
N_flag = [False for _ in range(N)]

next_A = [0 for _ in range(N+1)]

if K > 41:
    print(*[N for _ in range(N)])
    exit()

for count in range(K):
    for i in range(N+1): next_A[i] = 0

    for x,a in enumerate(A):
        if a == 0:
            next_A[x] += 1
            next_A[x+1] -= 1
        else:
            next_A[max(x-a,0)] += 1
            next_A[min(x+a+1,N)] -= 1

    for i in range(N):
        next_A[i+1] += next_A[i]

    A = next_A[:N]
    for x,a in enumerate(A):
        if a == N and not N_flag[x]:
            N_flag[x] = True
            N_count += 1
    if N_count == N:
        break
print(*A)

Submission status: Time Limit Exceeded

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

    def light_range(A):
        lighted = np.zeros(N, dtype=np.int64)
        for i, a in enumerate(A):
            lighted[max(0, i-a): min(N, i+a+1)] += 1
        return lighted
    

    def handle():
        nonlocal A
        lighted = light_range(A)
        A = lighted
        #print(f"lighted={lighted}")

    for _ in range(K):
        if min(A) == N:
            break
        handle()
    
    print(" ".join(map(str, A)))



if __name__ == '__main__':
    main()

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
  for i in range(N):
    count = 0
    for j in range(N):
      #print(A[j])
      if A[j]+1>abs(j-i):
        count +=1
    #print(["A"]+A)  
    B[i] = count
    #print(["A"]+A)
    #print([B])
  if min(B)==N:
    break
  A = B
  p +=1
print(*A)

Submission status: Time Limit Exceeded

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

import heapq  # heapqライブラリのimport
#heapq.heapify(a)  # リストを優先度付きキューへ
#heapq.heappop(a)  # 最小値の取り出し
    #heapq.heappush(a, -2)
import copy
for unko in range(k):

    denkyu=[]
    heapq.heapify(denkyu)
    cnt=0
    ans=[0]*n
    #print("start",a)
    for i,aa in  enumerate(a):
        if cnt==0:
            ans[i]+=1
            if aa>0:
                cnt+=1
                heapq.heappush(denkyu,i+aa+1)
        else:
            while 1:
                tmp=heapq.heappop(denkyu)
                if i<tmp:
                    heapq.heappush(denkyu, tmp)
                    break
                else:
                    cnt-=1
                if cnt==0:
                    break
            
            ans[i]+=cnt+1
            
            if aa>0:
                cnt+=1
                heapq.heappush(denkyu,i+aa+1)
        #print(aa,denkyu)
    #print(unko,ans,a)


    denkyu=[]
    heapq.heapify(denkyu)
    cnt=0
    for ii in  range(n):
        
        i=n-ii-1
        if cnt==0:
            if a[i]>0:
                cnt+=1
                heapq.heappush(denkyu,-1*(i-a[i]-1))
        else:
            while 1:
                tmp=heapq.heappop(denkyu)*(-1)
                if i>tmp:
                    heapq.heappush(denkyu, tmp*(-1))
                    break
                else:
                    cnt-=1
                if cnt==0:
                    break
  
            ans[i]+=cnt
            if a[i]>0:
                cnt+=1
                heapq.heappush(denkyu,(i-a[i]-1)*(-1))
        #print("migi",a[i],denkyu)

    a = copy.deepcopy(ans)
    if min(a)==n:
        break
    #print(unko,a)


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

Submission status: Time Limit Exceeded

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

for j in range(k):
    b = [0]*n
    count = 0
    for i in range(n):
        if i-a[i]>0:
            start = i-a[i]
        else:
            start = 0
        if i+a[i]+1>n:
            end = n
        else:
            end = i+a[i]+1
    
        for l in range(start,end):
             b[l] += 1
    if a == b:
        break
    a = b 

print(*a)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import copy

#f = open('./input_C.txt')
#N,K = map(int, f.readline().split())
#A0 = list(map(int, f.readline().split()))

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

B = A0
for i in range(K):
    A = copy.deepcopy(B)
    B = np.zeros(N)
    B = B.astype("int32")
    for j in range(N):
        B[max(0,j-A[j]):min(N,j+A[j]+1)]+=1
#        print(B)

anslist = B.tolist()
ans = ""
for ans_i in anslist:
    ans+=str(ans_i)+" "
ans = ans[:-1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = input().split()
i_list = list(range(len(a)))
a = [int(a[i]) for i in i_list]
c = [0]*n
d = [0]*n

for i in range(n):
    dum = [i]*n
    d[i] = list(map(lambda y,z: abs(y-z), i_list, dum))

for m in range(k):
    for i in range(n):
        dum = [i]*n
        b = list(map(lambda x,y: x-y, a, d[i]))
        c[i] = sum(1 for x in b if x >=0)
    a = []
    a += c
a = [str(aa) for aa in a]
print(' '.join(a))

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
T=list(map(int,input().split()))
if K==0:
    print(T)
    exit()

if N<=K:
    L=[N]*N
    print(L)
#S = [[0 for j in range(3)] for i in range(2)]　2行3列の場合
S = [[0 for j in range(N)] for i in range(K+1)]

for i in range(N):
    S[0][i]=T[i]

#print(S)
for i in range(K):
    for j in range(N):
        d=S[i][j]
        #print(d)
        for k in range(max(j-d,0),min(j+d+1,N)):
            #print(k,max(j-d,0),min(j+d+1,K+1))
            S[i+1][k]+=1


#print(S[K])

Z=[str(a) for a in S[K]]
Z=" ".join(Z)
print(Z)

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 > 40:
  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(map(int,input().split()))
ans1=[]
ans2=[]
ans1+=a
ans2+=a
for i in range(min(k,32)):
  now=0
  ans2=[]
  ans2+=ans1
  kans=[0]*n
  for j in range(n):
    if j+ans2[j]+1<=n-1:
      kans[j+ans2[j]+1]-=1
    now+=1+kans[j]
    #基本kans[j]は0だが終点は-1
    ans1[j]=now
  now=0
  kans=[0]*n
  for j in range(1,n+1):
    if n-j-ans2[n-j]>=0:
      kans[n-j-ans2[n-j]-1]-=1
    now+=1+kans[n-j]
    #基本kans[j]は0だが終点は-1
    ans1[n-j]+=now-1
print(*ans1)

Submission status: Time Limit Exceeded

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

A_list = [0]+list(map(int, input().split()))
A_np=np.array(A_list)
#print(A_np)

for j in range(K):
  new_A_np=np.array([0]*(N+1))
  for i in range(1,N+1):
    tmp_np=np.array([0]*(N+1))
    #print(A_np)
    mi=i-A_np[i]
    ma=i+A_np[i]
    if mi<0:
      mi=0
    if ma>N:
      ma=N
    #print(mi,ma)
    tmp_np[mi:ma+1]=1
    #print(tmp_np)
    new_A_np+=tmp_np
  #print(new_A_np)
  A_np=new_A_np
  if sum(A_np[1:N+1])==N*N:
    break
    
for i in range(1,N+1):
  print(A_np[i],end=" ")

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    for _ in range(K):
        a = [0] * N
        t = 0
        for i in range(N):
            t += a[i] + 1
            if i + A[i] + 1< N:
                a[i + A[i] + 1] -= 1
            a[i] = t
        t = 0
        b = [0] * N
        for i in reversed(range(N)):
            t += b[i]
            b[i] = t
            t += 1
            if i - A[i] - 1 >= 0:
                b[i - A[i] - 1] -= 1
            A[i] = a[i] + b[i]
    return A

print(*main())

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
a=input().split()
A=[int(b) for b in a]
suuji=0
def pluss(n):
    return n+1
for k in range(K):
    a = [1 for _ in range(N)]
    for n in range(N):
        number=A[n]
        plus=n+number
        minus=n-number
        if minus<0:
            minus=0
        a[minus:n]=map(pluss,a[minus:n])
        a[n+1:plus+1]=map(pluss,a[n+1:plus+1])
    A=a
    if sum(A)==N**2:
        break
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**2:
        break
a=[str(s) for s in a]
a=" ".join(a)
print(a)

Submission status: Time Limit Exceeded

Solution code:
import copy
import math

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

for i in range(k):  # 0～k-1
    next_a = [0] * n
    for j in range(len(a)): # 0～n-1個
        strength = a[j] + 0.5
        #print("j-strength = {}".format(j-strength))
        min_index = math.ceil(j-strength)
        if min_index <= 0:
            min_index = 0

        max_index = math.floor(j+strength)
        if max_index >= n:
            max_index = n-1

        #print("{}, {}".format(min_index, max_index))
        for l in range(min_index, max_index+1):
            #print("l = {}".format(l))
            next_a[l] += 1
    a = copy.copy(next_a)

b = [str(a) for a in a]
ret = ' '.join(b)
print(ret)