Problem:


Score : 500 points

Problem Statement

We have N bulbs arranged on a number line, numbered 1 to N from left to right.
Bulb i is at coordinate i.

Each bulb has a non-negative integer parameter called intensity.
When there is a bulb of intensity d at coordinate x, the bulb illuminates the segment from coordinate x-d-0.5 to x+d+0.5.
Initially, the intensity of Bulb i is A_i. We will now do the following operation K times in a row:

For each integer i between 1 and N (inclusive), let B_i be the number of bulbs illuminating coordinate i. Then, change the intensity of each bulb i to B_i.

Find the intensity of each bulb after the K operations.

Constraints

1 \leq N \leq 2 \times 10^5

1 \leq K \leq 2 \times 10^5

0 \leq A_i \leq N

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 \ldots A_N

Output

Print the intensity A{'}_i of each bulb i after the K operations to Standard Output in the following format:

A{'}_1 A{'}_2 \ldots A{'}_N

Sample Input 1

5 1
1 0 0 1 0

Sample Output 1

1 2 2 1 2 

Initially, only Bulb 1 illuminates coordinate 1, so the intensity of Bulb 1 becomes 1 after the operation.
Similarly, the bulbs initially illuminating coordinate 2 are Bulb 1 and 2, so the intensity of Bulb 2 becomes 2.

Sample Input 2

5 2
1 0 0 1 0

Sample Output 2

3 3 4 4 3 



Sample input:
5 1
1 0 0 1 0


Sample output:
1 2 2 1 2

Submission status: Time Limit Exceeded

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

def calc(a):
    for t in range(k):
        b = [0] * n
        for i in range(n):
            for j in range(n):
                if a[j] >=  abs(j - i):
                    b[i] += 1

        for i in range(n):
            if(max(n-i,i) > b[i]):
                break
            for j in range(n):
                a[j] += n *(k-t)
            return a
        a = b
    return a

a = calc(a)
for i in a:
    print(i,end=" ")

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
b =  [set([i]) for i in range(n)]
for _ in range(k):
  b = [0]*n
  for i in range(n):
    for j in range(max(0,i-a[i]),min(i+a[i]+1,n)):
      b[j]+=1
  a = b
print(' '.join([str(v) for v in a]))

Submission status: Time Limit Exceeded

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


def query(lamps):
    start_list = []
    end_list = []
    for idx, power in enumerate(lamps):
        start, end = idx - power, idx + power
        start_list.append(start)
        end_list.append(end)

    counts = [0] * n
    start_list.sort(reverse=True)
    end_list.sort(reverse=True)

    now = 0
    for idx in range(n):
        while start_list and start_list[-1] <= idx:
            start_list.pop()
            now += 1

        while end_list and end_list[-1] < idx:
            end_list.pop()
            now -= 1

        counts[idx] = now

    return counts


def full_check(counts, full):
    for count in counts:
        if count == full:
            continue
        else:
            return False

    return True


for _ in range(k):
    A = query(A)
    if full_check(A, n):
        break

print(*A)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

n, k = [int(x) for x in stdin.readline().rstrip().split()]
intense_counters = [0]
dd = [int(x) for x in stdin.readline().rstrip().split()]
intense_counters.extend(dd)


for times in range(k):
    new_intense_counters = [0] * (n+1)
    for i, intense in enumerate(intense_counters):
        if i == 0:
            continue

        min = i - intense
        max = i + intense

        for lighted_position in range(min, max+1):
            if 0 < lighted_position and lighted_position <= n:
                new_intense_counters[lighted_position] += 1
    intense_counters = new_intense_counters

print(" ".join(list(map(str, intense_counters[1:]))))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def get_add_arr(n, k, a):
  base = np.zeros(n, int)
  min_pos = max(k - a, 0)
  max_pos = min(n+1, k + a + 1)
  base[min_pos:max_pos] = 1
  
  return base

def main():
  n, k = map(int, input().split())
  a_arr = np.array(list(map(int, input().split())))
  for i in range(k):
    tmp_a_arr = np.zeros(n, int)
    for i in range(n):
      a = a_arr[i]
      tmp_a_arr += get_add_arr(n, i, a)
    a_arr = tmp_a_arr
  print(' '.join(str(x) for x in a_arr))
     
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = input().split()
a = [int(a[i]) for i in range(len(a))]
c = [0]*n
for m in range(k):
    for i in range(n):
        b = [a[j]-abs(j-i) for j in range(len(a))]
        c[i] = sum(1 for x in b if x >=0)
    a = []
    a += c
a = [str(aa) for aa in a]
print(' '.join(a))

Submission status: Time Limit Exceeded

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

for i in range(K):
    tmpA = [1 for i in range(N)]
    tmpB = []
    for j in range(N):
        tmpA[j] += len(tmpB)
        tmpB = list(filter(lambda x:x, map(lambda x:x-1, tmpB)))
        if A[j]:
            tmpB.append(A[j])

    
    tmpB = []
    for j in range(N - 1, -1 ,-1):
        tmpA[j] += len(tmpB)
        tmpB = list(filter(lambda x:x, map(lambda x:x-1, tmpB)))
        if A[j]:
            tmpB.append(A[j])
            
    A = tmpA

[print(i, end=' ') for i in A]
print()

Submission status: Time Limit Exceeded

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

t = 0
while t < k:
  tmpds = [0] * n
  i = 0
  while i < n:
    j = max(i - ds[i], 0)
    while j <= i + ds[i]:
      if j >= n:
        break
      tmpds[j] += 1
      j += 1
    i += 1
  ds = tmpds.copy()
  t += 1

dsstr = map(str, ds)
ans = " ".join(dsstr)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K = list(map(int,input().split()))
A = list(map(int,input().split()))
for k in range(K):
    B = [0 for i in A]
    for j in range(max(A)+1):
        for i in range(N):
            if A[i] > 0:
                if i+A[i] < N:
                    B[i+A[i]] += 1
                if i-A[i] >= 0:
                    B[i-A[i]] += 1
                A[i] -= 1
            if A[i] == 0:
                B[i] += 1
                A[i] -= 1
    A = [b for b in B]
B = [str(b) for b in B]
print(' '.join(B))

Submission status: Time Limit Exceeded

Solution code:
class A:

    def solve(self):
        name = input()
        print(name[:3])

class B:

    def solve(self):
        [a, v] = [int(x) for x in input().split(" ")]
        [b, w] = [int(x) for x in input().split(" ")]
        t = int(input())

        if a == 0:
            if b < 0:
                a_end = a - t * v
                b_end = b - t * w

                if a_end <= b_end:
                    print("YES")
                else:
                    print("NO")
            else:
                a_end = a + t * v
                b_end = b + t * w

                if a_end >= b_end:
                    print("YES")
                else:
                    print("NO")
        elif b == 0:
            if a > 0:
                a_end = a - t * v
                b_end = b - t * w

                if a_end <= b_end:
                    print("YES")
                else:
                    print("NO")
            else:
                a_end = a + t * v
                b_end = b + t * w

                if a_end >= b_end:
                    print("YES")
                else:
                    print("NO")
        elif a > 0 and b < 0:
            a_end = a - t * v
            b_end = b - t * w

            if a_end <= b_end:
                print("YES")
            else:
                print("NO")
        elif a < 0 and b > 0:
            a_end = a + t * v
            b_end = b + t * w

            if a_end >= b_end:
                print("YES")
            else:
                print("NO")
        elif a < 0 and b < 0:
            if a < b:
                a_end = a + t * v
                b_end = b + t * w

                if a_end >= b_end:
                    print("YES")
                else:
                    print("NO")
            else:
                a_end = a - t * v
                b_end = b - t * v

                if a_end <= b_end:
                    print("YES")
                else:
                    print("NO")
        else:
            if b > a:
                a_end = a + t * v
                b_end = b + t * w

                if a_end >= b_end:
                    print("YES")
                else:
                    print("NO")
            else:
                a_end = a - t * v
                b_end = b - t * v

                if a_end <= b_end:
                    print("YES")
                else:
                    print("NO")

class C:

    def solve(self):
        [n, k] = [int(x) for x in input().split(" ")]
        intensities = [int(x) for x in input().split(" ")]

        for o in range(k):
            new_intensities = [0 for x in range(n)]

            for i in range(n):
                for e in range(max(0, i - intensities[i]), min(i + intensities[i] + 1, n)):
                    new_intensities[e] += 1

            intensities = new_intensities

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

C().solve()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,K=map(int, input().split())

A=list(map(int, input().split()))
K=min(K, 30)
for k in range(K):
    B=[0]*(N+1)
    for i in range(N):
        a=A[i]
        start=max(0,i-a)
        end=min(N,i+a+1)
        B[start]+=1
        B[end]-=1
    B=np.array(B)
    A=np.cumsum(B)[:N]
    if A.min()==N:
        break
    #print(B)
    
    
print(*A)

Submission status: Time Limit Exceeded

Solution code:
def plus(x):
    return x+1

n,k=map(int,input().split())
A=list(map(int,input().split()))
for j in range(k):
    B=[0]*n
    for i in range(n):
        B=B[0:max(0,i-A[i])]+list(map(plus,B[max(0,i-A[i]):min(n,i+A[i]+1)]))+B[min(n,i+A[i]+1):n]
    A=B.copy()
for i in range(n):
    B[i]=str(B[i])
print(' '.join(B))

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    A_temp=[0]*N
    for k in range(K):
        for i in range(N):
            for j in range(max(0,i-A[i]),min(N,i+A[i]+1)):
                A_temp[j]+=1
        A=A_temp
        A_temp=[0]*N
    print(' '.join(map(str,A)))
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

for i in range(k):
    b = a.copy()
    a = c.copy()
    for j in range(n):
        a[j] += 1
        for k in range(b[j]):
            if j-k-1 >= 0:
                a[j-k-1] += 1
            if j+k+1 < n:
                a[j+k+1] += 1
s = ""
for i in a:
    s = s + str(i) + " "

print(s[:-1])

Submission status: Time Limit Exceeded

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

for k in range(K):
  copy=[0]*N
  for i in range(N):
    kido=light[i]
    smin=max(0,i-kido)
    smax=min(N-1,i+kido)
    for j in range(smin, smax+1):
      copy[j]+=1
  light=copy
print(*light)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

##### dict の for文 #####
# for k, v in d.items():
#     print(k, v)

##### 進数の変換 #####
# bin_str = bin(i)[2:]
# oct_str = oct(i)[2:]
# hex_str = hex(i)[2:]

##### とても大きな数 と 小数の計算誤差 #####
# 「Decimal」は計算誤差を 0にできる。必要に応じて粒度を設定せよ。
# getcontext().prec = 100
#
# tmp = Decimal(i)
# A,B = map(Decimal, input().split())
# ans = A * B

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N,K = inputMap()
	A = inputList()

	for j in range(K):
		T = [0 for i in range(N)]
		for i,val in enumerate(A):
			#print(T)
			tmp_min = max(0,i-val)
			T[tmp_min] += 1

			if i+val+1 > N-1:
				continue
			tmp_max = min(N-1,i+val+1)
			T[tmp_max] -= 1

		for i,val in enumerate(T):
			if i == 0:
				continue
			T[i] += T[i-1]
		A = T

	print(*A)



def segfunc(x, y):
    return 0

ide_ele = float('inf')

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# 2分検索のリバース
def bisect_left_reverse(a, x):
    if a[0] <= x:
        return 0
    if x < a[-1]:
        return len(a)
    # 二分探索
    ok = len(a) - 1
    ng = 0
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if a[mid] <= x:
            ok = mid
        else:
            ng = mid
    return ok

def bisect_right_reverse(a, x):
    if a[0] < x:
        return 0
    if x <= a[-1]:
        return len(a)
    # 二分探索
    ok = len(a) - 1
    ng = 0
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if a[mid] < x:
            ok = mid
        else:
            ng = mid
    return ok

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# 2分検索
# 存在しない場合: None 存在する場合: その値
def binary_search(list, item):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) //2
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid -1
        else:
            low = mid + 1
    return None

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# N 個のボールを K グループに分ける場合のパターン数
def sunuke(N, K, mod=10**9+7):
	if N < K or K-1 < 0:
		return 0
	else:
		return combination(N-1, K-1, mod)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# dfs のサンプル
def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


n, k = inpl()
a = inpl()
dp = [(0, 0)] * n
for j in range(k):
    for i in range(n):
        l = max(0, i - a[i])
        r = min(n - 1, i + a[i])
        dp[i] = (l, r)
    imos = [0] * n
    for i in range(n):
        l, r = dp[i]
        imos[l] += 1
        if r < n - 1:
            imos[r + 1] -= 1
    tmp = 0
    for i in range(n):
        tmp += imos[i]
        a[i] = tmp
print(*a)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

ans=np.array([0]*N)
def wa(A,ans,N):
    for n in range(N):
        haba=A[n]
        ue=n+haba
        sita=n-haba
        if sita<0:
            sita=0
        if ue>N-1:
            ue=N-1
        if haba==0:
            ans[n]+=1
        else:
            ans[sita:ue+1]+=1
    return ans
for n in range(K):
    ans=np.array([0]*N)
    A=wa(A,ans,N)
print(' '.join(map(str, A)))

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
List = list(map(int, input().split()))
strength = [1]*N
for k in range (K):
  for i in range(N):
    if List[i] == 0:
      pass
    else:
      for j in range(1,List[i]+1):
        if i-j<0 and (i+j > N or i + j == N):
          pass
        elif i-j<0 and i+j <N:
          strength[i+j] += 1
        elif i-j>=0 and (i+j > N or i + j == N):
          strength[i-j] += 1
        else:
          strength[i-j] += 1
          strength[i+j] += 1
      #print(List,strength)
  List = strength
  strength = [1]*N
print(*List)

Submission status: Time Limit Exceeded

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

def light_distance(x,power):
  return [x-power-0.5,x+power+0.5]

def light_power_position(power_range):
  start = power_range[0]
  end = power_range[1]
  return [1 if i>=start and end>=i else 0 for i in range(1,n+1)]

max_power = [n for i in range(n)]
for i in range(k):
  number_light = [0 for i in range(n)]
  for j in range(1,n+1):
    if light_power[j-1] == 0:
      number_light[j-1] += 1
    else:
      number_light = list(map(sum, zip(number_light, light_power_position(light_distance(j,light_power[j-1])))))
  light_power = number_light
  if light_power == max_power:
    print(i)
    break
print(' '.join(map(str, light_power)))

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
FA = list(map(int,input().split()))
A = [0]*N
ANS = [N]*N
for i in range(N):
    mi = max(0,i-FA[i])
    ma = min(N-1,i+FA[i])
    for i in range(mi,ma+1):
        A[i] +=1

for i in range(N):
    mi = i-A[i]-K+1
    ma = i+A[i]+K-1
    if mi>=0:
        for j in range(0,mi+1):
            ANS[j] -=1
    if ma<=N-1:
        for j in range(ma,N):
            ANS[j] -=1

if K == 1:
    print(*A)
else:
    print(*ANS)

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import math

def changeLamp(lampList):
    newLampList = [0] * len(lampList)
    for i in range(len(lampList)):
        curLampStr = lampList[i]
        rangeLeft = math.ceil(i - curLampStr - 0.5)
        rangeLeft = rangeLeft if rangeLeft>=0 else 0
        rangeRight = int(i + curLampStr + 0.5)
        rangeRight = rangeRight if rangeRight<=len(lampList)-1 else len(lampList)-1
        for j in range(rangeLeft, rangeRight+1):
            newLampList[j] += 1
    return newLampList

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

lampList = input().split()
for i in range(len(lampList)):
    lampList[i] = int(lampList[i])

for i in range(k):
    lampList = changeLamp(lampList)

for lamp in lampList:
    print(lamp, end=' ')

Submission status: Time Limit Exceeded

Solution code:

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


for _ in range(K):
  ans = [0 for _ in range(N)]
  for n in range(N):
    temp =  [0 for _ in range(N)]
    start = n-A[n]
    end = n+A[n]+1
    if start < 0:
      start = 0
    if end > N:
      end = N
    for x in range(start,end):
      ans[x]+=1

  A = ans
print(" ".join(map(str,list(map(int,A)))))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def count_num_light(a):
  ret = np.array([0 for _ in range(len(a))])
  for i in range(len(a)):
    start = max(0, i-a[i])
    ret[start:i+a[i]+1] += 1
  
  return ret
                  
n, k = map(int, input().split())
a = np.array(list(map(int, input().split())))

for i in range(k):
  num_light = count_num_light(a)
  a = num_light.copy()

print(*a)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int, input().split())
A_list = [0] + [int(e) for e in input().split()]

