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:
# imos法
# 長さNの1次元配列において、「ある連続する区間に、ある数vを足す」という操作をK回繰り返した結果を高速で求める

# 初期入力
import sys
input = sys.stdin.readline
N,K = (int(i) for i in input().split())
A = list(map(int, input().split()))


l =0
r =N
cumulative_sum =[0]*N
#操作数が電球の数より多いとき
if N <=K:
    A=[N]*N
# imos法
else:
    for j in range(K):
        B =[0]*(N+1)
        for i in range(N):
            index =A[i]
            if i-index <0:
                l=0
            else:
                l =i -index
            if i +index +1 >=N:
                r =N 
            else:
                r =i +index +1
            B[l] +=1 
            B[r] -=1
        #累積和(imos法) 
        cumulative_sum[0] =B[0]       
        for i in range(1,N):
            cumulative_sum[i] =cumulative_sum[i-1] +B[i]

        A =cumulative_sum
        if sum(A) ==N*N:
            print(*A)
            sys.exit(0)
        cumulative_sum =[0]*N
    
print(*A)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit

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

fin = np.array([N] * N)


@njit(cache=True)
def calc_b(a):
    b = np.array([0] * N)
    for i in range(N):
        l = max(0, i - a[i])
        r = min(N - 1, i + a[i])

        for j in range(l, r + 1):
            b[j] += 1
    return b


for k in range(K):
    a = calc_b(a)

    if all(a == fin):
        break

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

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    for x in range(k if k < 30 else 30):
        B = [0] * n
        for j in range(n):
            l = max(0, j - A[j])
            r = min(n - 1, j + A[j])
            B[l] += 1
            if r + 1 < n:
                B[r + 1] -= 1

        for x in range(1, n):
            B[x] += B[x - 1]
        A = B

    print(*A)


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

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

for k in range(42):
    A=T[::]
    L=[0 for _ in range(N)]
    R=[0 for _ in range(N)]
    for i in range(N):
        l=(i+1)-A[i]-0.5
        r=(i+1)+A[i]+0.5
        l=int(l+0.999)
        r=int(r)
        l-=1
        if l<0:
            l=0
        L[l]+=1
        if r>=N:
            continue
        R[r]+=1

    #print(L)
    #print(R)
    T=[0 for _ in range(N)]
    T[0]=L[0]
    for i in range(N-1):
        T[i+1]=T[i]+L[i+1]-R[i+1]
    #print(T)
    if (k+1)==K:
        break 

print(*T)

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import defaultdict

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


def left_right(x, d):
    left = x - d - 0.5
    right = x + d + 0.5
    return left, right


printed_lst = []
for x in range(K):
    dic = defaultdict(int)
    for i in range(N):
        l, r = left_right(i + 1, al[i])
        left = math.ceil(l)
        if left <= 0:
            left = 1
        right = math.floor(r)
        for n in range(left, right + 1):
            dic[n] += 1
    al = list(dic.values())[:N]
    #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]))

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = [int(i) for i in input().split()]
for j in range(min(k, 42)):
    bit = [0 for _ in range(n)]
    for i in range(n):
        bit[max(i - a[i], 0)] += 1
        if i + a[i] + 1 < n:
            bit[i + a[i] + 1] -= 1
    result = [bit[0]]
    for i in range(n - 1):
        result.append(bit[i + 1] + result[-1])
    a = result
print(' '.join(list(map(str, a))))

Submission status: Time Limit Exceeded

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

for _ in range(K):
    A=T[::]
    L=[0 for _ in range(N)]
    R=[0 for _ in range(N)]
    for i in range(N):
        l=(i+1)-A[i]-0.5
        r=(i+1)+A[i]+0.5
        l=int(l+0.999)
        r=int(r)
        l-=1
        if l<0:
            l=0
        L[l]+=1
        if r>=N:
            continue
        R[r]+=1

    #print(L)
    #print(R)
    T=[0 for _ in range(N)]
    T[0]=L[0]
    for i in range(N-1):
        T[i+1]=T[i]+L[i+1]-R[i+1]
    #print(T)

print(*T)

