Submission #748093

#TimeUsernameProblemLanguageResultExecution timeMemory
748093Sam_a17Group Photo (JOI21_ho_t3)C++17
64 / 100
5069 ms392432 KiB
#define _CRT_SECURE_NO_WARNINGS #include <bits/stdc++.h> //#include "temp.cpp" #include <cstdio> using namespace std; #ifndef ONLINE_JUDGE #define dbg(x) cerr << #x <<" "; print(x); cerr << endl; #else #define dbg(x) #endif #define sz(x) (int((x).size())) #define len(x) (int)x.length() #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define clr(x) (x).clear() #define uniq(x) x.resize(unique(all(x)) - x.begin()); #define pb push_back #define popf pop_front #define popb pop_back void print(long long t) {cerr << t;} void print(int t) {cerr << t;} void print(string t) {cerr << t;} void print(char t) {cerr << t;} void print(double t) {cerr << t;} void print(long double t) {cerr << t;} void print(unsigned long long t) {cerr << t;} template <class T, class V> void print(pair <T, V> p); template <class T> void print(vector <T> v); template <class T> void print(set <T> v); template <class T, class V> void print(map <T, V> v); template <class T> void print(multiset <T> v); template <class T> void print(T v[],T n) {cerr << "["; for(int i = 0; i < n; i++) {cerr << v[i] << " ";} cerr << "]";} template <class T, class V> void print(pair <T, V> p) {cerr << "{"; print(p.first); cerr << ","; print(p.second); cerr << "}";} template <class T> void print(vector <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";} template <class T> void print(deque <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";} template <class T> void print(set <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";} template <class T> void print(multiset <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";} template <class T, class V> void print(map <T, V> v) {cerr << "[ "; for (auto i : v) {print(i); cerr << " ";} cerr << "]";} #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; #define nl '\n' // for random generations mt19937 myrand(chrono::steady_clock::now().time_since_epoch().count()); // mt19937 myrand(131); // for grid problems int dx[8] = {-1,0,1,0,1,-1,1,-1}; int dy[8] = {0,1,0,-1,1,1,-1,-1}; // lowest / (1 << 17) >= 1e5 / (1 << 18) >= 2e5 / (1 << 21) >= 1e6 void fastIO() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); } // file in/out void setIO(string str = "") { fastIO(); if (str != "") { freopen((str + ".in").c_str(), "r", stdin); freopen((str + ".out").c_str(), "w", stdout); } } // Indexed Set template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; const int N = 5005; // bit struct fenwick { int size; vector<long long> tree; void init(int size_) { tree.assign(size_ + 2, 0); size = size_; } void upd(int u, long long v) { while(u <= size) { tree[u] += v; u += u & (-u); } } long long qry(int u) { long long sum = 0; while(u > 0) { sum += tree[u]; u -= u & (-u); // lsb } return sum; } long long sum(int l, int r) { return qry(r) - qry(l - 1); } }; int n, pos[N]; int get(vector<int>& a, vector<int>& b) { fenwick ft; ft.init(n + 1); int ans = 0; for(int i = 0; i < n; i++) { int wh = pos[b[i]]; ans += wh - 1 - ft.qry(wh); ft.upd(wh, 1); } return ans; } int dp[N]; int rec(int to) { if(to == 0) { return 0; } if(dp[to] != -1) { return dp[to]; } int maxi = n - (n - to); fenwick ft; ft.init(n + 1); for(int i = maxi + 1; i <= n; i++) { ft.upd(pos[i], 1); } int put = n * n; for(int i = to; i >= 1; i--) { fenwick nft = ft; int nd = to - i; int cur = maxi - nd, sm = 0; for(int j = to; j >= i; j--, cur++) { int suf = n - pos[cur]; suf -= nft.sum(pos[cur], n); nft.upd(pos[cur], 1); sm += suf; } put = min(put, sm + rec(i - 1)); } dp[to] = put; return dp[to]; } void solve_() { cin >> n; vector<int> a(n); for(int i = 0; i < n; i++) { cin >> a[i]; pos[a[i]] = i + 1; } // int ans = n * n; // for(int i = 1; i < (1 << n); i++) { // if(!(i & 1)) continue; // vector<int> b(n); // int it = n, lst = n - 1; // for(int j = n - 1; j >= 0; j--) { // if(i & (1 << j)) { // b[j] = it; // it -= (lst - j + 1); // lst = j - 1; // } // } // for(int j = 0; j < n; j++) { // if(b[j]) continue; // b[j] = b[j - 1] - 1; // } // ans = min(ans, get(a, b)); // } for(int i = 0; i <= n; i++) { dp[i] = -1; } cout << rec(n) << '\n'; } int main() { setIO(); auto solve = [&](int test_case)-> void { while(test_case--) { solve_(); } }; int test_cases = 1; // cin >> test_cases; solve(test_cases); return 0; }

Compilation message (stderr)

Main.cpp: In function 'void setIO(std::string)':
Main.cpp:67:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |     freopen((str + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:68:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |     freopen((str + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...