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:
N, K = map(int, input().split())
A = list(map(int, input().split()))
for k in range(K):
    B = [0] * N
    for n in range(N):
        l = max(0, n- A[n])
        r = min(N-1, n+A[n])
        B[l] += 1
        if r +1 < N:
            B[r+1] -= 1
    #print(B)
    for i in range(N-1):
        B[i+1] += B[i]
    #print(B)
    if sum(A) == N**2:
        break
    else:
        A = B
ans = ''
for a in A:
    ans += str(a) + ' '
print(ans)

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 n in range(N):
        l = max(0, n- A[n])
        r = min(N-1, n+A[n])
        B[l] += 1
        if r +1 < N:
            B[r+1] -= 1
    #print(B)
    for i in range(N-1):
        B[i+1] += B[i]
    #print(B)
    A = B[:]
    if sum(A) == N**2:
        break
ans = ''
for a in A:
    ans += str(a) + ' '
print(ans)

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 n in range(N):
        l = max(0, n- A[n])
        r = min(N-1, n+A[n])
        B[l] += 1
        if r +1 < N:
            B[r+1] -= 1
    #print(B)
    for i in range(N-1):
        B[i+1] += B[i]
    #print(B)
    if sum(A) == N**2:
        break
    else:
        A = B
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 n in range(N):
        l = max(0, n- A[n])
        r = min(N-1, n+A[n])
        B[l] += 1
        if r +1 < N:
            B[r+1] -= 1
    #print(B)
    for i in range(N-1):
        B[i+1] += B[i]
    #print(B)
    if sum(A) == N**2:
        break
    else:
        A = B[:]
ans = ''
for a in A:
    ans += str(a) + ' '
print(ans)

Submission status: Time Limit Exceeded

Solution code:
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())


def main():
    import numpy as np
    N,K = mis()
    A = np.array(lmis())
    l = np.zeros(N+1, dtype=np.int64)
    for _ in range(K):
        l[:] = 0
        for i in range(N):
            a = A[i]
            l[max(0, i-a)] += 1
            l[min(N, i+a+1)] -= 1
        A = l.cumsum()[:-1]
        if np.all(A==N):
            break
    print(*A)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain, accumulate
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    N,K = mis()
    A = lmis()
    l = [0]*(N+1)
    for _ in range(min(K, N)):
        for i in range(len(l)):
            l[i] = 0
        for i in range(N):
            a = A[i]
            l[max(0, i-a)] += 1
            l[min(N, i+a+1)] -= 1
        tmp = 0
        for i in range(N):
            tmp += l[i]
            A[i] = tmp
    print(*A)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain, accumulate
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    import numpy as np
    N,K = mis()
    A = np.array(lmis())
    l = np.zeros(N+1, dtype=np.int64)
    for _ in range(K):
        l[:] = 0
        for i in range(N):
            a = A[i]
            l[max(0, i-a)] += 1
            l[min(N, i+a+1)] -= 1
        A = l.cumsum()
        if np.all(A==N):
            break
    print(*A[:-1])

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain, accumulate
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    N,K = mis()
    A = lmis()
    for _ in range(K):
        l = [0]*(N+1)
        for i in range(N):
            a = A[i]
            l[max(0, i-a)] += 1
            l[min(N, i+a+1)] -= 1
        A = list(accumulate(l))[:-1]
        if all(a==N for a in A):
            break
    print(*A)

main()

Submission status: Time Limit Exceeded

Solution code:
#coding; utf-8
import copy
N, k = map(int,input().split())
A = list(map(int,input().split()))
B = [0] * N
A = [0] + A
#B = copy.copy(A)
for j in range(k):
    #print(A)
    n_light = [0] * (N+1)
    for i in range(N):
        d = A[i+1]
        l = i+1-d
        r = i+1+d
        #print(l, r)
        n_light[max(l, 1)] += 1
        if r+1 <= N:# and l != r:
            n_light[r+1] -= 1
        #print(n_light)
    #print(n_light)
    for i in range(1,N):
        n_light[i+1] += n_light[i]
    n_str = [str(i) for i in n_light]
    A = n_light 
print(' '.join(n_str[1:]))

Submission status: Time Limit Exceeded

Solution code:
import sys
import  math
import fractions
from collections import defaultdict
import numpy as np
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

N,K=nm()
A=nl()

