제출 #944952

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
944952		imann	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	69 ms	5716 KiB

triusis

#include <iostream>
#include <array>
#include <algorithm>
#include <limits>

using ll = long long;

const int MAX_N = 2*1000*100 + 3;

std::array<ll, MAX_N> As, dp;

int solve(int n) {
  std::reverse(As.begin(), As.begin() + n);

  dp.fill(std::numeric_limits<ll>::max());
  for (int i = 0; i < n; ++i) {
    if (As[i] <= 0) {
      int j = std::upper_bound(dp.begin(), dp.begin() + n, As[i]) - dp.begin();
      dp[j] = As[i];
    }
  }

  int ans = 0;
  for (int i = 0; i < n; ++i) {
    if (dp[i] != std::numeric_limits<ll>::max())
      ans = i + 1;
  }
  return ans;
}

int main() {
  int n, m; std::cin >> n >> m;
  for (int i = 0; i < n; ++i) {
    std::cin >> As[i];
    As[i] -= (i + 1) * m;
  }
  std::cout << n - solve(n) << std::endl;
}

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