Submission #1208228

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208228		ofoz	Rabbit Carrot (LMIO19_triusis)	Pypy 3	100 / 100	241 ms	60836 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
        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






solve()

Compilation message (stdout)

Compiling 'triusis.py'...

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

=======

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