Submission status: Time Limit Exceeded

Solution code:
# import math

N, K = map(int, input().split())
# if K >= 1000 and N / 2 + 1 < K:
#     K = int(math.sqrt(N))
# if K >= 50:
#     K = 50
A_list = list(map(int, input().split()))

A_New_list = [0 for i in range(N)]
for k in range(K):
    for i in range(N):
        if i - A_list[i] <= 0:
            A_New_list[0] += 1
        else:
            A_New_list[i - A_list[i]] += 1
        if i + A_list[i] + 1 < N:
            A_New_list[i + A_list[i] + 1] -= 1
    for i in range(1,N):
        A_New_list[i] += A_New_list[i-1]
    A_list = A_New_list
    if k != K - 1:
        A_New_list = [0 for n in range(N)]
A_New_list = [str(a) for a in A_New_list]
ans = " ".join(A_New_list)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

N, K = map(int, input().split())
# if K >= 1000 and N / 2 + 1 < K:
#     K = int(math.sqrt(N))
if K >= 50:
    K = 50
A_list = list(map(int, input().split()))

A_New_list = [0 for i in range(N)]
for k in range(K):
    for i in range(N):
        if i - A_list[i] <= 0:
            A_New_list[0] += 1
        else:
            A_New_list[i - A_list[i]] += 1
        if i + A_list[i] + 1 < N:
            A_New_list[i + A_list[i] + 1] -= 1
    for i in range(1,N):
        A_New_list[i] += A_New_list[i-1]
    A_list = A_New_list
    if k != K - 1:
        A_New_list = [0 for n in range(N)]
A_New_list = [str(a) for a in A_New_list]
ans = " ".join(A_New_list)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k,*l=map(int,open(0).read().split())
for _ in range(k):
  s=[0]*(n+1)
  for i in range(n):
    s[max(i-l[i],0)]+=1
    s[min(i+l[i]+1,n)]-=1
  s[0]=min(s[0],n)
  for i in range(1,n):
    s[i]=min(s[i-1]+s[i],n)
  if s==l[:n]: break
  l=s[:n]
print(*l)

Submission status: Time Limit Exceeded

Solution code:
#東京海上日動　プログラミングコンテスト2020 c
n,k  = map(int, input().split())
ln  = list(map(int, input().split()))
import numpy as np
ln = np.array(ln)
def lamps(ln):
    line = [0 for i in range(n)]
    line = np.array(line)
    for i in range(n):
        small = max(0, i - ln[i])
        large = min(i + ln[i],  n-1)
        line[small : i] += 1
        line[i + 1 : large +1] += 1
    line +=1
        
    return line
for n1 in range(k):
    if min(ln) >= n:
        break
    ln = lamps(ln)
print(*ln)

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import defaultdict

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


def left_right(x, d):
    left = x - d - 0.5
    right = x + d + 0.5
    return left, right

printed = set()
printed_lst = []
bl = []
for x in range(K):
    dic = defaultdict(int)
    for i in range(N):
        l, r = left_right(i + 1, al[i])
        left = math.ceil(l)
        if left <= 0:
            left = 1
        right = math.floor(r)
        for n in range(left, right + 1):
            dic[n] += 1
    al = list(dic.values())[:N]
    bl = [str(i) for i in al]
    bls = ''.join(bl)
    #print(bls)
    printed.add(bls)
    printed_lst.append(bls)
    if len(printed) != len(printed_lst):
        print(bls)
        exit()

print(' '.join(bl))

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+2)
    for j in range(n):
        b[max(0,j-a[j]+1)]+=1
        b[min(n+1, j+a[j]+2)]-=1
    for j in range(n):
        b[j+1]+=b[j]
    if a==b[1:n+1]:
        break
    else:
        a=b[1:n+1]
for i in a:
    print(i,end=" ")

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def draft(A, K, N):
    for _ in range(1, K+1):# 2 * 10**5
        tmp = np.zeros(N, dtype=np.int64)
        for i in range(N):# 2 * 10**5
            L = i - A[i]
            R = i + A[i] + 1
            if L < 0:
                tmp[0] += 1
            else:
                tmp[L] += 1
            if R < N:
                tmp[R] -= 1
        A = np.cumsum(tmp)
        if not np.count_nonzero(A < N) > 0:
            break
    for i in range(N):
        print(int(A[i]), end=" ")

