Submission #1208221

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208221		ofoz	Rabbit Carrot (LMIO19_triusis)	Pypy 3	63 / 100	1097 ms	59420 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):

        # print(dp)
        for l in range(n, 0, -1):
            if a[i] <= dp[l-1]: dp[l] = max(dp[l], a[i])
    
    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: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 28 / 28
• Subtask 4: 0 / 37