Submission #1208226

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208226		ofoz	Rabbit Carrot (LMIO19_triusis)	Pypy 3	0 / 100	160 ms	51404 KiB

triusis

from collections import deque
from sys import setrecursionlimit
from math import ceil, floor, sqrt
from itertools import permutations

def solve():
    n, m = map(int, input().split(" "))
    a = []
    for i in range(n): a.append(int(input()) - m * (i+1))

    dp = [-float('inf')] * (n+1)
    dp[0] = 0
    for i in range(n):

        l, r = 0, n-1
        while r-l>1:
            mid = (l+r)//2
            if a[i] <= dp[mid]: l = mid
            else: r = mid

        if a[i] <= dp[l]: dp[r] = max(a[i], dp[r])

    
    for i in range(n, -1, -1):
        if dp[i] > -float('inf'):
            print(n - i)
            return





"""
a[i] <= a[i+1] + m
a[i] - mi >= a[i+1] - (m+1)i
"""

solve()

Compilation message (stdout)

Compiling 'triusis.py'...

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

=======

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