def main():
    N, K = map(int, input().split())
    A = np.array(input().split(), dtype=np.int64)
    draft(A, K, N)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
b = [0]*(n+2)
S=sum(a)
for i in range(k):
    s=S
    S=0
    for j in range(n):
        if j<a[j]:
            b[0]+=1
        else:
            b[j-a[j]+1]+=1
        if n-1-j<a[j]:
            b[n+1]-=1
        else:
            b[j+a[j]+2]-=1
    for j in range(n):
        if j==0:
            a[j] = b[j]+b[j+1]
        else:
            a[j] = a[j-1]+b[j+1]
        b[j]=0
        S+=a[j]
    b[-2]=0
    b[-1]=0
    if S==s:
        break
for i in a:
    print(i,end=" ")

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


N, K = map(int, input().split())
A = np.array(input().split(), dtype=int)
for k in range(K):
    B = np.zeros(N + 1, dtype=int)
    for i in range(N):
        a = A[i]
        B[max(0, i - a)] += 1
        B[min(N, i + a + 1)] -= 1
    A = np.cumsum(B)[:-1]
    if np.all(A == N):
        break
print(' '.join(map(str, A)))

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

Submission status: Time Limit Exceeded

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

def update(n, A):
    B = [0]*n
    for i in range(n):
        B[max(0, i-A[i])] += 1
        if i+A[i]+1 < n:
            B[i+A[i]+1] -= 1
    for i in range(1,n):
        B[i] += B[i-1]
    return B

for _ in range(k):
    A = update(n, A)
    if A[0] == n and len(set(A)) == 1:
        break
print(*A)

Submission status: Time Limit Exceeded

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

def solve(k,n,a):
    for _ in range(k):
        Y = [0]*(n+1)
        for i, x in enumerate(a):
            Y[max(0, i-x)] += 1
            Y[min(n, i+x+1)] -= 1
        for j in range(1, n):
            Y[j] += Y[j-1]
        if a == Y[:-1]:
            break
        a = Y[:-1]
    return a

ans=solve(K,N,A)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def draft(A, K, N):
    K = min(K, 20)
    for _ in range(1, K+1):# 2 * 10**5
        tmp = np.zeros(N, dtype=np.int64)
        for i in range(N):# 2 * 10**5
            L = i - A[i]
            R = i + A[i] + 1
            if L < 0:
                tmp[0] += 1
            else:
                tmp[L] += 1
            if R < N:
                tmp[R] -= 1
        A = np.cumsum(tmp)
    for i in range(N):
        print(int(A[i]), end=" ")

def main():
    N, K = map(int, input().split())
    A = np.array(input().split(), dtype=np.int64)
    draft(A, K, N)

if __name__ == "__main__":
    main()

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.log10(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
    ls = new
print(*ls)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
b = [0]*(n+2)
S=sum(a)
for i in range(k):
    s=S
    for j in range(n):
        if j<a[j]:
            b[0]+=1
        else:
            b[j-a[j]+1]+=1
        if n-1-j<a[j]:
            b[n+1]-=1
        else:
            b[j+a[j]+2]-=1
    for j in range(n):
        if j==0:
            a[j] = b[j]+b[j+1]
        else:
            a[j] = a[j-1]+b[j+1]
        b[j]=0
    b[-2]=0
    b[-1]=0
    S=sum(a)
    if S==s:
        break
for i in a:
    print(i,end=" ")

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env pypy3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)

def main():
    N, K = LI()
    A = LI()

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

        if A == B:
            break
        A = B
    print(*A[:-1], sep=" ")
main()

Submission status: Time Limit Exceeded

Solution code:
import copy
import sys
import math