imos_l=[0]*(N+1)

for i in range(K):    
    imos_l=[0]*(N+1)
    for j in range(len(A)): 
        imos_l[max(j-A[j],0)]+=1
        imos_l[min(j+A[j]+1,N)]-=1
    for j in range(len(imos_l)-1):
        imos_l[j+1]=imos_l[j]+imos_l[j+1]
    for j in range(len(A)):
        A[j]=imos_l[j]
    flag=True
    for j in range(len(A)):
        if(A[j]<N):
            flag=False
    if(flag):
        print(*A)
        sys.exit(0)

print(*A)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def main():
    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):
            a = A[j]
            b[max(j-a, 0)] += 1
            b[min(j+a+1, N)] -= 1
        for k in range(1,N+1):
            b[k] += b[k-1]
        b = b[:N]
        if b == A:
            break
        else:
            A = b
    print(*A)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def main():
    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):
            a = A[j]
            b[max(j-a, 0)] += 1
            b[min(j+a+1, N)] -= 1
        for k in range(1,N+1):
            b[k] += b[k-1]
        if b == A:
            break
        else:
            A = b[:N]
    print(*A)

if __name__ == '__main__':
    main()

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
    for i in range(0,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,1):
        b[i]+=b[i-1]
    if a==b:
        break
    a=b

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

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
light=list(map(int,input().split()))
for k in range(K):
  imo=[0]*(N+1)
  for i in range(N):
    if i-light[i]>0:
      l=i-light[i]
    else:
      l=0
    if i+light[i]<N-1:
      r=i+light[i]+1
    else:
      r=N
    imo[l]+=1
    imo[r]-=1
  for i in range(1,N):
    imo[i]+=imo[i-1]
  if light==imo:
    break
  else:
    light=imo[:]
print(*light[:-1])

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
import numpy as np

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

for q in range(min(42,k)):
  b = [0]*(n+1)
  for i in range(n):
    l = max(0, i-a[i])
    r = min(i+a[i]+1, n)
    b[l] += 1
    if r <= n-1: b[r] -= 1
  
  a = list(accumulate(b))
  a = a[:-1]
   
  if np.all(a == n):
    break

print(*a)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
input = sys.stdin.readline
n, k = map(int, input().split())
a = list(map(int, input().split()))

for q in range(k):
  b = [0]*(n+1)
  for i in range(n):
    l = max(0, i-a[i])
    r = min(i+a[i]+1, n)
    b[l] += 1
    if r <= n-1: b[r] -= 1
  
  B = np.array(b)
  a = B.cumsum()[:-1]
  
  """[0] = b[0]
  for j in range(n-1):
    a[j+1] = a[j] + b[j+1]"""
  
  if np.all(a == n):
    break

print(*a)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
input = sys.stdin.readline
n, k = map(int, input().split())
a = list(map(int, input().split()))

for q in range(k):
  b = [0]*(n+1)
  for i in range(n):
    l = max(0, i-a[i])
    r = min(i+a[i]+1, n)
    b[l] += 1
    if r <= n-1: b[r] -= 1
      
  a[0] = b[0]
  for j in range(n-1):
    a[j+1] = a[j] + b[j+1]
  if np.all(a == n):
    break

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

if k > n-1:
  list1 = [n]*n
  a = list1

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