#そのままやると10**5 **2　でTLE
#自分の座標を通過するまでは、自分の明るさ＝照射範囲は変わらない

#is_lighted[i][j]…iの座標のランプがjを照らすなら1否なら0の行列
#これで照らされる個数をカウントしていけばOK

edge = [[0 for _ in range(N+2)]]
center = [[0] + [0 for _ in range(1,N+1)] + [0] for i in range(N)]
is_lighted = edge + center + edge

def calc_lighted_area():
    for i in range(1,N+1):
        d = A_list[i]
        
        #照射範囲を求める
        if i-d < 0:
            left_side = 0
        else:
            left_side = i-d

        if i+d > N:
            right_side = N+1
        else:
            if d != 0:
                right_side = i+d+1
            else:
                right_side = left_side + 1
        
        is_lighted[i][left_side:right_side] = [1 for i in range(right_side - left_side)]

#for i in range(1,N+1):
#    print(is_lighted[i][1:N+1])

calc_lighted_area()

for j in range(K):
    for i in range(1,N+1):
        Bi = sum([row[i] for row in is_lighted])        
        A_list[i] = Bi
    calc_lighted_area()

print(' '.join(map(str, A_list[1:N+1])))

Submission status: Time Limit Exceeded

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

for i in range(K):
    imos = [0] * (N + 1)
    for j in range(N):
        s = A[j]
        l, r = max(0, j - A[j]), min(j + A[j], N - 1)
        # print("l,r,s = {} {} {}".format(l, r, s))
        imos[l] += 1
        imos[r + 1] -= 1
    for k in range(N):
        imos[k + 1] = imos[k] + imos[k + 1]
    A = imos[:N]


