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:
import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue
import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, k = ns()
    a = na()

    for _ in range(k):
        imos = [0 for _ in range(n)]

        for i, ai in enumerate(a):
            imos[max(0, i - ai)] += 1
            if i + ai + 1 < n:
                imos[i + ai + 1] -= 1

        val = 0
        for i, im in enumerate(imos):
            val += im
            # tmp = 1 if a[i] == 0 else 0
            a[i] = val

        if min(a) == n:
            break

    print(*a, sep=" ")


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=input().split()
ch=0
r=[0]*n
ans=[0]*n
     
for j in range(k):
  for i in range(n):
    if i-int(a[i])<0:
      r[0]+=1
    else:
      r[i-int(a[i])]+=1
    
    if i+int(a[i])<n-1:
      r[i+int(a[i])+1]-=1
    
  ans[0]=r[0]
  ch+=ans[0]
  for i in range(n-1):
    ans[i+1]=ans[i]+r[i+1]
    ch+=ans[i+1]
  if ch==n*n:
    for k in range(n):
      print(n,end=' ')
    exit()
  a=ans
  r=[0]*n
  ch=0
    
for i in range(n):
  print(ans[i],end=' ')

Submission status: Time Limit Exceeded

Solution code:
from numpy import cumsum
N,K=map(int,input().split())
A=list(map(int,input().split()))
imos=[0 for i in range(N+1)]
ANS=[str(N)]*N
if K>=40:
  ans=" ".join(ANS)
  print(ans)
else:
  for t in range(K):
    for i in range(N):
      l=max(0,i-A[i])
      r=min(N,i+A[i]+1)
      imos[l]+=1
      imos[r]-=1
    imos=cumsum(imos)
    for i in range(0,N):
      A[i]=imos[i]
    imos=[0 for i in range(N+1)]
  for i in range(N):
    A[i]=str(A[i])
  ans=" ".join(A)
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
N,K=map(int,input().split())
A=list(map(int,input().split()))
imos=[0 for i in range(N+1)]
ANS=[str(N)]*N
if K>=40:
  ans=" ".join(ANS)
  print(ans)
else:
  for t in range(K):
    for i in range(N):
      l=max(0,i-A[i])
      r=min(N,i+A[i]+1)
      imos[l]+=1
      imos[r]-=1
    imos=list(accumulate(imos))
    for i in range(0,N):
      A[i]=imos[i]
    imos=[0 for i in range(N+1)]
  for i in range(N):
    A[i]=str(A[i])
  ans=" ".join(A)
  print(ans)

Submission status: Time Limit Exceeded

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

for i in range(K):
  a = [0] * N
  for n, A_n in enumerate(A):
    b_min = 0 if n-A_n < 0 else n-A_n
    b_max = N-1 if n+A_n > N-1 else n+A_n

    b = [0] * (b_min) + [1] * (b_max+1 - b_min) + [0] * (N - b_max - 1)
    a = [ x + y for (x, y) in zip(a, b)]
  A = a

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
from operator import add

N,K = map(int,input().split())
A = map(int,input().split()) 
for k in range(K):
    B = [0] * N
    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
    T = accumulate(B,add) 
    if T == A:
        break
    A = T
print(*A)

Submission status: Time Limit Exceeded

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

for i in range(K):
    new_A_beta = []
    new_A_beta.clear()
    for j in range(N):
        from_num = (j + 1) - A[j] - 0.5
        to_num = (j + 1) + A[j] + 0.5
        for k in range(N):
            if from_num <= (k + 1) <= to_num:
                new_A_beta.append(k + 1)
        new_A = []
        new_A.clear()
        for l in range(N):
            new_A.append(new_A_beta.count(l + 1))
    if all(elem == N for elem in new_A):
        print(*new_A)
        exit()
    A.clear()
    for m in new_A:
        A.append(m)

print(*new_A)

Submission status: Time Limit Exceeded

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

for i in range(K):
  a = [0] * N
  for n, A_n in enumerate(A):
    b = [0] * N
    b_min = 0 if n-A_n < 0 else n-A_n
    b_max = N-1 if n+A_n > N-1 else n+A_n

    for j in range(b_min, b_max+1):
      b[j] = 1
    a = [ x + y for (x, y) in zip(a, b)]
  A = 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()))
