This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 1e9;
int main() {
int n, m;
cin >> n >> m;
n++;
vector<int> arr(n);
for (int i = 1; i < n; i++)
cin >> arr[i];
const int M = 5e3;
vector memo(n, vector(M+1, -1));
auto dp = [&](auto& dp, int i, int x)->int {
if (x < 0) return inf;
if (x > M) return inf;
if (i == 0) {
return x== arr[i] ? 0 : inf;
}
if (memo[i][x] != -1) return memo[i][x];
int res = inf;
for (int p = x-m; p <= x+m; p++) {
res = min(res, dp(dp, i-1, p) + (x != arr[i]));
}
return memo[i][x] = res;
};
int res = inf;
for (int i = 0; i <= M; i++)
res = min(res, dp(dp, n-1, i));
cout << res << '\n';
return 0;
}
# | 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... |