print(*imos[:N])

Submission status: Time Limit Exceeded

Solution code:
import copy

NK = input().split()
A = input().split()
N = int(NK[0])
K = int(NK[1])
AA = [0] * N
for i in range(N):
    AA[i] = int(A[i])
BB = [0] * N
for i in range(K):
    for j in range(N):
        # print("before adding")
        # print(AA)
        for k in range(j - AA[j], j + AA[j]+1):
            # print(k)
            if k >= 0 and k < N:
                BB[k]+= 1
        # print(BB)
    AA=copy.copy(BB)
    if i < K-1:
        BB = [0] * N
print(*BB)

Submission status: Time Limit Exceeded

Solution code:
N, K = (int(s) for s in input().rstrip().split())
a = [int(s) for s in input().rstrip().split()]

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

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def next(A):
    t = len(A)
    L = np.zeros(t)
    for i in range(t):
        m = max(0,int(i-A[i]))
        M = min(t,int(i+A[i]+1))
        L[m:M] += np.ones(M-m)
    return L

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

for _ in range(K):
    A = next(A)
A = [str(int(i)) for i in A]
print(" ".join(A))

Submission status: Time Limit Exceeded

Solution code:
n ,k = map(int, input().split())
A = list(_ for _ in map(int, input().split()))
for _ in range(k):
    B = [0]*n
    for i in range(n):
        a = A[i]
        a_d = i - a
        if a_d <0: a_d = 0
        a_u = i + a
        if a_u > n - 1: a_u = n-1
        for s in range(a_d,a_u+1):
            B[s] += 1
    A = B

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

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
import math
if math.ceil(n/2)<k:
  print(*([n]*n))
  exit()
