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>
int main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
int n;
std::cin >> n;
std::vector<int> h(n);
for (auto& i : h) std::cin >> i;
std::vector<int> pos(n);
for (int i = 0; i < n; ++i) pos[h[i] - 1] = i;
std::vector<std::vector<int>> pref(n + 1, std::vector<int>(n + 1));
for (int i = 0; i < n; ++i) {
pref[i + 1] = pref[i];
for (int j = 0; j <= n; ++j) {
if (h[i] <= j) pref[i + 1][j]++;
}
}
std::vector<int> dp(n + 1, 1e9);
dp[0] = 0;
for (int i = 0; i < n; ++i) {
int cur = dp[i];
for (int j = i; j < n; ++j) {
int k = pos[j];
int add = k - i;
add += pref[n][j] - pref[k][j];
add -= 2 * ((pref[n][j] - pref[n][i]) - (pref[k][j] - pref[k][i]));
cur += add;
dp[j + 1] = std::min(dp[j + 1], cur);
}
}
std::cout << dp[n];
}
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |