#include <bits/stdc++.h>
using namespace std;
#define FOR(i, l, r) for (int i=l; i<=r; i++)
void solve() {
int n, m; cin >> n >> m;
vector<int> dp(n+1, 1e9);
dp[0] = 0;
// aj <= ai + M*(j-i)
// M*j - aj >= M*i - ai
// bj >= bi
int res = 0;
FOR(i, 1, n) {
int a; cin >> a;
int b = m*i-a;
if (b < 0) continue;
auto it = lower_bound(dp.begin(), dp.end(), b);
int idx = it - dp.begin() + 1;
dp[idx] = min(dp[idx], b);
res = max(res, idx);
}
cout << n-res;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |