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;
#define ll long long
#define dbg(...) cerr<<#__VA_ARGS__<<" = ";_do(__VA_ARGS__);
template<typename T> void _do(T x){cerr<<x<<"\n";}
template<typename T,typename ...U> void _do(T x,U ...y){cerr<<x<<", ";_do(y...);}
signed main(){
ios::sync_with_stdio(0), cin.tie(0);
int N;
cin >> N;
vector<int> arr(N + 1), pos(N + 1);
for (int i = 1; i <= N; i++) cin >> arr[i], pos[arr[i]] = i;
vector<vector<int>> dp(N + 1, vector<int>(N + 1, 0));
vector<vector<int>> psum(N + 1, vector<int>(N + 1, 0));
dp[1][1] = 0;
psum[1][pos[1]] = 1;
for (int i = 1; i <= N; i++) psum[1][i] += psum[1][i - 1];
auto inv = [&](int up, int val, int p) -> int {
// how much >= val and position < p
int cnt = 0, cnt2 = 0;
cnt += psum[up][p] - psum[val - 1][p];
// for (int i = val; i <= up; i++) {
// if (pos[i] < p) cnt2++;
// }
// dbg(up, val, cnt, cnt2);
cnt += psum[val - 1][N] - psum[val - 1][p];
// for (int i = 0; i < val; i++) {
// if (pos[i] > p) cnt2++;
// }
return cnt;
};
for (int i = 2; i <= N; i++) {
dp[i][i] = 1e9;
for (int j = 1; j < i; j++) {
dp[i][j] = dp[i - 1][j] + inv(i - 1, j, pos[i]);
dp[i][i] = min(dp[i][i], dp[i - 1][j] + inv(i - 1, i, pos[i]));
}
for (int j = 1; j <= i; j++) {
psum[i][pos[j]]++;
}
for (int j = 1; j <= N; j++) {
psum[i][j] += psum[i][j - 1];
// dbg(i, j, psum[i][j]);
}
}
int ans = 1e9;
for (int i = 1; i <= N; i++) ans = min(ans, dp[N][i]);
cout << ans << '\n';
}
Compilation message (stderr)
Main.cpp: In lambda function:
Main.cpp:27:22: warning: unused variable 'cnt2' [-Wunused-variable]
27 | int cnt = 0, cnt2 = 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... |