Submission #385225

#	Time	Username	Problem	Language	Result	Execution time	Memory
385225		SansPapyrus683	Rabbit Carrot (LMIO19_triusis)	Cpython 3	100 / 100	558 ms	21560 KiB

triusis

from typing import List
from bisect import bisect_right


def longest_nondec_subseq(arr: List[int]) -> int:
    min_endings = []
    for i in arr:
        # bisect_right not left because it just has to be nondecreasing
        pos = bisect_right(min_endings, i)
        # standard LIS protocol
        if pos == len(min_endings):
            min_endings.append(i)
        else:
            min_endings[pos] = i
    return len(min_endings)


pole_num, jump_height = [int(i) for i in input().split()]
poles = [int(input()) for _ in range(pole_num)]

poss_unchanged = []
for i, p in enumerate(poles):
    if (i + 1) * jump_height >= p:
        poss_unchanged.append((i + 1) * jump_height - p)

print(pole_num - longest_nondec_subseq(poss_unchanged))

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