print(*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 q in range(k):
  b = [0]*(n+1)
  for i in range(n):
    l = max(0, i-a[i])
    r = min(i+a[i]+1, n)
    b[l] += 1
    if r <= n-1: b[r] -= 1
      
  a[0] = b[0]
  for j in range(n-1):
    a[j+1] = a[j] + b[j+1]

print(*a)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
As = list(map(int, input().split()))
for i in range(K):
  if min(As) == N:
    break
  dBs = [0]*(N+1)
  for i in range(N):
    A = As[i]
    dBs[max(0, i-A)] += 1
    dBs[min(N, i+A+1)] -= 1
  #print(dBs)
  Bs = [dBs[0]]
  for i in range(1, N):
    B = Bs[i-1]+dBs[i]
    Bs.append(B)
  As = Bs
print(" ".join(map(str, As)))

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
light=list(map(int,input().split()))
for k in range(K):
  imo=[0]*(N+1)
  for i in range(N):
    l=max(0,i-light[i])
    r=min(N-1,i+light[i])+1
    imo[l]+=1
    imo[r]-=1
  for i in range(1,N):
    imo[i]+=imo[i-1]
  if light==imo:
    break
  else:
    light=imo[:]
print(*light[:-1])

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
light=list(map(int,input().split()))
for k in range(K):
  imo=[0]*(N+1)
  for i in range(N):
    l=max(0,i-light[i])
    r=min(N-1,i+light[i])+1
    imo[l]+=1
    imo[r]-=1
  for j in range(1,N):
    imo[j]+=imo[j-1]
  if light==imo:
    break
  else:
    light=imo[:]
print(*light[:-1])

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
light=list(map(int,input().split()))
for k in range(K):
  imo=[0]*(N+1)
  for i in range(N):
    kido=light[i]
    imo[max(0,i-kido)]+=1
    imo[min(N-1,i+kido)+1]-=1
    
  for j in range(1,N):
    imo[j]+=imo[j-1]
  if light[:]==imo[:-1]:
    break
  else:
    light=imo[:-1]
print(*light)

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())))
for j in range(1, min(k+1, 50)):
    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)
    a = tmp[:n]
print(*a)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
light=list(map(int,input().split()))
copy=[0]*N
for k in range(K):
  imo=[0]*(N+1)
  x=0
  for i in range(N):
    kido=light[i]
    imo[max(0,i-kido)]+=1
    imo[min(N-1,i+kido)+1]-=1
  for j in range(N):
    x+=imo[j]
    copy[j]=x
  if light==copy:
    break
  else:
    light=copy[:]
print(*light)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
light=list(map(int,input().split()))
for k in range(K):
  imo=[0]*(N+1)
  x=0
  for i in range(N):
    kido=light[i]
    imo[max(0,i-kido)]+=1
    imo[min(N-1,i+kido)+1]-=1
  for j in range(N):
    x+=imo[j]
    light[j]=x
  if N==min(light):
    break
print(*light)

Submission status: Time Limit Exceeded

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

for _ in range(k):
    b=[0]*n
    for i in range(n):
        b[max(0,i-a[i])]+=1
        if i+a[i]<n-1:
            b[i+a[i]+1]-=1    
    f=0
    tmp=0
    for i in range(n):
        tmp+=b[i]
        a[i]=tmp
        if tmp!=n:
            f=1
    if f==0:
        break
print(*a)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

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

for _ in range(min(K, 41)):
    memo = [0] * N
    for i, a in enumerate(A):
        if i > a:
            memo[i - a] += 1
        else:
            memo[0] += 1
        j = i - ~ a
        if j < N:
            memo[j] -= 1
    A = [*accumulate(memo)]

print(*A)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

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

for _ in range(min(K, 41)):
    memo = [0 for _ in range(N)]
    for i, a in enumerate(A):
        if i > a:
            memo[i - a] += 1
        else:
            memo[0] += 1
        j = i - (-a - 1)
        if j < N:
            memo[j] -= 1
        A = [*accumulate(memo)]

print(*A)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

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

for _ in range(K):
    memo = [0 for _ in range(N)]
    for i, a in enumerate(A):
        if i > a:
            memo[i - a] += 1
        else:
            memo[0] += 1
        j = i - (-a - 1)
        if j < N:
            memo[j] -= 1
        A = [*accumulate(memo)]

print(*A)

Submission status: Time Limit Exceeded

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

def conversion(a):
  b = [0]*(n+1)
  for i in range(n):
    b[max(i-a[i], 0)] += 1
    b[min(i+a[i]+1, n)] -= 1
  a = [0]*n
  for i in range(n):
    a[i] = sum(b[0:i+1])
  return a
 
  

for i in range(min(k, 20)):
  a = conversion(a)

for i in range(n):
  print(a[i], end = ' ')

Submission status: Time Limit Exceeded

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

def conversion(a):
  b = [0]*(n+1)
  for i in range(n):
    b[max(i-a[i], 0)] += 1
    b[min(i+a[i]+1, n)] -= 1
  a = [0]*n
  for i in range(n):
    a[i] = sum(b[0:i+1])
  return a
 
  

for i in range(min(k, 41)):
  a = conversion(a)

for i in range(n):
  print(a[i], end = ' ')

Submission status: Time Limit Exceeded

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

