Submission #1205413

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205413		ofoz	Rabbit Carrot (LMIO19_triusis)	Pypy 3	63 / 100	1098 ms	62460 KiB

triusis

from collections import deque
from sys import setrecursionlimit

def solve():
    n, m = map(int, input().split(" "))
    a = []
    for _ in range(n): a.append(int(input()))
    a.insert(0, 0)
    a.append(-float('inf'))
    n += 2
    dp = [float('inf')] * n
    dp[0] = 0

    for i in range(1, n):
        if a[i] - a[i-1] <= m: dp[i] = dp[i-1]
        for j in range(i):
            diff = i - j - 1
            if a[i] - a[j] > (diff+1) * m: continue
            dp[i] = min(dp[i], dp[j] + diff)
    print(dp[n-1])

    



"""

""" 




solve()

Compilation message (stdout)

Compiling 'triusis.py'...

=======
  adding: __main__.pyc (deflated 32%)

=======

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 28 / 28
• Subtask 4: 0 / 37