def main():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    B = [0] * n

    # k_max = 1 + math.ceil(math.log10(n))

    for i in range(min(k, 41)):
        for j in range(n):
            l = max(0, j-A[j]) #座標iの電球が照らす範囲の左端
            r = min(n-1, j+A[j]) #座標iの電球が照らす範囲の右端
            B[l] += 1
            if (r+1 < n):
                B[r+1] -= 1 # 後ほど累積和にしたときに、照らす範囲の右端より外には影響が及ばないようにあらかじめ1引いておく

        for j in range(n-1):
            B[j+1] += B[j]

        A = copy.deepcopy(B)
        B = [0] * n

    print(*A)

if __name__ == '__main__':
    main()

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 k in range(K):
    B_acc = np.zeros(N + 1, dtype=int)
    for i in range(N):
        a = A[i]
        B_acc[max(0, i - a)] += 1
        B_acc[min(N, i + a + 1)] -= 1
    B_acc = np.cumsum(B_acc)
    A = B_acc[:-1]
    if all(a == N for a in A):
        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):
    Y = [0]*(n+1)
    for i, x in enumerate(a):
        Y[max(0, i-x)] += 1
        Y[min(n, i+x+1)] -= 1
    for j in range(1, n):
        Y[j] += Y[j-1]
    if a == Y[:-1]:
        break
    a = Y[:-1]
print(*a)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def draft(A, K, N):
    A = np.array(A)
    K = min(K, 20)
    for _ in range(1, K+1):# 2 * 10**5
        tmp = np.zeros(N, dtype=np.int64)
        for i in range(N):# 2 * 10**5
            L = i - A[i]
            R = i + A[i] + 1
            if L < 0:
                tmp[0] += 1
            else:
                tmp[L] += 1
            if R < N:
                tmp[R] -= 1
        A = np.cumsum(tmp)
    for i in range(N):
        print(int(A[i]), end=" ")

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

for i in range(K):
    table = [0 for _ in range(N*2)]
    # imos法 - メモ
    for j in range(N):
        ai = As[j]
        # 電球が照らす左端をメモ
        table[max((j-ai)*2-1, 0)] += 1
        # 電球が照らす右端をメモ
        table[min((j+ai)*2+1, N*2-1)] -= 1
    
    # imos法 - シミュレート
    for j in range(N*2):
        if j > 0:
            table[j] += table[j-1]
    
    # 答えになおす
    for j in range(N):
        As[j] = table[j*2]
    
    exit_condition = True
    for j in range(N):
        if As[j] != N:
            exit_condition = False
            break
    
    if exit_condition:
        print(*As)
        exit(0)
            

print(*As)

Submission status: Time Limit Exceeded

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

n,k=map(int,input().split())
dp2=list(map(int,input().split()))
    
k=min(k,41)
for ki in range(1,k+1):
    ims=[0]*(n+1)
    for ni in range(n):
        if ni<dp2[ni]: ims[0]+=1
        else: ims[ni-dp2[ni]]+=1
        if n>ni+dp2[ni]:
            ims[ni+dp2[ni]+1]-=1

    dp2[0]=ims[0]
    for ni in range(1,n):
        dp2[ni]=dp2[ni-1]+ims[ni]
    
print(' '.join(map(str,dp2)))

Submission status: Time Limit Exceeded

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

def update(n, 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]
    return B

k = 41 if k>41 else k
for _ in range(k):
    A = update(n, A)
s = [str(x) for x in A]
print(' '.join(s))

Submission status: Time Limit Exceeded

Solution code:
import copy
import sys
import math

def main():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    B = [0] * n

    k_max = 1 + math.ceil(math.log2(n))

    for i in range(min(k, k_max)):
        for j in range(n):
            l = max(0, j-A[j]) #座標iの電球が照らす範囲の左端
            r = min(n-1, j+A[j]) #座標iの電球が照らす範囲の右端
            B[l] += 1
            if (r+1 < n):
                B[r+1] -= 1 # 後ほど累積和にしたときに、照らす範囲の右端より外には影響が及ばないようにあらかじめ1引いておく

        for j in range(n-1):
            B[j+1] += B[j]

        A = copy.deepcopy(B)
        B = [0] * n

    print(*A)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
input = sys.stdin.readline