def conversion(a):
  b = [0]*(n+1)
  for i in range(n):
    b[max(i-a[i], 0)] += 1
    b[min(i+a[i]+1, n)] -= 1
  a = [0]*n
  for i in range(n):
    a[i] = sum(b[0:i+1])
  return a
 
for i in range(k):
  a = conversion(a)

for i in range(n):
  print(a[i], end = ' ')

Submission status: Time Limit Exceeded

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

for k in range(K):
    imos = [0]*(N+2) #[0],[N+1]は使わない
    for i in range(1,N+1):
        d = A[i]
        imos[max(1,i-d)] += 1
        imos[min(N,i+d) + 1] -= 1
    
    for i in range(2,N+1):
        imos[i] += imos[i-1]
    
    if imos[1:N+1] == A[1:]:
        break
    else:
        A = [0] + imos[1:N+1]

print(*A[1:N+1])

Submission status: Time Limit Exceeded

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

for k in range(K):
    imos = [0]*(N+2) #[0],[N+1]は使わない
    for i in range(1,N+1):
        d = A[i]
        imos[max(1,i-d)] += 1
        imos[min(N,i+d) + 1] -= 1
    
    for i in range(2,N+1):
        imos[i] += imos[i-1]
    
    if imos[1:N+1] == A:
        break
    else:
        A = [0] + imos[1:N+1]

print(*A[1:N+1])

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
n,k = map(int,input().split())
ls = list(map(int,input().split()))
if n >=1000 and k >n/20*math.log(n):
    for q in range(len(ls)):
        print(len(ls),end=" ")
    sys.exit()
if k >= len(ls):
    for q in range(len(ls)):
        print(len(ls),end=" ")
    sys.exit()
for _ in range(k):
    new = [0]*n
    for i in range(n):
        p = 0
        for l in range(1,max(n-i,i+1)):
            if i+l >= 0 and i+l <n:
                if ls[i+l] >= l:
                    p += 1
            if i-l >= 0 and i-l <n:
                if ls[i-l] >= l:
                    p += 1
        new[i] = p+1
    if new == ls:
        print(*ls)
        sys.exit()
    ls = new
print(*ls)

Submission status: Time Limit Exceeded

Solution code:
# 東京海上日動 プログラミングコンテスト2020 C

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:
# 東京海上日動 プログラミングコンテスト2020 C

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
    for i in range(n):
        t += B[i]
        A[i] = t
    if A == [n for i in range(n)]:
        break
    # print(A, B)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
from numba import njit
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def update(A):
    N = len(A)
    B = np.zeros_like(A)
    for i, x in enumerate(A):
        l = max(0, i - x)
        r = min(N - 1, i + x)
        B[l] += 1
        if r + 1 < N:
            B[r + 1] -= 1
    B = np.cumsum(B)
    return B

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

K = min(K, 100)
for _ in range(K):
    A = update(A)
