제출 #666570

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
666570		I_love_Chou_Giang	Rabbit Carrot (LMIO19_triusis)	C++14	100 / 100	26 ms	5320 KiB

triusis

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

typedef long long ll;

#define vt vector
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()

#define R_EP(i, a, b, s) for (int i = (a); (s) > 0 ? i < (b) : i > (b); i += (s))
#define R_EP1(e) R_EP(i, 0, e, 1)
#define R_EP2(i, e) R_EP(i, 0, e, 1)
#define R_EP3(i, b, e) R_EP(i, b, e, 1)
#define R_EP4(i, b, e, s) R_EP(i, b, e, s)
#define GET5(a, b, c, d, e, ...) e
#define R_EPC(...) GET5(__VA_ARGS__, R_EP4, R_EP3, R_EP2, R_EP1)
#define rep(...) R_EPC(__VA_ARGS__)(__VA_ARGS__)
#define trav(x, a) for (auto x : a) 

template<typename T> inline bool umax(T&x, const T& y) { if (x >= y) return false; x = y; return true; }
template<typename T> inline bool umin(T&x, const T& y) { if (x <= y) return false; x = y; return true; }

const int MOD = int(1e9) + 7, naxm = 200000, INF = int(1e9);

int N, M, a[naxm + 5], dp[naxm + 5];
vt<int> f;

int main() {
  ios_base::sync_with_stdio(false), cin.tie(nullptr);

  cin >> N >> M;
  rep(i, 1, N + 1) cin >> a[i];

  // maximize number of a[i] do not change
  // a[i] <= M * i => M * i - a[i] >= 0
  // a[i] <= a[j] + M * (i - j) (j < i) <=> M * j - a[j] <= M * i - a[i]
  // so we define M * x - a[x] = f[x] => f[0] >= 0 && f[x] <= f[x + 1] => longest non-decreasing subsequence

  rep(i, 1, N + 1) {
    if (M * i - a[i] >= 0) f.pb(M * i - a[i]);
  }

  vt<int> dp;
  trav(v, f) {
    int l = lower_bound(all(dp), v + 1) - dp.begin();
    if (l < sz(dp)) dp[l] = v;
    else dp.pb(v);
  }

  cout << N - sz(dp) << "\n";

  return 0;
}

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