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

n, k = map(int, input().split())
a = list(map(int, input().split())) + [0]

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

print(*a[:-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import accumulate

input = sys.stdin.readline


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

    for _ in range(min(41, K)):
        A_cumsum = [0] * N
        for i in range(N):
            a = i - A[i]
            b = i + A[i] + 1
            if a < 0:
                A_cumsum[0] += 1
            else:
                A_cumsum[a] += 1
            if N - 1 < b:
                pass
            else:
                A_cumsum[b] -= 1
        A = list(accumulate(A_cumsum))

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy

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

if K >= N:
  print(*([N]*N))
  exit()
  
K=min(100,K)

for k in range(K):
  B=[0]*N
  for i in range(N):
    a,b=max(0,i-A[i]),min(N,i+A[i]+1)
    B = [B[j]+1 if a<=j and j<b else B[j] for j in range(N)]
  A = deepcopy(B)
  
print(*A)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy

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

if K >= N:
  print(*([N]*N))
  exit()

for k in range(K):
  B=[0]*N
  for i in range(N):
    a,b=max(0,i-A[i]),min(N,i+A[i]+1)
    B = [B[j]+1 if a<=j and j<b else B[j] for j in range(N)]
  A = deepcopy(B)
  
print(*A)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split(" "))
ar = list(map(int,input().split(" ")))
br = [0 for i in range(n)]
for i in range(k):
    for j in range(n):
        for k in range(max(0,j-ar[j]),min(n-1,j+ar[j])+1):
            br[k] += 1
    ar = br.copy()
    br = [0 for l in range(n)]
for i in range(n-1):
    print(ar[i],end=" ")
print(ar[n-1])

Submission status: Time Limit Exceeded

Solution code:
def main():
    N_ko, K_kai = map(int, input().split())
    init_light = list(map(int, input().split()))


    for k in range(min(42,K_kai)):
        light_list = [0 for i in range(N_ko)]

        for i in range(N_ko):
            left = max(0, i - init_light[i])
            right = min(N_ko - 1, i + init_light[i])
            
            light_list[left] += 1

            if (right + 1 < N_ko):
                light_list[right + 1] -= 1
            
        for i in range(1, N_ko):
            light_list[i] += light_list[i - 1]
        
        init_light = light_list

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N_ko, K_kai = map(int, input().split())
    init_light = list(map(int, input().split()))


    for k in range(K_kai):
        light_list = [0 for i in range(N_ko)]

        for i in range(N_ko):
            left = max(0, i - init_light[i])
            right = min(N_ko - 1, i + init_light[i])
            
            light_list[left] += 1

            if (right + 1 < N_ko):
                light_list[right + 1] -= 1
            
        for i in range(1, N_ko):
            light_list[i] += light_list[i - 1]
        
        init_light = light_list

        judge = all([init_light[i] == N_ko for i in range(N_ko)])
        
        
        if (judge):
            break   
    
    print(' '.join(map(str,light_list)))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
class Imos:
    def __init__(self, n):
        self.A = [0]*(n+1)
        self.n = n

    def __call__(self):
        
        dist = list(accumulate(self.A))[:self.n]
        self.A = [0] * (self.n+1)
        return dist

    def query(self, l, r):
        self.A[l] += 1
        self.A[r] -= 1

n, k, *A = map(int, open(0).read().split())
imos = Imos(n)
for _ in range(min(100, k)):
    for i in range(n):
        imos.query(max(0, i-A[i]), min(i+A[i]+1, n))
    A = imos()
print(*A)

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random,resource

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,k = LI()
    a = LI()

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

        if r[0] == n and r[n] == -n:
            a = [n] * n
            break

        t = 0
        for i in range(n):
            t += r[i]
            a[i] = t

    return JA(a, " ")


print(main())

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 for _ in range(N)]
    if all(b == N for b in B):
        break
    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.copy()
   
for b in B:
    print(b, end=" ")

Submission status: Time Limit Exceeded

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

b = [i for i in A]
for _ in range(K):
    buf = [0]*(N+1)
    for i, j in enumerate(b):
        buf[max(i-j, 0)] += 1
        buf[min(i+j+1, N)] -= 1
    for i in range(1, N+1):
        buf[i] += buf[i-1]
    b = [buf[i] for i in range(N)]

print(*b)

Submission status: Time Limit Exceeded

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

ans = [0] * (N+1)