imos=[0 for i in range(N+1)]
zero=[0 for i in range(N+1)]
ANS=[str(N)]*N
if K>=40:
  ans=" ".join(ANS)
  print(ans)
else:
  for t in range(K):
    for i in range(N):
      l=max(0,i-A[i])
      r=min(N,i+A[i]+1)
      imos[l]+=1
      imos[r]-=1
    for i in range(0,N):
      imos[i+1]+=imos[i]
      A[i]=imos[i]
    imos=[0 for i in range(N+1)]
  for i in range(N):
    A[i]=str(A[i])
  ans=" ".join(A)
  print(ans)

Submission status: Time Limit Exceeded

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

for j in range(k):
  ls = [0 for i in range(n)]
  rs = [0 for i in range(n)]
  
  for i in range(n):
    l = max(i - a[i], 0)
    r = min(i + a[i], n-1) + 1
    ls[l] += 1
    if r < n:
      rs[r] += 1
  
  ans[0] = ls[0] - rs[0]
  for i in range(1, n):
    ls[i] += ls[i-1]
    rs[i] += rs[i-1]
    ans[i] = ls[i] - rs[i]
  
  if len(set(ans)) == 1 and ans[0] == n:
    break

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

Submission status: Time Limit Exceeded

Solution code:
def conv(A,N):
    #A(座標iの電灯の強さリスト)からB(座標iを照らしている電灯数)への変換
    #累積和を使う
    B_=[0 for n in range(N)]
    for n in range(1,N+1):
        il_min=max(n-A[n-1],1)
        il_max=min(n+A[n-1],N)
        B_[il_min-1]+=1
        if il_max<=N-1:
            B_[il_max]-=1

    B=[0 for n in range(N)]
    B[0]=B_[0]
    for n in range(1,N):
        B[n]=B[n-1]+B_[n]
    return B

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

    for k in range(K):
        B=conv(A,N)
        if A==B:
            break
        else:
            A=B
    return " ".join(list(map(str,A)))

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

Submission status: Time Limit Exceeded

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

for i in range(K):
  new_A_beta = []
  new_A_beta.clear()
  for j in range(N):
    from_num = (j+1) - A[j] -0.5
    to_num = (j+1) + A[j] + 0.5
    for k in range(N):
      if from_num <= (k+1) <= to_num:
        new_A_beta.append(k+1)
    new_A =[]
    new_A.clear()
    for l in range(N):
      new_A.append(new_A_beta.count(l+1))
  A.clear()
  for m in new_A:
    A.append(m)
    
print(*new_A)

Submission status: Time Limit Exceeded

Solution code:
def conv(A,N):
    #A(座標iの電灯の強さリスト)からB(座標iを照らしている電灯数)への変換
    #累積和を使う
    B_=[0 for n in range(N)]
    for n in range(1,N+1):
        il_min=max(n-A[n-1],1)
        il_max=min(n+A[n-1],N)
        B_[il_min-1]+=1
        if il_max<=N-1:
            B_[il_max]-=1
    B=[sum(B_[:n+1]) for n in range(N)]
    return B

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

    for k in range(K):
        B=conv(A,N)
        if A==B:
            break
        else:
            A=B
    return " ".join(list(map(str,A)))

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

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
imos=[0 for i in range(N+1)]

for t in range(K):
  for i in range(N):
    l=max(0,i-A[i])
    r=min(N,i+A[i]+1)
    imos[l]+=1
    imos[r]-=1
  for i in range(0,N):
    imos[i+1]+=imos[i]
    A[i]=imos[i]
  imos=[0 for i in range(N+1)]
  if len(set(A))==1 and (N in set(A)):
    break
for i in range(N):
  A[i]=str(A[i])
ans=" ".join(A)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
imos=[0 for i in range(N+1)]
ANS=[str(N)]*N
if K>=100:
  ans=" ".join(ANS)
  print(ans)
