Submission #653211

#TimeUsernameProblemLanguageResultExecution timeMemory
653211StickfishGroup Photo (JOI21_ho_t3)C++17
100 / 100
855 ms460 KiB
#include <iostream> #include <vector> #include <algorithm> using namespace std; struct bitr { void resize(int n) { t.resize(n); sz = n; } void add(int i, int x) { while (i < sz) { t[i] += x; i |= i + 1; } } int get(int i) { int ans = 0; while (i > -1) { ans += t[i]; i &= i + 1; --i; } return ans; } int operator()(int l, int r) { return get(r - 1) - get(l - 1); } private: int sz; vector<int> t; }; const int MAXN = 5001; int a[MAXN]; int ra[MAXN]; int dp_[MAXN]; int* dp = dp_ + 1; signed main() { int n; cin >> n; for (int i = 0; i < n; ++i) cin >> a[i]; for (int i = 0; i < n; ++i) ra[--a[i]] = i; for (int i = 0; i < n; ++i) dp[i] = MAXN * MAXN; for (int i = -1; i < n; ++i) { bitr used; bitr nonused; used.resize(n); nonused.resize(n); for (int j = i + 1; j < n; ++j) { nonused.add(ra[j], 1); } int add = 0; for (int j = i + 1; j < n; ++j) { nonused.add(ra[j], -1); add += nonused.get(ra[j] - 1); add -= used(ra[j], n); add += used.get(ra[j]); used.add(ra[j], 1); dp[j] = min(dp[j], dp[i] + add); } } cout << dp[n - 1] << '\n'; }
#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...