# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1205424 | ofoz | Rabbit Carrot (LMIO19_triusis) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi pair<int, int>
#define vi vector<int>
void solve() {
int n, m;
cin >> n >> m;
vector<int> a(n);
for (int &x : a) cin >> x;
a.insert(a.begin(), 0);
a.push_back(INT32_MIN);
n += 2;
vi dp(n, INT32_MAX);
dp[0] = 0;
for (int i = 1; i < n; i++) {
if (a[i] - a[i-1] <= m) dp[i] = dp[i-1];
for (int j = 0; j < i; j++) {
int diff = i - j - 1;
if ((a[i] - a[j]) > (diff + 1) * m) continue;
dp[i] = min(dp[i], dp[j] + diff);
}
}
cout << dp[n-1];
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
}