else:
  for t in range(K):
    for i in range(N):
      l=max(0,i-A[i])
      r=min(N,i+A[i]+1)
      imos[l]+=1
      imos[r]-=1
    for i in range(0,N):
      imos[i+1]+=imos[i]
      A[i]=imos[i]
    imos=[0 for i in range(N+1)]
    if len(set(A))==1 and (N in set(A)):
      break
  for i in range(N):
    A[i]=str(A[i])
  ans=" ".join(A)
  print(ans)

Submission status: Time Limit Exceeded

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


for i in range(k):
    b = [0] * (n+1)
    for j in range(n):
        l = max(0, j-a[j])
        r = min(n, j+a[j]+1)
        b[l] += 1
        b[r] -= 1
    for j in range(n):
        b[j+1] += b[j]
    b.pop()
    if a == b:
        break
    a = b
print(' '.join(map(str, a)))

Submission status: Time Limit Exceeded

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


for i in range(k):
    b = [0] * (n+1)
    for j in range(n):
        l = max(0, j-a[j])
        r = min(n, j+a[j]+1)
        b[l] += 1
        b[r] -= 1
    for j in range(n):
        b[j+1] += b[j]
    b.pop()
    if a == b:
        print(' '.join(map(str, a)))
        exit()
    a = b
print(' '.join(map(str, a)))

Submission status: Time Limit Exceeded

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

for _ in range(0, K):
    B = [0 for _ in range(N)]

    for i in range(0,N):
        f = max(0, i - A[i])
        t = min(N-1, i + A[i])
        #for j in range(max(0, f), min(N, t)+1):
        #    B[j] += 1
        B[f] += 1
        if t+1 < N:
            B[t+1] -= 1
    for i in range(1,N):
        B[i] += B[i-1]
    if A == B:
        break
    A = B
    i += 1
    
print(" ".join(map(lambda a: str(a), A)))

Submission status: Time Limit Exceeded

Solution code:
n,k=[int(_) for _ in input().split()]
A=[int(_) for _ in input().split()]
_A=[0 for i in range(n)]
for i in range(min(k,50)):
    for j in range(n):
        _A[j]=0

    for j in range(n):
        if j-A[j]>0:
            _A[j-A[j]]+=1
        else:
            _A[0]+=1
        if j+A[j]+1<n:
            _A[A[j]+j+1]-=1
    for j in range(1,n):
        _A[j]+=_A[j-1]
    for j in range(n):
        A[j]=_A[j]
    
    if sum(A)==n*n:
        break

for i in range(n):
    print(A[i],end=" ")
print()

Submission status: Time Limit Exceeded

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

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

  for i in range(1, n):
    ls[i] += ls[i-1]
    rs[i] += rs[i-1]

  for i in range(n):
    ans[i] = ls[i] - rs[i]
  
  if len(set(ans)) == 1 and ans[0] == n:
    break

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
from operator import add

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

for k in range(K):
    B = [0] * N
    for i,x in enumerate(A):
        left = max(0, i-x)
        right = min(N-1, i+x)
        B[left] += 1
        if right+1 != N:
            B[right+1] -= 1
    A = list(accumulate(B,add))    
print(*A,sep=" ")

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate


def main():
    number, operations = [int(x) for x in input().split()]
    dists = [int(x) for x in input().split()]

    number = 10 ** 5 * 2
    dists = [0] * number
    operations = number

    for ope_count in range(operations):
        temp = [0] * (number + 1)
        for i, v in enumerate(dists):
            left = max(i - v, 0)
            right = min(i + v + 1, number)
            temp[left] += 1
            temp[right] -= 1
        dists = accumulate(temp)
        if ope_count == 41:
            break

    print(*list(dists)[:-1])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def proc():
    global A
    B = [0 for _ in range(N)]

    for i in range(0,N):
        f = max(0, i - A[i])
        t = min(N-1, i + A[i])
        #for j in range(max(0, f), min(N, t)+1):
        #    B[j] += 1
        B[f] += 1
        if t+1 < N:
            B[t+1] -= 1
    for i in range(1,N):
        B[i] += B[i-1]
    A = B

i = 0
while i in range(0, K):
    proc()
    if all(map(lambda a: a == N, A)):
        i = K
    i += 1