import numpy as np
import copy
for kk in range(k):
  r=[0]*n
  for ii in range(n):
    if a[ii]==0:
      r[ii]+=1
    else:
      for jj in np.arange(max(0,ii-a[ii]),min(n,ii+a[ii]+1)):
          r[jj]+=1
  if a==r:
    print(*a) # * to remove []
    exit()
  #print(kk,a) # test
  a=copy.copy(r)
print(*a) # * to remove []

Submission status: Time Limit Exceeded

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

for _ in range(k):
    B = [0] * n
    for i, a in enumerate(A):
        sta = math.ceil(i-a-0.5)
        end = math.floor(i+a+0.5)
        for j in range(max(0, sta), min(end+1, n)):
            B[j] += 1
    if A == B:
        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()))

cnt=0
for _ in range(K):
    if cnt==N:
        break
    num=[0]*N
    cnt=0
    for i in range(N):
        num[i]+=1
        if num[i]==N:
            cnt+=1
        if A[i]==0:
            continue
        for j in range(max(0,i-A[i]),min(N,i+A[i]+1)):
            if j==i:
                continue
            num[j]+=1
            if num[j]==N:
                cnt+=1
    A=num

print(*A)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

# Calculate intensity
N, K = [int(v) for v in input().split(" ")]
A_arr = np.array([int(v) for v in input().split(" ")])
step = np.arange(len(A_arr))
if K > N-1:
  print(" ".join([str(N)]*N))
  exit()