print(' '.join(A.astype(str)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit

@njit
def solve(n, k, l):
    if k >= 50:
        k = 50
    
    dp= [[0,0]]
    for i in range(n-1):
        dp += [[0]*2]
    
    ans = l[:]
    
    for i in range(k):
        for j in range(n):
            tmp = ans[j]
            dp[j][0] = (j+1 - tmp)
            dp[j][1] = (j+1 + tmp)
    
        ans = [0] * n
    
        for x in range(n):
            for y in range(n):
                if dp[y][0] <= x+1 <= dp[y][1]:
                    ans[x] += 1
    
    else:
        return ans

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

print(*solve(n,k,l))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
#from numba import njit

#@njit
def solve(n, k, l):
    if k >= 50:
        k = 50
    
    dp= [[0,0]]
    for i in range(n-1):
        dp += [[0]*2]
    
    ans = l[:]
    
    for i in range(k):
        for j in range(n):
            tmp = ans[j]
            dp[j][0] = (j+1 - tmp)
            dp[j][1] = (j+1 + tmp)
    
        ans = [0] * n
    
        for x in range(n):
            for y in range(n):
                if dp[y][0] <= x+1 <= dp[y][1]:
                    ans[x] += 1
    
    else:
        return ans

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

print(*solve(n,k,l))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
#from numba import njit

#@njit #処理の並列化

def imos(n, a):
    
    l=np.zeros((n+1), dtype = np.int64)

    for i in range(n):
        ai = a[i] # 光の強さ_これにより照らせる範囲が決まる
        start = max(0, i - ai) #StartIndex_照らせる範囲
        end = min(n, i + ai + 1) #EndIndex + 1_照らせる範囲
        l[start] += 1 # 各々を'+1'と'-1'で表し...
        l[end] -= 1
    return np.cumsum(l)[:n] # 累積和をとる_cumulative sum

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

for _ in range(k):
    a = imos(n, a)
    if a.min() == n: # すべての要素が最大値'n'になるとbreak
        break

print(*a)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
List = list(map(int, input().split()))
 
def imosu(x,k):
  data = [0]*k
  for i in range(k):
    first = i-x[i]
    last = i+x[i]
    if first < 0:
      first = 0
    data[first] += 1
    if last+1 < k:
      data[last+1] +=-1
  ruiseki = [0]*k
  ruiseki[0] = data[0]
  for i in range(k-1):
    ruiseki[i+1] = ruiseki[i] + data[i+1]
  return ruiseki
 
for i in range(K):
  List = imosu(List,N)
  if List.count(N) == N:
    break
print(*List)

Submission status: Time Limit Exceeded

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

for i in range(K):
  data = [0]*N
  for j in range(N):
    if j-List[j] < 0:
      data[0] += 1
    else:
      data[j-List[j]] += 1
    if j+List[j]+1 < N:
      data[j+List[j]+1] +=-1
  List[0] = data[0]
  for j in range(N-1):
    List[j+1] = List[j] + data[j+1]
  if List.count(N) == N:
    break
print(*List)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
List = list(map(int, input().split()))
def imosu(x,k):
  data = [0]*k
  for i in range(k):
    first = i-x[i]
    last = i+x[i]
    if first < 0:
      first = 0
    data[first] += 1
    if last+1 < k:
      data[last+1] +=-1
  ruiseki = [0]*k
  ruiseki[0] = data[0]
  for i in range(k-1):
    ruiseki[i+1] = ruiseki[i] + data[i+1]
  return ruiseki

for i in range(K):
  data = [0]*N
  ruiseki = [0]*N
  for i in range(N):
    first = i-List[i]
    last = i+List[i]
    if first < 0:
      first = 0
    data[first] += 1
    if last+1 < N:
      data[last+1] +=-1
  List[0] = data[0]
  for i in range(N-1):
    List[i+1] = List[i] + data[i+1]
  if List.count(N) == N:
    break
print(*List)

Submission status: Time Limit Exceeded

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

for i in range(K):
  Flag = False
  data = [0]*N
  ruiseki = [0]*N
  for i in range(N):
    first = i-List[i]
    last = i+List[i]
    if first < 0:
      first = 0
    data[first] += 1
    if last+1 < N:
      data[last+1] +=-1
  List[0] = data[0]
  for i in range(N-1):
    List[i+1] = List[i] + data[i+1]
  if List.count(N) == N:
      Flag = True
  if Flag:
    break
print(*List)

Submission status: Time Limit Exceeded

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

def imosu(x,k):
  data = [0]*k
  for i in range(k):
    first = i-x[i]
    last = i+x[i]
    if first < 0:
      first = 0
    data[first] += 1
    if last+1 < k:
      data[last+1] +=-1
  ruiseki = [0]*k
  ruiseki[0] = data[0]
  for i in range(k-1):
    ruiseki[i+1] = ruiseki[i] + data[i+1]
  return ruiseki

for i in range(K):
  Flag = False
  List = imosu(List,N)
  if List.count(N) == N:
      Flag = True
  if Flag:
    break
print(*List)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
List = list(map(int, input().split()))
data_x = [0]*N
res = [0]*N

def imosu(x,k):
  data = [0]*k
  for i in range(k):
    first = i-x[i]
    last = i+x[i]
    if first < 0:
      first = 0
    data[first] += 1
    if last+1 < k:
      data[last+1] +=-1
  return data

def ruiseki_f(y, k):
  ruiseki = [0]*k
  ruiseki[0] = y[0]
  for i in range(k-1):
    ruiseki[i+1] = ruiseki[i] + y[i+1]
  return ruiseki

for i in range(K):
  Flag = False
  data_x = imosu(List,N)
  List = ruiseki_f(data_x,N)
  if List.count(N) == N:
      Flag = True
  #print(Flag)
  if Flag:
    break
res = List
print(*res)