for j in range(K):
    ans = [0] * (N+1)
    for i in range(N):
        L = max(0, i-A[i])
        R = min(N, i+A[i]+1)
        ans[L] += 1
        ans[R] -= 1
    for i in range(1, N+1):
        ans[i] += ans[i-1]
    issame = True
    for i in range(N):
        if i != 0:
            if ans[i-1] != N or ans[i-1] != ans[i]:
                issame = False
        A[i] = ans[i]
    if issame:
        break

for i in range(N):
    print(ans[i], end=' ')

Submission status: Time Limit Exceeded

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

ans = [0] * (N+1)

for j in range(K):
    ans = [0] * (N+1)
    for i in range(N):
        L = max(0, i-A[i])
        R = min(N, i+A[i]+1)
        ans[L] += 1
        ans[R] -= 1
    issame = True
    for i in range(1, N+1):
        ans[i] += ans[i-1]
        if ans[i] != ans[i-1]:
            issame = False
    if issame:
        break
    for i in range(N):
        A[i] = ans[i]

for i in range(N):
    print(ans[i], end=' ')

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

from collections import defaultdict
from heapq import heappush, heappop
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")


def debug(*x):
    print(*x, file=sys.stderr)


def solve(N, K, AS):
    for _i in range(K):
        d = [0] * (N + 1)
        for i in range(N):
            x = AS[i]
            d[max(i - x, 0)] += 1
            d[min(i + x + 1, N)] -= 1
        cur = 0
        ret = [0] * N
        for i in range(N):
            cur += d[i]
            ret[i] = cur
        AS = ret

    return ret


def main():
    N, K = map(int, input().split())
    AS = list(map(int, input().split()))

    print(*solve(N, K, AS))


T1 = """
5 1
1 0 0 1 0
"""


def test_T1():
    """
    >>> as_input(T1)
    >>> main()
    1 2 2 1 2
    """


T2 = """
5 2
1 0 0 1 0
"""


def test_T2():
    """
    >>> as_input(T2)
    >>> main()
    3 3 4 4 3
    """


def _test():
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())

    def input():
        return bytes(f.readline(), "ascii")

    def read():
        return bytes(f.read(), "ascii")


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        print("testing")
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Time Limit Exceeded

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

def imos(n,a):
  imos_l=[0]*n
  for i in range(n):
    l=max(i-a[i],0)
    r=min(i+a[i],n-1)
    imos_l[l]+=1
    if (r+1)!=n:
      imos_l[r+1]-=1

  b=[0]
  for i in range(1,n+1):
    b.append(imos_l[i-1]+b[i-1])
  return b[1:]

for i in range(k):
  na=imos(n,a)
  if na==a:
    break
  a=na

print(*a)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int,input().split())
A = list(map(int,input().split()))
for k in range(K):
    C=[0]*N
    for i in range(1,N+1):
        a=max(1,i-A[i-1])
        b=min(N,i+A[i-1])
        for j in range(a-1,b):
            C[j]=C[j]+1
    A=C