def Luminate(A_arr, i):
  isLuminated = np.abs(step - i) < A_arr
  return isLuminated

def get_Intensity(A_arr):
  return np.array([np.sum(Luminate(A_arr, i)) for i in range(len(A_arr))])
Intensity = A_arr
for i in range(K):
  Intensity = get_Intensity(Intensity+1)
  if np.sum(Intensity) == N**2:
    break
print(" ".join([str(v) for v in Intensity]))

Submission status: Time Limit Exceeded

Solution code:
#C
N,K = map(int, input().split())
lights = list(map(int, input().split()))
#print(lights)
bright = [0 for i in range(N)]
#print(bright)
for kaisuu in range(K):
    for i in range(N):
        #左の電球から順に、その電球が照らす範囲のbrightに+1
        count = lights[i]
        for j in range(i-count,i+count+1):
            if 0<=j<=N-1:
                bright[j]+=1
    lights = bright
    bright = [0 for z in range(N)]
    #print(kaisuu,lights)
    #print(kaisuu,bright)
#print(lights)
for ans in lights:
    print(ans, end=" ")

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
N, K = map(int, input().split())
# 文字列の入力
#s = input()
#開業されたN個要素を受け付ける
input_list = list(map(int, input().split()))

for i in range(K):
    tmp_list = []
    for j in range(N):
        tmp = 0
        for l in range(N):
            if abs(j-l) <= input_list[l]:
                tmp = tmp+1
        tmp_list.append(tmp)

    input_list = tmp_list

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