from collections import deque
from sys import setrecursionlimit
def isLower(c1: list[int], c2: list[int]):
if any([x < 0 for x in c1]): return False
if any([x < 0 for x in c2]): return True
return c1[0] < c2[0]
def solve():
n, m = map(int, input().split(" "))
a = [0]
for _ in range(n): a.append(int(input()))
dp = [float('inf')] * (n+1)
extra = 0
for i in range(1, n+1):
if a[i] - a[i-1] <= m: break
a[i] = a[i-1] + m
extra += 1
dp[0] = 0
dp[1] = 0
# print(a)
for i in range(1, n+1):
for j in range(1, i):
diff = i - j
if a[i] - a[j] > m * diff: continue
dp[i] = min(dp[i], dp[j] + (i - j - 1))
# print(a)
print(dp[-1] + extra)
"""
A_i <= A_i+1
"""
solve()
Compilation message (stdout)
Compiling 'triusis.py'...
=======
adding: __main__.pyc (deflated 42%)
=======
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |