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 numpy as np

def fn(N, K, A):
    for _ in range(K):
        B = np.zeros(N, dtype=np.int64)
        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

        A = np.cumsum(B)
        if (np.all(A == N)):
            return A
    return A

N, K = map(int, input().split())
A = list(map(int, input().split()))
A = np.array(A, dtype=np.int64)

B = fn(N, K, A)
print(" ".join(B.astype(str)))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(300000)

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI0(): return map(lambda s: int(s) - 1, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
def LMI0(): return list(map(lambda s: int(s) - 1, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')
from itertools import accumulate



N, K = MI()
A = LMI()

for _ in range(K):
    accum = [0] * (N + 1)
    for i, a in enumerate(A):
        l, r = max(0, i - a), min(N - 1, i + a)
        accum[l] += 1
        accum[r + 1] -= 1
    accum = list(accumulate(accum))
    if accum[0] == accum[-1] == N:
        break
    A = accum[:-1]
print(*A)

Submission status: Time Limit Exceeded

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

#print([0] *n)

for _ in range(min(k,45)):

    bn = [0] *n
    for i in range(n):
        for j in range(max(i-an[i],0), min(n, i+an[i]+1)):
            bn[j] += 1
            #print(bn)
    an = bn

print(*an)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, K = map(int, input().split())
A = list(map(int, input().split()))
B = [0]*len(A)

for _ in range(K):
  for i in range(N):
    l = max(0, i-A[i])
    r = min(N-1, i+A[i])
    B[l]+=1
    if r+1 < N:
      B[r+1]-=1
  A = np.cumsum(B)
  if min(A) == N:
    break
  B = [0]*len(A)
A = map(str, A)
print(' '.join(A))

Submission status: Time Limit Exceeded

Solution code:
import copy
import math

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

all_flag = False
for i in range(k):  # 0～k-1
    next_a = [0] * n

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

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

            #print("{}, {}".format(min_index, max_index))
            for l in range(min_index, max_index+1):
                #print("l = {}".format(l))
                next_a[l] += 1
                if next_a[l] > n:   # これいるかな？
                    next_a[l] = n

        a = copy.copy(next_a)

        # check
        all_flag2 = True
        for l in next_a:
            if l < n:
                all_flag2 = False
                break
        if all_flag2 == True:
            break

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

Submission status: Time Limit Exceeded

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

def simulate():
    global A
    B = [0]*N
    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]
    if sum(B) == N*K:
        print(*[N]*N)
        exit()
    A = B

for k in range(K):
    simulate()
print(*A)

Submission status: Time Limit Exceeded

Solution code:
import math
def main():
    n, k = list(map(int, input().split()))
    A = list(map(int, input().split()))
    C = [set(range(n)) for _ in range(n)]
    I = set(range(n))
    if k >= math.log2(n):
        print(' '.join([n] * n))
    else:
        for _ in range(k):
            for i in I:
                rm = set()
                for j in C[i]:
                    if A[j] >= abs(i - j):
                        rm.add(j)
                C[i] -= rm
            if len(C[i]) == 0:
                I.remove(i)
            A = [n - len(C[i]) for i in range(n)]
        print(' '.join(list(map(str, A))))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
def inbox(i, n):
    i = max(0, i)
    i = min(i, n)
    return(i)

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

    for _ in range(k):
        b = [0 for p in range(n)]
        for i in range(n):
            l = inbox(i - a[i], n)
            r = inbox(i + a[i] + 1, n)
            b[l] += 1
            if r != n:
                b[r] -= 1

        for i in range(1, n):
            b[i] += b[i-1]
        if b == a:
            break
        a = b[:]

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

counts = 0
for i in range(k):
    b = [0] * n
    for j in range(n):
        left = j - a[j] - 0.5
        right = j + a[j] + 0.5
        for k in range(max(0,int(left+1)),min(n,int(right)+1)):
            b[k] += 1
    a = b[:]

print(*a)

Submission status: Time Limit Exceeded

Solution code:
from numba import njit

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

@njit(cache=True)
def solve(A):
    B = [0] * (N + 1)
    for x, d in enumerate(A):
        B[max(0, x - d)] += 1
        B[min(N, x + d + 1)] -= 1
    for i in range(N):
        B[i + 1] += B[i]
    return B

for _ in range(min(K, 41)):
    A = solve(A)

print(*A[:-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,k=map(int,input().split())
a=[int(i) for i in input().split()]
k=min(k,41)

for j in range(k):
    b=np.zeros_like(a)
    for i in range(n):
        l=max(0,i-a[i])
        r=min(n-1,i+a[i])
        b[l]+=1
        if r+1<n:
            b[r+1]-=1
    for i in range(1,n):
        b[i]+=b[i-1]
    a=b
print(" ".join(map(str,a)))

Submission status: Time Limit Exceeded

Solution code:
import copy
import math

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

all_flag = False
for i in range(k):  # 0～k-1
    next_a = [0] * n

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

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

            #print("{}, {}".format(min_index, max_index))
            for l in range(min_index, max_index+1):
                #print("l = {}".format(l))
                next_a[l] += 1
                if next_a[l] > n:   # これいるかな？
                    next_a[l] = n

        # check
        all_flag2 = True
        for l in next_a:
            if l < n:
                all_flag2 = False
                break
        all_flag = all_flag2
    
        a = copy.copy(next_a)

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

Submission status: Time Limit Exceeded

Solution code:
import copy
from functools import lru_cache
import math
def resolve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

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

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

        A = B[:]

        if k >= 41:
            break

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

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import copy
from functools import lru_cache
import math
def resolve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

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

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

        A = B[:]

        if min(A) == N:
            break

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

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
tmp = input().split(' ')
A = []

for i in range(N):
    A = A + [int(tmp[i])]
Z = [N]*N

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

    for i in range(1,N):
        B[i]+=B[i-1]
        
    A = B[0:N]

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, K = map(int, input().split())
A = list(map(int, input().split()))
A = np.array(A, dtype=np.int64)

for _ in range(0, min(42, K)):
    B = np.zeros(N, dtype=np.int64)
    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
    A = np.cumsum(B)
    if (np.all(A == N)):
        break;

print(" ".join([str(item) for item in A]))

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
 
for _ in range(min(k,41)):
    s=[0 for _ in range(n)]
    e=[0 for _ in range(n)]
    for i in range(n):
        d=a[i]
        s[max(0,i-d)]+=1
        e[min(n-1,i+d)]+=1
    a[0]=s[0]
    for i in range(1,n):
        s[i]=s[i-1]+s[i]
        e[i]=e[i-1]+e[i]
        a[i]=s[i]-e[i-1]
 
print(*a)

Submission status: Time Limit Exceeded

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

for _ in range(min(k,100)):
    s=[0 for _ in range(n)]
    e=[0 for _ in range(n)]
    for i in range(n):
        d=a[i]
        s[max(0,i-d)]+=1
        e[min(n-1,i+d)]+=1
    a[0]=s[0]
    for i in range(1,n):
        s[i]=s[i-1]+s[i]
        e[i]=e[i-1]+e[i]
        a[i]=s[i]-e[i-1]

print(*a)

Submission status: Time Limit Exceeded

Solution code:
import copy
from functools import lru_cache
import math
def resolve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

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

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

        A = copy.deepcopy(B)

        if min(A) == N:
            break

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

if __name__ == "__main__":
    resolve()

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

    A = B
    if all([i==N for i in B]):
        break

print(*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):
  p=[0]*N
  n=[0]*N
  for i in range(N):
    if i-A[i]>0:
      p[i-A[i]]+=1
    else:
      p[0]+=1
    if i+A[i]<N-1:
      n[i+A[i]+1]+=1
  light=0
  Ncount=0
  for i in range(N):
    light=light+p[i]-n[i]
    A[i]=light
    if light==N:
      Ncount+=1
  if Ncount==N:
    out=[N]*N
    print(*out, sep=' ')
    exit()
print(*A, sep=' ')

Submission status: Time Limit Exceeded

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

for j in range(k):
    b=[0 for i in range(n)]
    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
print(" ".join(map(str,a)))

Submission status: Time Limit Exceeded

Solution code:
n,k,*a=map(int,open(0).read().split())
for _ in range(k):
  b=[0]*(n+1)
  for i,c in enumerate(a):
    b[max(0,i-c)]+=1
    b[min(n,c+i+1)]-=1
  for i in range(n):
    b[i+1]+=b[i]
  a=b[:-1]
  if a==[n]*n:
    print(*a)
    exit()
print(*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):
  p=[0]*N
  n=[0]*N
  for i in range(N):
    if i-A[i]>0:
      p[i-A[i]]+=1
    else:
      p[0]+=1
    if i+A[i]<N-1:
      n[i+A[i]+1]+=1
  light=0
  Ncount=0
  for i in range(N):
    light=light+p[i]-n[i]
    A[i]=light
    if light==N:
      Ncount+=1
  if Ncount==N:
    out=[N]*N
    print(*out, sep=' ')
print(*A, sep=' ')

Submission status: Time Limit Exceeded

Solution code:
import copy
from functools import lru_cache
import math
def resolve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    #N = 20000
    #K = 20000
    #A = [0] * N

    cut_mode = True

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

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

        if cut_mode and A == B:
            break

        A = copy.deepcopy(B)

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

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
def inbox(i, n):
    i = max(0, i)
    i = min(i, n)
    return(i)

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

    a_new = [0 for _ in range(n)]
    for _ in range(k):
        b = [0 for p in range(n)]
        for i in range(n):
            l = inbox(i - a[i], n)
            r = inbox(i + a[i] + 1, n)
            b[l] += 1
            if r != n:
                b[r] -= 1

        a_new[0] = b[0]
        for i in range(1, n):
            a_new[i] = a_new[i-1] + b[i]
        if a_new == a:
            break
        a = a_new[:]

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
current = a[:]
for _ in range(min(50, k)):
    nex = [0]*n
    for i, v in enumerate(current):
        l = max(0, i-v)
        r = min(n-1, i+v)
        nex[l] += 1
        if r+1 < n:
            nex[r+1] -= 1
    for i in range(1, n):
        nex[i] += nex[i-1]
    current = nex

print(*current)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np


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


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

    B = np.cumsum(B)
    return B


def main():
    N, K = map(int, readline().split())
    A = np.array(list(map(int, readline().split())))


    K = min(K, 50)
    for _ in range(K):
        A = c(A)

    print(' '.join(A.astype(str)))


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

    A = B

    if all(B) == N:
        break

print(*A)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=[int(i) for i in input().split()]
c=1
k=min(k,40)


for j in range(k):
    b=[0 for i in range(n)]
    e=float("inf")
    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]
        e=max(e,b[i-1])
    c+=1
    a=b
    if e==n:
        break
print(" ".join(map(str,a)))

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
tmp = input().split(' ')
A = []

for i in range(N):
    A = A + [int(tmp[i])]
Z = [N]*N

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

    A[0] = B[0]
    for i in range(1,N):
        A[i]=A[i-1]+B[i]

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    for _ in range(0, min(42, K)):
        A = update(A, N)
    print(" ".join([str(item) for item in A]))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

import math
n,k = map(int,input().split())
a = np.array(input().split(),np.int64)

def solve(n,k,a):
    for i in range(k):
        new = np.zeros_like(a)
        for j in range(n):
            distance = j - a[j]
            if distance < 0:
                distance = 0
            last =  j + a[j]
            if last > n-1:
                last = n-1
            new[distance]+=1
            if last+1 < n:
                new[last+1]-=1
        a = np.cumsum(new)
        if np.all(a==n):
            break
    print(*a)

solve(n,k,a)

Submission status: Time Limit Exceeded

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

dic = {}
base_dic = {}

for i, j in enumerate(A, 1):
    dic[i] = j
    base_dic[i] = 0

for l in range(K):

    dic_copy = dic.copy()
    dic = base_dic.copy()

    for i, j in dic_copy.items():
        if i - j >= 1:
            low = i - j
        else:
            low = 1
        if i + j <= N:
            high = i + j
        else:
            high = N
        for k in range(low, high + 1):
                dic[k] += 1

        if dic == dic_copy:
            break

ans = []
for v in dic.values():
    ans.append(v)
ans = map(str, ans)
ans = " ".join(ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque
from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate

def solve():
    N, K = MI()
    A = LI()
    for i in range(K):
        B = [0] * N
        for idx, a in enumerate(A):
            l = max(0, idx - a)
            r = idx + a + 1
            # print(idx, a, l, r)
            B[l] += 1
            if N > r:
                B[r] -= 1
        # print(B)
        B = list(accumulate(B))
        # print(B)
        if all([j == N for j in B]):
            printlist(B)
            return
        A = B
    printlist(A)

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque
from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate

def solve():
    N, K = MI()
    A = LI()
    for i in range(K):
        B = [0] * N
        for idx, a in enumerate(A):
            l = max(0, idx - a)
            r = idx + a + 1
            # print(idx, a, l, r)
            B[l] += 1
            if N > r:
                B[r] -= 1
        # print(B)
        B = list(accumulate(B))
        # print(B)
        if all([j == N for j in B]):
            printlist(B)
            return
        A = B
    printlist(A)

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
# original submission: https://atcoder.jp/contests/tokiomarine2020/submissions/14259812
import math
N, K = map(int, input().split())
A = list(map(int, input().split()))

if K > 4 * math.log2(N):
    for _ in range(N):
        print(N," ", end = "")
    print()
else:
    cum_sum = [0]*N
    for i in range(K):
        for i in range(N):
          cum_sum[i] = 0
        for j in range(N):
            left = j - A[j]
            right = j + A[j]
            cum_sum[left if left >= 0 else 0] += 1
            if right + 1 < N:
                cum_sum[right+1] -= 1
        A[0] = cum_sum[0]
        for j in range(N-1):
            cum_sum[j+1] += cum_sum[j]
            A[j+1] = cum_sum[j+1]
            
    for i in range(N):
        print(A[i], " ", end = "")
    print()

Submission status: Time Limit Exceeded

Solution code:
# C - Lamps
# imos法, 累積和

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

for _ in range(K):
    B = [0] * (N+1)
    for i, a in enumerate(A):
        left = max(0, i-a)
        right = min(i+a+1, N)
        B[left] += 1
        B[right] -= 1
    for i in range(N):
        B[i+1] += B[i]
    B.pop()
    if A == B:
        break
    else:
        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):
    nxt = [0]*n
    for j in range(n):
        r = min(n-1,j+a[j])
        l = max(j-a[j],0)
        nxt[l] += 1
        if r+1 < n:
            nxt[r+1] -= 1
    b = [0]*n
    b[0] = nxt[0]
    for j in range(1,n):
        b[j] = nxt[j]+b[j-1]
    a,b = b,a
    if a == b:
        break
print(*a)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,k,*a=map(int,open(0).read().split())
for _ in range(k):
  b=np.zeros(n+1,dtype=int)
  for i,c in enumerate(a):
    b[max(0,i-c)]+=1
    b[min(n,c+i+1)]-=1
  b=np.cumsum(b,dtype=int)
  a=b[:-1]
  if all(a==n):
    print(*a)
    exit()
print(*a)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
lamps = list(map(int,input().split()))
for ki in range(k):
    lamplog = [0]*(n+1)
    for i in range(n):
        lamplog[max(0,i-lamps[i])  ] += 1   #先端を出す
        lamplog[min(i+lamps[i]+1,n)] -= 1   #末尾を出す
    # print(lamplog)
    for i in range(n):                      #累積和を計算
        lamplog[i+1] += lamplog[i]
    # print(lamplog)
    lamplog.pop()
    if(lamplog == lamps):                   #１つ前の結果と今回の結果が同じだったら。
        break
    lamps = lamplog                         #今回の結果を記録

ans = ""
for i in range(len(lamplog)):
    ans += str(lamplog[i]) +" "
print(ans.rstrip())

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
# import copy


def xnxn(n=0, flag="v"):
    """
    args:
        int n: a number of lows to read
    example:
        input   1
        retrun  1

        input   1 2 3
        return  [1,2,3]
        input   1 2 3
                4 
        return  [[1,2,3],
                [4]]
    """
    if n == 0:
        temp = list(map(int, input().split()))
        if len(temp) == 1:
            if flag == "l":
                return temp
            else:
                return temp[0]
        elif len(temp) > 1:
            return temp
    else:
        temp = [list(map(int, input().split())) for _ in range(n)]
        return temp


n, k = xnxn()
a = xnxn(flag="l")
for _ in range(k):
    tmp = [0]*(n+1)
    for i in range(0, n):
        l = max(0, i - a[i])
        r = min(n, i + a[i]+1)
        tmp[l] += 1
        tmp[r] -= 1
    for i in range(1, n):
        tmp[i] += tmp[i - 1]
    if a == tmp:
        break
    a = tmp

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

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = [0] + list(map(int, input().split()))
from math import log
mx = min(int(log(K)) + 10**4, K)
for _ in range(mx):
    left_right = [0] + [(i-A[i], i+A[i]) for i in range(1, N+1)]
    ini = [0]*(N+1)
    for i in range(1, 1+N):
        l, r = left_right[i]
        l = max(1, l)
        ini[l] += 1
        if r+1 <= N:
            ini[r+1] -= 1
    A[1] = ini[1]
    for i in range(2, N+1):
        A[i] = A[i-1] + ini[i]
print(*A[1:])

Submission status: Time Limit Exceeded

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

import numpy as np

for kaisu in range(K):
	f0=np.array([0]*N)
	for i in range(N):
		binary_ls=[0]*max(0,i-a_ls[i])+[1]*(N-max(0,i-a_ls[i])-max(N-1-i-a_ls[i],0))+[0]*max(N-1-i-a_ls[i],0)
		f1=np.array(binary_ls)
		f0+=f1
	
	a_ls=f0.tolist()
	if a_ls==[N]*N:
		break


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


# 2darray [[0] * 4 for i in range(3)]

Submission status: Time Limit Exceeded

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

import sys
import copy

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


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


    one_list = [0] * n

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

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

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

            #print(lamped_list)

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

        flag = True
        for i in a_list:
            if i != n:
                flag = False
                break
        if flag:
            print(*a_list)
            exit()


    print(*a_list)









if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
# import copy


def xnxn(n=0, flag="v"):
    """
    args:
        int n: a number of lows to read
    example:
        input   1
        retrun  1

        input   1 2 3
        return  [1,2,3]
        input   1 2 3
                4 
        return  [[1,2,3],
                [4]]
    """
    if n == 0:
        temp = list(map(int, input().split()))
        if len(temp) == 1:
            if flag == "l":
                return temp
            else:
                return temp[0]
        elif len(temp) > 1:
            return temp
    else:
        temp = [list(map(int, input().split())) for _ in range(n)]
        return temp


n, k = xnxn()
a = xnxn(flag="l")
for _ in range(k):
    tmp = [0]*(n+1)
    for i in range(0, n):
        l = max(0, i - a[i])
        r = min(n, i + a[i]+1)
        tmp[l] += 1
        tmp[r] -= 1
    for i in range(1, n):
        tmp[i] += tmp[i - 1]

    if a == tmp:
        break
    a = tmp

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

Submission status: Time Limit Exceeded

Solution code:
# original submission: https://atcoder.jp/contests/tokiomarine2020/submissions/14259812
import math
N, K = map(int, input().split())
A = list(map(int, input().split()))

if K > 4 * math.log2(N):
    for _ in range(N):
        print(N," ", end = "")
    print()
else:
    for i in range(K):
        cum_sum = [0]*N
        for j in range(N):
            left = max(0, j - A[j])
            right = min(N-1, j+A[j])
            cum_sum[left] += 1
            if right + 1 < N:
                cum_sum[right+1] -= 1
        A[0] = cum_sum[0]
        for j in range(N-1):
            cum_sum[j+1] += cum_sum[j]
            A[j+1] = cum_sum[j+1]

            
    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()]
d=[0 for i in range(n)]
c=1
k=min(k,40)


while c<=k:
    b=list(d)
    e=float("inf")
    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]
        e=max(e,b[i-1])
    c+=1
    a=b
    if e==n:
        break
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 _ in range(k):
    imos = [0] * (n + 1)
    for i in range(n):
        imos[max(0, i - a[i])] += 1
        imos[min(n, i + a[i] + 1)] -= 1
    for i in range(1, n):
        imos[i] += imos[i-1]
    imos.pop()
    a = imos
    if min(a) == n:
        break 
print(*a)