for s in A:
  print(s, 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=[]
    for i in range(N):
        c=0
        for j in range(N):
            if -A[j]<=j-i<=A[j]:
               c=c+1
        B.append(c)
    A=B
for s in A:
  print(s, 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=[]
    for i in range(N):
        c=0
        for j in range(N):
            if abs(j-i)<=A[j]+0.5:
               c=c+1
        B.append(c)
    A=B
for s in A:
  print(s, end =" ")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    n,k=map(int,input().split())
    A=list(map(int,input().split()))+[0]

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

        for j in range(n):
            val=A[j]
            B[max(0,j-val)]+=1
            B[min(n,j+val+1)]-=1
        
        for k in range(n):
            B[k+1]+=B[k]
        A=B

        if A==[n]*(n+1):
            break
    
    

    print(*A[:-1])    
    
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    n,k=map(int,input().split())
    A=list(map(int,input().split()))+[0]

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

        for j in range(n):
            val=A[j]
            B[max(0,j-val)]+=1
            B[min(n,j+val+1)]-=1
        
        for k in range(n):
            B[k+1]+=B[k]
        A=B

        if A==[n]*n:
            break
    
    

    print(*A[:-1])    
    
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    n,k=map(int,input().split())
    A=list(map(int,input().split()))+[0]

    from itertools import accumulate

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

        for j in range(n):
            val=A[j]
            #if val==0: continue
            B[max(0,j-val)]+=1
            B[min(n,j+val+1)]-=1
        
        for k in range(n):
            B[k+1]+=B[k]
        A=B

        if A==[n]*n:
            break
    
    

    print(*A[:-1])    
    
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    n,k=map(int,input().split())
    A=list(map(int,input().split()))+[0]

    from itertools import accumulate

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

        for j in range(n):
            val=A[j]
            #if val==0: continue
            B[max(0,j-val)]+=1
            B[min(n,j+val+1)]-=1
        A=list([0]+list(accumulate(B)))[1:]

        if A==[n]*n:
            break
    
    

    print(*A[:-1])    
    
resolve()

Submission status: Time Limit Exceeded

Solution code:
from copy import copy, deepcopy # pythonのみ．copyは1次元，deepcopyは多次元．
# from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
# from functools import reduce
# from heapq import heapify, heappop, heappush
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    n,k=map(int,input().split())
    A=list(map(int,input().split()))+[0]

    m=n
    log = 0
    while m >= 2:
        m = m // 2
        log += 1
    from itertools import accumulate

    for i in range(min(k,n*2*log+1)):
        B=[0]*(n+1)

        for j in range(n):
            val=A[j]
            #if val==0: continue
            B[max(0,j-val)]+=1
            B[min(n,j+val+1)]-=1
        A=list([0]+list(accumulate(B)))[1:]
    
    

    print(*A[:-1])    
    
    
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import accumulate
sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    for _ in range(60 if k >= 60 else k):
        B = [0] * (n + 1)
        for i in range(n):
            left = max(0, i - A[i])
            right = min(n, i + A[i] + 1)
            B[left] += 1
            B[right] -= 1

        B = list(accumulate(B))
        A = B
    print(*B[:n])


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
n, k = map(int, input().split())
A = list(map(int, input().split()))
C = [n for i in range(n)]
for r in range(k):
    B = [0 for i in range(n+1)]
    for i in range(n):    
        d_min = max(0, i - A[i])
        d_max = min(n, i + A[i] + 1)
        B[d_min] += 1
        B[d_max] -= 1
        # print(d_min, d_max, B)
    t = 0
    flag = True
    for i in range(n):
        t += B[i]
        #if A[i] != t:
        #    flag = False
        A[i] = t
    #if flag:
    #    break
    if A == C:
        break
    # print(A, B)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
n, k = map(int, input().split())
A = list(map(int, input().split()))
 
for r in range(k):
    B = [0 for i in range(n+1)]
    for i in range(n):    
        d_min = max(0, i - A[i])
        d_max = min(n, i + A[i] + 1)
        B[d_min] += 1
        B[d_max] -= 1
        # print(d_min, d_max, B)
    t = 0
    flag = True
    for i in range(n):
        t += B[i]
        if A[i] != t:
            flag = False
        A[i] = t
    if flag:
        break
    # print(A, B)

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

Submission status: Time Limit Exceeded

Solution code:
import math
N ,K = map(int,input().split())
A = list(map(int, input().split()))
sum = [0] * N

for i in range(min(41,K)):
    for i in range(N):
        lo = max(0,i - A[i])
        up = min(N - 1,i+A[i])
        sum[lo] += 1
        if up + 1 < N:
            sum[up + 1] -= 1

    for i in range(1,N):
        sum[i] += sum[i-1]

    for i in range(N):
        A[i] = sum[i]
        sum[i] = 0

S = ""
for i in range(N):
    S += str(A[i])
    if i != N - 1 :
        S += " "

print(S)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math
n, k= [int(k) for k in input().split()]
a = np.array([int(k) for k in input().split()])
for _ in range(k):
    b = np.zeros(n,dtype=int)
    for i in range(n):
        d = a[i]
        x = i + 1
        l = math.ceil(x - d - 0.5)
        r = int(x + d + 0.5)
        for j in range(max(1, l), min(n + 1, r + 1)):
            b[j - 1] += 1
    a = b
print(" ".join([str(k) for k in a]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


### 解答
N, K = map(int, input().split())
A = np.asarray(list(map(int, input().split())), dtype=np.int)

#B = [0]*N                                 # 記録用のリスト

def imos(A):      
  B = np.zeros(N)
  for i in range(N):                      # 各電球によって照らされる範囲を考える
    start = max(0, i-A[i])                # 始点のインデックスは0かi-A[i]
    end = min(N, i+A[i]+1)
    #print(start, end)                # 終点のインデックスはNかi+A[i]+1
    B[start] += 1                         # 始点に+1を記録する
    if end <= N - 1:
      B[end] -= 1                         # 終点に電球が存在する場合は-1を記録する
  A = np.cumsum(B).astype(np.int)
  return A




for k in range(K):                        # 以降の操作をK回繰り返す
  A = imos(A)
  if np.min(A) == N:
    break
print(*A)                                 # リストAの中身を順に表示

Submission status: Time Limit Exceeded

Solution code:
from numba import jit


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

#B = [0]*N                                 # 記録用のリスト

@jit
def imos(A):      
  B = [0 for _ in range(N)] 
  for i in range(N):                      # 各電球によって照らされる範囲を考える
    start = max(0, i-A[i])                # 始点のインデックスは0かi-A[i]
    end = min(N, i+A[i]+1)                # 終点のインデックスはNかi+A[i]+1
    B[start] += 1                         # 始点に+1を記録する
    if end <= N - 1:
      B[end] -= 1                         # 終点に電球が存在する場合は-1を記録する
  bmin = B[0] 
  for i in range(1, N):                   # 累積和の計算
    B[i] = B[i-1] + B[i]
    bmin = min(B[i], bmin)
  A = B                                   # AをBで更新してつぎのループへ 
  if bmin == N:                        # すべての電球がN個の電球に照らされるタイミングでbreakする
    return A, True
  return A, False



for k in range(K):                        # 以降の操作をK回繰り返す
  A, saturated = imos(A)
  if saturated:
    break
print(*A)                                 # リストAの中身を順に表示

Submission status: Time Limit Exceeded

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

#B = [0]*N                                 # 記録用のリスト

for k in range(K):                        # 以降の操作をK回繰り返す
  B = [0 for _ in range(N)] 
  for i in range(N):                      # 各電球によって照らされる範囲を考える
    start = max(0, i-A[i])                # 始点のインデックスは0かi-A[i]
    end = min(N, i+A[i]+1)                # 終点のインデックスはNかi+A[i]+1
    B[start] += 1                         # 始点に+1を記録する
    if end <= N - 1:
      B[end] -= 1                         # 終点に電球が存在する場合は-1を記録する
  bmin = B[0] 
  for i in range(1, N):                   # 累積和の計算
    B[i] = B[i-1] + B[i]
    bmin = min(B[i], bmin)
  A = B                                   # AをBで更新してつぎのループへ 
  if bmin == N:                        # すべての電球がN個の電球に照らされるタイミングでbreakする
    break

print(*A)                                 # リストAの中身を順に表示

Submission status: Time Limit Exceeded

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

#B = [0]*N                                 # 記録用のリスト

for k in range(K):                        # 以降の操作をK回繰り返す
  B = [0]*N 
  for i in range(N):                      # 各電球によって照らされる範囲を考える
    start = max(0, i-A[i])                # 始点のインデックスは0かi-A[i]
    end = min(N, i+A[i]+1)                # 終点のインデックスはNかi+A[i]+1
    B[start] += 1                         # 始点に+1を記録する
    if end <= N - 1:
      B[end] -= 1                         # 終点に電球が存在する場合は-1を記録する
  bmin = B[0] 
  for i in range(1, N):                   # 累積和の計算
    B[i] = B[i-1] + B[i]
    bmin = min(B[i], bmin)
  A = B                                   # AをBで更新してつぎのループへ 
  if bmin == N:                        # すべての電球がN個の電球に照らされるタイミングでbreakする
    break

print(*A)                                 # リストAの中身を順に表示

Submission status: Time Limit Exceeded

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

#B = [0]*N                                 # 記録用のリスト

for k in range(K):                        # 以降の操作をK回繰り返す
  B = [0]*N 
  for i in range(N):                      # 各電球によって照らされる範囲を考える
    start = max(0, i-A[i])                # 始点のインデックスは0かi-A[i]
    end = min(N, i+A[i]+1)                # 終点のインデックスはNかi+A[i]+1
    B[start] += 1                         # 始点に+1を記録する
    if end <= N - 1:
      B[end] -= 1                         # 終点に電球が存在する場合は-1を記録する
  bsum = B[0]
  for i in range(1, N):                   # 累積和の計算
    B[i] = B[i-1] + B[i]
    bsum += B[i]

  
  A = B                                   # AをBで更新してつぎのループへ
  
  if bsum == N**2:                        # すべての電球がN個の電球に照らされるタイミングでbreakする
    break

print(*A)                                 # リストAの中身を順に表示

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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): 
    start = max(0, i-A[i])
    end = min(N, i+A[i]+1)
    B[start] += 1
    if end <= N - 1:
      B[end] -= 1
  B = np.cumsum(B)
  #for i in range(1, N):
    #B[i] = B[i-1] + B[i] 
  A = B
  if min(A) == N:
    break
 
print(*A)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,k = inpl()
now = inpl()
now.append(0)
for _ in range(k):
    pre = now[::]
    now = [0] * (n+1)
    for j in range(n):
        a = max(0,j-pre[j])
        b = min(n,j+pre[j]+1)
        now[a] += 1
        now[b] -= 1
    x = 0
    for j in range(n):
        x += now[j]
        now[j] = x
    if min(now) == n:
        break
print(*now[:n])

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,k = inpl()
now = inpl() + [0]
for _ in range(k):
    pre = now[::]
    now = [0] * (n+1)
    for j in range(n):
        a = max(0,j-pre[j])
        b = min(n,j+pre[j]+1)
        now[a] += 1
        now[b] -= 1
    x = 0
    mi = 0
    for j in range(n):
        x += now[j]
        now[j] = x
        mi = min(x,mi)
    if mi == n:
        break
print(*now[:n])

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,k = inpl()
now = inpl() + [0]
for _ in range(k):
    pre = now[::]
    now = [0] * (n+1)
    for j in range(n):
        a = max(0,j-pre[j])
        b = min(n,j+pre[j]+1)
        now[a] += 1
        now[b] -= 1
    x = 0
    for j in range(n):
        x += now[j]
        now[j] = x
    if min(now) == n:
        break
print(*now[:n])

Submission status: Time Limit Exceeded

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

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 imos(a):
    tmp = np.zeros(n+1, dtype=np.int64)
    for i in range(n):
        tmp[max(0, i - a[i])] += 1
        tmp[min(i + a[i] + 1, n)] -= 1
    tmp = np.cumsum(tmp)
    return tmp[:n]
 
for j in range(1, k+1):
    a = imos(a)
print(*a)

Submission status: Time Limit Exceeded

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

fin = min(A) == N
for j in range(K):
    if fin:
        break
    T = [0] * (N + 1)
    for i in range(N):
        T[max(i - A[i], 0)] += 1
        T[min(i + A[i] + 1, N)] -= 1
    A[0] = T[0]
    fin = A[0] == N
    for i in range(1, N):
        A[i] = A[i - 1] + T[i]
        if A[i] < N:
            fin = False
print(' '.join(list(map(str, A))))

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

n, k = map(int, input().split())
a = list(map(int, input().split()))
for _ in range(k):
   b = [0] * n
   for i in range(n):
      b[max(0, i-a[i])] += 1
      tmp = i + a[i] + 1
      if tmp < n:
         b[tmp] -= 1
   a = list(accumulate(b))
   if a == [n] * n:
      break

print(*a)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
import sys
N, K = map(int, input().split())
An = list(map(int, input().split()))

for cnt in range(K):
    tmp = [0]*(N+1)
    for i in range(N):
        power = An[i]
        left = max(0, i-power)
        right = min(N, i+power+1)
        tmp[left] += 1
        tmp[right] -= 1
    An = list(accumulate(tmp))[:-1]
    if cnt > 40:
        An = [N]*N
        print(*An)
        sys.exit()
print(*An)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
N, K = map(int, input().split())
An = list(map(int, input().split()))

for cnt in range(K):
    tmp = [0]*(N+1)
    for i in range(N):
        power = An[i]
        left = max(0, i-power)
        right = min(N, i+power+1)
        tmp[left] += 1
        tmp[right] -= 1
    An = list(accumulate(tmp))[:-1]
    if cnt > 40:
        An = [N]*N
        break
print(*An)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
N, K = map(int, input().split())
An = list(map(int, input().split()))

for cnt in range(K):
    tmp = [0]*(N+1)
    for i in range(N):
        power = An[i]
        left = max(0, i-power)
        right = min(N, i+power+1)
        tmp[left] += 1
        tmp[right] -= 1
    An = list(accumulate(tmp))[:-1]
    if cnt > 40:
        An = [N]*N
print(*An)

Submission status: Time Limit Exceeded

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

def simulation(N, K, A_list):
    for k in range(min(K, 42)):
        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()

Submission status: Time Limit Exceeded

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

def simulation(N, K, A_list):
    for k in range(min(K, 42)):
        #next_A_list = [0 for i in range(N)]
        imos_list = [0 for i in range(N)]
        for i in range(N):
            d = A_list[i]
            imos_list[max(i-d, 0)] += 1
            if i+d+1 <= N-1:
                imos_list[i+d+1] -= 1
            #for j in range(i-d, i+d+1):
            #    if j >= 0 and j <= N-1:
            #        next_A_list[j] += 1
        for i in range(1, N):
            imos_list[i] += imos_list[i-1]
        A_list = imos_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()