def draft(A, K, N):
    A = np.array(A)
    K = min(K, 20)
    for _ in range(1, K+1):# 2 * 10**5
        tmp = np.zeros(N, dtype=np.int64)
        for i in range(N):# 2 * 10**5
            L = i - A[i]
            R = i + A[i] + 1
            if L < 0:
                tmp[0] += 1
            else:
                tmp[L] += 1
            if R < N:
                tmp[R] -= 1
        A = np.cumsum(tmp)
    for i in range(N):
        print(int(A[i]), end=" ")

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

from itertools import accumulate

for j in range(min(k,50)):
    for i in range(n):
        b[max(0,i-a[i])]+=1
        b[min(n,i+a[i]+1)]+=-1
    a = list(accumulate(b))[:n]
    b = [0 for i in range(n+1)]

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

Submission status: Time Limit Exceeded

Solution code:
#東京海上日動　プログラミングコンテスト2020 c
n,k  = map(int, input().split())
ln  = list(map(int, input().split()))
import numpy as np
ln = np.array(ln)
from numba import jit
@jit
def lamps(ln):
    line = [0 for i in range(n)]
    line = np.array(line)
    for i in range(n):
        small = i - ln[i]
        large = i + ln[i]
        if small < 0:
            small = 0
        if large > n -1:
            large = n-1
        line[small : i] += 1
        line[i + 1 : large +1] += 1
    line +=1
        
    return line
for n1 in range(k):
    if min(ln) >= n:
        break
    ln = lamps(ln)
for i in ln:
  print(i, end = ' ')

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from copy import deepcopy
import sys
input = sys.stdin.readline

def draft(A, K, N):
    A = np.array(A)
    K = min(K, 20)
    for _ in range(1, K+1):# 2 * 10**5
        tmp = np.zeros(N+1, dtype=np.int64)
        for i in range(N):# 2 * 10**5
            L = max(0, i - A[i])
            R = min(N, i + A[i]+1)
            tmp[L] += 1
            tmp[R] -= 1
        A = np.cumsum(tmp)[:-1]
    for i in range(N):
        print(int(A[i]), end=" ")

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np

n,k=(int(x) for x in input().split())
a = [int(x) for x in input().split()]


for _ in range(k):
    new_a = []
    c = 0
    a_in = np.maximum(0,np.arange(0, n)-a)
    a_out = np.minimum(n,np.arange(0, n)+a)
    
    for x in np.arange(0,n):
        c += np.count_nonzero(a_in == x)
        c -= np.count_nonzero(a_out+1 == x)
        new_a.append(c)
    a = new_a
    if np.all(a==n):
        break

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

Submission status: Time Limit Exceeded

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

    for _ in range(k):
        imos = [0]*(n+1)
        finish = True
        for i, brightness in enumerate(a):
            if finish and brightness != n:
                finish = False
            begin = max(i - brightness, 0)
            end = i + brightness
            imos[begin] += 1
            if end < n:
                imos[end + 1] -= 1
        if finish:
            break
        for i in range(n-1):
            imos[i+1] += imos[i]
        a = imos[:-1]
    print(*a, sep=" ")


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

da=[0 for i in range(N)]
for k 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]=B[l]+1
        if(r+1<N):
            B[r+1]=B[r+1]-1
    for i in range(1,N):
        B[i]=min(N,B[i]+B[i-1])
    A=B
b=[str(i) for i in B]
b=" ".join(b)
print(b)

Submission status: Time Limit Exceeded

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

for k in range(K):
    if all(A) == N:
        break
    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
    
    ruiseki = [0] * N
    ruiseki[0] = B[0]
    for i in range(1,N):
        ruiseki[i] = ruiseki[i-1] + B[i]
        
    A = ruiseki[:]
print(*ruiseki,sep=" ")

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from copy import deepcopy
def draft(A, K, N):
    A = np.array(A)
    K = min(K, 50)
    for _ in range(1, K+1):# 2 * 10**5
        tmp = np.zeros(N+1, dtype=np.int64)
        for i in range(N):# 2 * 10**5
            L = max(0, i - A[i])
            R = min(N, i + A[i]+1)
            tmp[L] += 1
            tmp[R] -= 1
        A = np.cumsum(tmp)[:-1]
    for i in range(N):
        print(int(A[i]), end=" ")

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
n,k = map(int,input().split())
ls = list(map(int,input().split()))
if n >=5000 and k >n/100:
    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
    ls = new
