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 i64 = long long;
constexpr int inf = 1E9;
template <typename T>
struct Fenwick {
int n;
std::vector<T> a;
Fenwick(int n_ = 0) {
init(n_);
}
void init(int n_) {
n = n_;
a.assign(n, T{});
}
void add(int x, const T &v) {
for (int i = x + 1; i <= n; i += i & -i) {
a[i - 1] = a[i - 1] + v;
}
}
T sum(int x) {
T ans{};
for (int i = x; i > 0; i -= i & -i) {
ans = ans + a[i - 1];
}
return ans;
}
T rangeSum(int l, int r) {
return sum(r) - sum(l);
}
int select(const T &k) {
int x = 0;
T cur{};
for (int i = 1 << std::__lg(n); i; i /= 2) {
if (x + i <= n && cur + a[x + i - 1] <= k) {
x += i;
cur = cur + a[x - 1];
}
}
return x;
}
};
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin >> n;
std::vector<int> a(n + 1), pos(n + 1);
for (int i = 1; i <= n; i++) {
std::cin >> a[i];
pos[a[i] - 1] = i - 1;
}
std::vector<int> dp(n + 1);
dp[0] = 0;
for (int i = 1; i <= n; i++) {
dp[i] = inf;
Fenwick<int> fen(n);
int cur = 0;
for (int j = i - 1; j >= 0; j--) {
cur += fen.rangeSum(pos[j], n) - fen.sum(pos[j]);
fen.add(pos[j], 1);
dp[i] = std::min(dp[i], dp[j] + cur);
}
}
int answer = dp[n];
Fenwick<int> fen(n);
for (int i = 0; i < n; i++) {
answer += fen.rangeSum(pos[i], n);
fen.add(pos[i], 1);
}
std::cout << answer << "\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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |