Submission #503511

#TimeUsernameProblemLanguageResultExecution timeMemory
503511InternetPerson10Group Photo (JOI21_ho_t3)C++17
100 / 100
768 ms313296 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...