print(*ls)

Submission status: Time Limit Exceeded

Solution code:
#東京海上日動　プログラミングコンテスト2020 c
n,k  = map(int, input().split())
ln  = list(map(int, input().split()))
import numpy as np
ln = np.array(ln)
def lamps(ln):
    line = [0 for i in range(n)]
    line = np.array(line)
    for i in range(n):
        small = i - ln[i]
        large = i + ln[i]
        if small < 0:
            small = 0
        if large > n -1:
            large = n-1
        line[small : i] += 1
        line[i + 1 : large +1] += 1
    line +=1
        
    return line
for n1 in range(k):
    if min(ln) >= n:
        break
    ln = lamps(ln)
for i in ln:
  print(i, end = ' ')

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import accumulate
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))

def main():
    n,k = map(int,sys.stdin.readline().rstrip().split())
    a = LI()
    for _ in range(k):
        table = [0]*(n+1)
        for i,x in enumerate(a):
            table[max(0,i-x)] += 1
            table[min(n-1,i+x)+1] -=1
        a = list(accumulate(table))[:-1]
    print(*a)
    return

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from numba import jit

@jit
def f(lst):
    for n in range(N):
        L = max(0, n-lst[n])
        R = min(N-1 , n + lst[n])
        B[L] += 1
        if R+1 != N:
            B[R+1] -= 1
    return B     
    
@jit
def f2(lst):
    for i in range(1,N):
        ruiseki[i] = ruiseki[i-1] + lst[i]
    return ruiseki    

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

for k in range(K):
    if all(A) == N:
        break
    B = [0] * N
    B = f(A)
   
    ruiseki = [0] * N
    ruiseki[0] = B[0]
    A = f2(B)
print(*ruiseki,sep=" ")

Submission status: Time Limit Exceeded

Solution code:
import sys
n,k = map(int,input().split())
ls = list(map(int,input().split()))
if n >=1000 and k >n/20:
    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
    ls = new
print(*ls)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from copy import deepcopy
def draft(A, K, N):
    A = np.array(A)
    for _ in range(1, K+1):# 2 * 10**5
        tmp = np.zeros(N+1, dtype=np.int64)
        for i in range(N):# 2 * 10**5
            L = max(0, i - A[i])
            R = min(N, i + A[i]+1)
            tmp[L] += 1
            tmp[R] -= 1
        A = np.cumsum(tmp)[:-1]
        if not np.count_nonzero(A < N) > 0:
            break
    for i in range(N):
        print(int(A[i]), end=" ")

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    for k in range(K):
        A_temp=[0]*N
        for i,data in enumerate(A):
            for j in range(max(0,i-data),min(N,i+data+1)):
                A_temp[j]+=1
        A=A_temp
        for ai in A:
            if ai != N:
                break
        else:
            break
                
    print(*A)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

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

current_arr = A
for k in range(K):
    if k > 41:
        break
    imos = [0] * N
    ruiseki = [0] * (N+1)
    for i, ai in enumerate(current_arr):
        imos[max([0, i-ai])] += 1
        if i+ai+1 < N:
            imos[i+ai+1] -= 1
    for j, im in enumerate(imos):
        ruiseki[j+1] = ruiseki[j] + im
    current_arr = ruiseki[1:]
#print(imos)
#print(ruiseki)
#print(*accumulate(imos))
print(*current_arr)

Submission status: Time Limit Exceeded

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

if K >= N - 1:
    ans = [N] * N
    print(*ans)

else:
    for i in range(K):
        tmp = [0] * (N + 1)
        for j in range(N):
            
            end_l = max(j - A[j], 0)
            end_r = min(j + A[j] + 1, N)
            tmp[end_l] += 1
            tmp[end_r] -= 1

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

    print(*A[:N])