Submission #655663

#	Time	Username	Problem	Language	Result	Execution time	Memory
655663		erray	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	84 ms	6680 KiB

triusis

#include <bits/stdc++.h>

using namespace std;

int main() {
  int N, K;
  cin >> N >> K;
  vector<int> A(N + 1);
  for (int i = 0; i < N; ++i) {
    cin >> A[i + 1];
  }
  N += 1;
  vector<long long> fx(N);
  for (int i = 0; i < N; ++i) {
    fx[i] = A[i] - 1LL * i * K;
  }
  vector<long long> lis;
  for (int i = N - 1; i > 0; --i) {
    int next = lower_bound(lis.begin(), lis.end(), fx[i] + 1) - lis.begin();
    if (next == int(lis.size())) {
      lis.push_back(fx[i]);
    } else {
      lis[next] = fx[i];
    }
  }
  while (!lis.empty() && lis.back() > fx[0]) {
    lis.pop_back();
  }
  cout << N - 1 - int(lis.size()) << '\n';
}

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