Submission #747749

#	Time	Username	Problem	Language	Result	Execution time	Memory
747749		nguyennehehe	Rabbit Carrot (LMIO19_triusis)	C++14	100 / 100	29 ms	7620 KiB

triusis

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

using ll = long long;
using ld = long double;
using vi = vector<int>;
using pii = pair<int, int>;

#define sz(a) (int)(a).size()
#define all(a) (a).begin(), (a).end()
#define pb push_back

const int N = 2e5 + 5;

int n, a[N], m;
vector<ll> b;

int solve() {
  vector<ll> dp;

  for (ll x: b) {
    auto it = upper_bound(all(dp), x);
    if (it == dp.end()) dp.pb(x);
    else {
      int pos = it - dp.begin();
      dp[pos] = x;
    }
  }
  return sz(dp);
}

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

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

  for (int i = 1; i <= n; ++i) {
    if (a[i] <= 1LL * i * m) b.pb(1LL * i * m - a[i]);
  }

  cout << n - solve();
}

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