print(" ".join(map(lambda a: str(a), A)))

Submission status: Time Limit Exceeded

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

for i in range(k):
    b = [0] * (n+1)
    c = list(b)
    for j in range(n):
        l = max(0, j-a[j])
        r = min(n, j+a[j]+1)
        b[l] += 1
        b[r] -= 1
    for j in range(1, n):
        b[j] += b[j-1]
    a = b
    if b == c:
        for j in range(n):
            print(a[j], end=' ')
        exit()
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()))
imos=[0 for i in range(N+1)]
ANS=[str(N)]*N
if K>=40:
  ans=" ".join(ANS)
  print(ans)
else:
  for t in range(K):
    for i in range(N):
      l=max(0,i-A[i])
      r=min(N,i+A[i]+1)
      imos[l]+=1
      imos[r]-=1
    for i in range(0,N):
      imos[i+1]+=imos[i]
      A[i]=imos[i]
    imos=[0 for i in range(N+1)]
  for i in range(N):
    A[i]=str(A[i])
  ans=" ".join(A)
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
imos=[0 for i in range(N+1)]
ANS=[str(N)]*N
if K>=50:
  ans=" ".join(ANS)
  print(ans)
else:
  for t in range(K):
    for i in range(N):
      l=max(0,i-A[i])
      r=min(N,i+A[i]+1)
      imos[l]+=1
      imos[r]-=1
    for i in range(0,N):
      imos[i+1]+=imos[i]
      A[i]=imos[i]
    imos=[0 for i in range(N+1)]
  for i in range(N):
    A[i]=str(A[i])
  ans=" ".join(A)
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate
import math

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    mina = min(A)
    for i in range(K):
        B = [0]*N
        for j in range(N):
            if j-A[j] >= 0:
                B[j-A[j]] += 1
            else:
                B[0] += 1
            if j+A[j]+1 < N:
                B[j+A[j]+1] -= 1
            # print(j,B)
        A = list(accumulate(B[:]))
        mina = mina*2+1
        if mina >= N and A[0] == A[-1] == N:
            break
        # print(A,mina) 
    print(*A)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
N, K, *A = map(int, open(0).read().split())
for _ in range(min(K, 41)):
    next_A = [0] * (N + 1)
    for i, a in enumerate(A):
        next_A[max(0, i - a)] += 1
        next_A[min(N, i + a + 1)] -= 1
    A = list(accumulate(next_A))
A.pop()
print(*A)

Submission status: Time Limit Exceeded

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

def proc():
    global A
    B = [0 for _ in range(N)]

    for i in range(0,N):
        f = max(0, i - A[i])
        t = min(N-1, i + A[i])
        #for j in range(max(0, f), min(N, t)+1):
        #    B[j] += 1
        B[f] += 1
        if t+1 < N:
            B[t+1] -= 1
    for i in range(1,N):
        B[i] += B[i-1]
    A = B

for _ in range(0, min(K,41)):
    proc()

print(" ".join(map(lambda a: str(a), A)))

Submission status: Time Limit Exceeded

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

def proc():
    global A
    B = [0 for _ in range(N)]

    for i in range(0,N):
        f = max(0, i - A[i])
        t = min(N-1, i + A[i])
        #for j in range(max(0, f), min(N, t)+1):
        #    B[j] += 1
        B[f] += 1
        if t+1 < N:
            B[t+1] -= 1
    for i in range(1,N):
        B[i] += B[i-1]
    A = B

for _ in range(0, K):
    proc()

print(" ".join(map(lambda a: str(a), A)))

Submission status: Time Limit Exceeded

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

    for _ in range(K):
        B = [0] * (N + 1)
        for i, x in enumerate(A):
            B[max(0, i - x)] += 1
            B[min(N - 1, i + x) + 1] -= 1
        for i in range(N):
            B[i + 1] += B[i]
        B.pop()
        if A == B: break
        A = B
    print(*A)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#いもす法

import copy
from sys import stdin

n,k=map(int,input().split())
#a=list(map(int,input().split()))
a=list(map(int, stdin.readline().split()))
imosutable=[0]*(n+1)

