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;
typedef long long ll;
const ll BIG = 1234567891234567890;
ll ans[5001];
ll dp[5001][5001];
ll permute_people[5001][5001]; // Permute people [i, j] once they are already on the left
ll push_people[5001][5001]; // Push people [i, j] to the left
struct FTree {
vector<int> nums;
int size = 1;
void init(int n) {
vector<int>().swap(nums);
size = 1;
while(size <= n) size *= 2;
nums.resize(size+1);
}
void add(int n, int k) {
while(n <= size) {
nums[n] += k;
n += (n & (-n));
}
}
int sum(int n) {
int ans = 0;
while(n) {
ans += nums[n];
n -= (n & (-n));
}
return ans;
}
};
ll swap_photo(vector<int> nums) {
int n = nums.size();
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
dp[i][j] = 0;
}
}
vector<int> ind(n);
for(int i = 0; i < n; i++) ind[nums[i]] = i;
FTree ft, ft2;
for(int i = 0; i < n; i++) {
ft.init(n+1);
ft2.init(n+1);
for(int j = i; j < n; j++) ft2.add(ind[j]+1, 1);
for(int j = i; j < n; j++) {
if(i == j) push_people[i][j] = ft2.sum(ind[j]+1) - 1;
else push_people[i][j] = push_people[i][j-1] + ft2.sum(ind[j]+1) - 1 - (j - i) + ft.sum(ind[j]+1);
ft.add(ind[j]+1, 1);
}
}
for(int i = n-1; i >= 0; i--) {
ans[i] = BIG;
for(int j = i; j < n; j++) {
dp[i][j] = push_people[i][j] + ans[j+1];
ans[i] = min(ans[i], dp[i][j]);
}
}
return ans[0];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<int> nums(n);
for(int i = 0; i < n; i++) cin >> nums[i];
for(int i = 0; i < n; i++) nums[i]--;
cout << swap_photo(nums);
}
# | 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... |