Submission #1205285

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205285		ofoz	Rabbit Carrot (LMIO19_triusis)	Pypy 3	0 / 100	229 ms	51388 KiB

triusis

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()))
    a.append(-float('inf'))
    dp = [float('inf')] * (n+2)
    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+2):
        dp[i] = dp[i-1]
        if a[i] - a[i-1] > m: dp[i] += 1
        for j in range(1, i):
            diff = i - j - 1
            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 44%)

=======

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