for m in range(0,k):
    maxed=0
    for i in range(0,n):
        d=a[i]
        imosutable[max(0,i-d)]+=1
        imosutable[min(i+d+1,n)]-=1
    for i in range(1,n):
        imosutable[i]+=imosutable[i-1]
        if imosutable[i]==n:
            maxed+=1   

    if maxed==(n-1) and imosutable[0]==n:
        answer=imosutable[0:n]
        print(' '.join(map(str,answer)))
        exit()

    a=copy.copy(imosutable)
    imosutable=[0]*(n+1)

answer=a[0:n]
for s in answer[0:n-1]:
    print (str(s)+" ",end="")
print(answer[n-1])

Submission status: Time Limit Exceeded

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

r = [[0 for _ in range(n)] for _ in range(k)]

for i in range(k):
    for j in range(n):
        if j-a[j] < 0 and j+a[j]+1 <= (n-1):
            r[i][0] += 1
            r[i][j+a[j]+1] -= 1           
        elif j-a[j] < 0 and j+a[j]+1 > (n-1):
            r[i][0] += 1
        elif j-a[j] >=0 and j+a[j]+1 <= (n-1):
            r[i][j-a[j]] += 1
            r[i][j+a[j]+1] -= 1
        elif j-a[j] >= 0 and j+a[j]+1 > (n-1):
            r[i][j-a[j]] += 1
        else:
            r[i][j-a[j]] += 1
            r[i][j+a[j]+1] -= 1
    for j in range(1, n):
        r[i][j] += r[i][j-1]
    a = r[i]
    if r[i] == r[i-1]:
        print(' '.join(map(str, r[i])))
        exit()
print(' '.join(map(str, r[k-1])))

Submission status: Time Limit Exceeded

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

def proc():
    global A
    B = [0 for _ in range(N)]

    for i in range(0,N):
        f = i - A[i]
        t = i + A[i]
        for j in range(max(0, f), min(N, t+1)):
            B[j] += 1
    
    A = B

for _ in range(0, min(K,41)):
    proc()

print(" ".join(map(lambda a: str(a), A)))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    # print(A)
    for i in range(K):
        
        B = [0] * N
        for j in range(N):
            B[max(j-A[j],0)] += 1
            if j+A[j]+1 < N:
                B[j+A[j]+1] -= 1
            # print(j,B)
        A = list(accumulate(B[:]))
        if A == [N]*N:
            break
    print(*A)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#いもす法

import copy
n,k=map(int,input().split())
a=list(map(int,input().split()))
imosutable=[0]*(n+1)

for m in range(0,k):
    maxed=0
    for i in range(0,n):
        d=a[i]
        imosutable[max(0,i-d)]+=1
        imosutable[min(i+d+1,n)]-=1
    for i in range(1,n):
        imosutable[i]+=imosutable[i-1]
        if imosutable[i]==n:
            maxed+=1   

    if maxed==(n-1) and imosutable[0]==n:
        answer=imosutable[0:n]
        print(' '.join(map(str,answer)))
        exit()

    a=copy.copy(imosutable)
    imosutable=[0]*(n+1)

answer=a[0:n]
for s in answer[0:n-1]:
    print (str(s)+" ",end="")
