Submission #1196647

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196647		julia_08	Rabbit Carrot (LMIO19_triusis)	C++20	100 / 100	19 ms	1864 KiB

triusis

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5 + 10;

int a[MAXN], dp[MAXN];

int main(){
  cin.tie(0)->sync_with_stdio(0);

  int n, m; cin >> n >> m;

  for(int i=1; i<=n; i++){
    cin >> a[i];
    a[i] = i * m - a[i];
  }

  for(int i=1; i<=n; i++) dp[i] = 2e9;

  for(int i=1; i<=n; i++){

    if(a[i] < 0) continue;

    int l = upper_bound(dp + 1, dp + n + 1, a[i]) - dp;
    dp[l] = a[i];

  }

  int l = 0;

  for(int i=1; i<=n; i++) if(dp[i] != 2e9) l = i;

  cout << n - l << "\n";

  return 0;
}

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