print(answer[n-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import jit
@jit(cache=True)
def solve(n,k,A):
    l,r=0,0
    for ki in range(k):
        B=np.zeros(n+1,dtype=np.int64)
        for i,j in enumerate(A):
            l=max(0,i-j)
            r=min(n,i+j+1)
            B[l]+=1
            B[r]-=1
        A=np.cumsum(B[:-1])
        np.delete(A,n-1)
    return A

n,k=map(int,input().split())
A=list(map(int,input().split()))
A=np.array(A)
x=solve(n,k,A)
print(*x)

Submission status: Time Limit Exceeded

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

def proc():
    global A
    B = [0 for _ in range(N)]

    for i in range(0,N):
        f = i - A[i]
        t = i + A[i]
        for j in range(max(0, f), min(N, t+1)):
            B[j] += 1
    
    A = B

for _ in range(0, K):
    proc()

print(" ".join(map(lambda a: str(a), A)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import jit
@jit(cache=True)
def solve(n,k,A):
    l,r=0,0
    for ki in range(k):
        B=np.zeros(n+1,dtype=np.int64)
        for i,j in enumerate(A):
            l=max(0,i-j)
            r=min(n,i+j+1)
            B[l]+=1
            B[r]-=1
        A=np.cumsum(B[:-1])
        np.delete(A,n-1)
    return A

n,k=map(int,input().split())
A=list(map(int,input().split()))
A=np.array(A)
x=solve(n,k,A)
print(*x)

Submission status: Time Limit Exceeded

Solution code:
import collections

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

sum_before = 0
for k in range(K):
    sum = 0
    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
        b[r] -= 1
    for i in range(N):
        b[i + 1] += b[i]
        sum += b[i]
    b.pop(-1)
    if sum_before == sum:
        break
    A = b
    sum_before = sum

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

Submission status: Time Limit Exceeded

Solution code:
def strength(A):
  """
  光の強さAのリストを受け取って、操作後の光の強さBのリストを返す
  """
  
  # Aと同じ要素数の配列Bで初期化
  B = [0] * len(A)
  
  # Aの要素数の数だけループを回し、Aの要素の値分、横の要素に値を加える
  for i in range(len(A)):
    
    # 影響する最小/最大座標
    min = i - A[i]
    max = i + A[i]
    
    # 最小から最大まで1加える
    if (min < 0):
      min = 0
    if (max + 1 > N):
      max = N
    else:
      max = max + 1
    for j in range(min, max):
      B[j] += 1
  
  return B

  
# 電球の数N, 操作回数K
N, K = map(int, input().split())

# 最初の光の強さA
A = list(map(int, input().split()))

B = [N] * len(A)

if (K >= N):
  print(*B)
  
else:
  
  # 操作をK回実行する。途中で全部がNになったら終了
  for k in range(K):
    B = strength(A)
    A = B
    if (B.count('N') == N):
      break

  print(*B)

Submission status: Time Limit Exceeded

Solution code:
#いもす法で解いてみる
#いもす法とは

import copy
n,k=map(int,input().split())
a=list(map(int,input().split()))
imosutable=[0]*n*2

for m in range(0,k):
    maxed=0
    for i in range(0,n):
        d=a[i]
        imosutable[max(0,i-d)]+=1
        imosutable[min(i+d+1,2*n-1)]-=1
    for i in range(1,n):
        imosutable[i]+=imosutable[i-1]
        if imosutable[i]==n:
            maxed+=1   

    if maxed==n:
        answer=imosutable[0:n]
        print(' '.join(map(str,a)))
        exit()

    a=copy.copy(imosutable)
    imosutable=[0]*n*2

answer=a[0:n]
for s in answer[0:n-1]:
    print (str(s)+" ",end="")
print(answer[n-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
inp = sys.stdin.buffer.readline
 
import numpy as np
def resolve():
    N, K = map(int, inp().split())
    A = np.array(list(map(int, inp().split())), np.int64)
 
    for _ in range(K):
        imos_table = np.zeros(N + 1, np.int64)
        for i, a in enumerate(A):
            # 配列の個数を超えないように注意
            imos_table[max(i - a, 0)] += 1
            imos_table[min(i + a + 1, N)] -= 1
        A = np.cumsum(imos_table)[:-1]
        if np.all(A == N):
            print(*A)
            return
    else:
        print(*A)
        
if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import jit
@jit(cache=True)

def solve(n,k,A):
    l,r=0,0
    for ki in range(k):
        B=np.zeros(n+1,dtype=int)
        for i,j in enumerate(A):
            l=max(0,i-j)
            r=min(n,i+j+1)
            B[l]+=1
            B[r]-=1
        A=np.cumsum(B[:-1])
        if A[A==n].size==n:
            break
    return A

n,k=map(int,input().split())
A=list(map(int,input().split()))
x=solve(n,k,A)
print(*x)

Submission status: Time Limit Exceeded

Solution code:
def strength(A):
  """
  光の強さAのリストを受け取って、操作後の光の強さBのリストを返す
  """
  
  # Aと同じ要素数の配列Bで初期化
  B = [0] * len(A)
  
  # Aの要素数の数だけループを回し、Aの要素の値分、横の要素に値を加える
  for i in range(len(A)):
    
    # 影響する最小/最大座標
    min = i - A[i]
    max = i + A[i]
    
    # 最小から最大まで1加える
    if (min < 0):
      min = 0
    if (max + 1 > N):
      max = N
    else:
      max = max + 1
    for j in range(min, max):
      B[j] += 1
  
  return B

  
# 電球の数N, 操作回数K
N, K = map(int, input().split())

# 最初の光の強さA
A = list(map(int, input().split()))

B = []

# 操作をK回実行する。途中で全部がNになったら終了
for k in range(K):
  B = strength(A)
  A = B
  if (B.count('N') == N):
    break

print(*B)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import jit
@jit(cache=True)

def solve(n,k,A):
    l,r=0,0
    for ki in range(k):
        B=np.zeros(n+1,dtype=int)
        for i,j in enumerate(A):
            l=max(0,i-j)
            r=min(n,i+j+1)
            B[l]+=1
            B[r]-=1
        A=np.cumsum(B[:-1])
        np.delete(A,n-1)
    return A

n,k=map(int,input().split())
A=list(map(int,input().split()))
x=solve(n,k,A)
print(*x)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import jit
#@jit(cache=True)

def solve(n,k,A):
    l,r=0,0
    for ki in range(k):
        B=np.zeros(n+1,dtype=int)
        for i,j in enumerate(A):
            l=max(0,i-j)
            r=min(n,i+j+1)
            B[l]+=1
            B[r]-=1
        A=np.cumsum(B[:-1])
        np.delete(A,n-1)
    return A

n,k=map(int,input().split())
A=list(map(int,input().split()))
x=solve(n,k,A)
print(*x)

Submission status: Time Limit Exceeded

Solution code:
import math
from itertools import accumulate

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

for _ in range(K):
    s = [0] * N
    for i in range(N):
        left = i - al[i]
        right = i + al[i]
        if left < 0:
            left = 0
        s[left] += 1
        if right + 1 <= N - 1:
            s[right + 1] -= 1
        # print(left,right)
    al = list(accumulate(s))
    # print(al)
    if al == [N] * N:
        print(*al)
        #print('end')
        exit()

print(*al)

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import factorial
from collections import Counter
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
MOD = 10**9 + 7

n, k = MAP()
a = LIST()


end = [n]*n

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

for i in range(n):
    print(str(int(a[i]))+" ",end = "" )

Submission status: Time Limit Exceeded

Solution code:
import collections

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

sum_before = 0
for k in range(K):
    sum = 0
    b = [0 for _ in range(N + 1)]
    for i, a in enumerate(A):
        l = max(0, i - a)
        r = min(i + a + 1, N)
        b[l] += 1
        b[r] -= 1
    for i in range(N):
        b[i + 1] += b[i]
        sum += b[i]
    b.pop(-1)
    if sum_before == sum:
        break
    A = b
    sum_before = sum

for n in A:
    print(n)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N,k = map(int,input().split())
l = [int(a) for a in input().split()]
m = [N] * N
for _ in range(k):
    a = [0] * (N+1)
    for i,x in enumerate(l):
        a[max(0,i-x)] += 1
        a[min(i+x+1,N)] -= 1
    a_l = np.cumsum(np.array(a))[:-1].tolist()
    if a_l == m:
        break
    else:
        l = a_l
print(' '.join(map(str, a_l)))

Submission status: Time Limit Exceeded

Solution code:
import math
from itertools import accumulate

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

printed_lst = []
for _ in range(K):
    s = [0]*N
    for i in range(N):
        left = i - al[i]
        right = i + al[i]
        if left < 0:
            left = 0
        s[left] += 1
        if right+1 <= N-1:
            s[right+1] -= 1
        #print(left,right)
    al = list(accumulate(s))
    #print(al)
    if al in printed_lst:
        print(' '.join([str(i) for i in al]))
        #print('end')
        exit()
    else:
        printed_lst.append(al)

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