Submission #751649

#TimeUsernameProblemLanguageResultExecution timeMemory
751649KihihihiGroup Photo (JOI21_ho_t3)C++17
100 / 100
445 ms196572 KiB
#include <iostream> #include <iomanip> #include <algorithm> #include <numeric> #include <cmath> #include <cassert> #include <ctime> #include <chrono> #include <cstdio> #include <random> #include <vector> #include <string> #include <map> #include <unordered_map> #include <set> #include <unordered_set> #include <deque> #include <queue> #include <bitset> #include <list> #include <fstream> #include <functional> #include <complex> using namespace std; mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count()); short skip_cin = 0; const long long INF = 1e18, MOD = 1e9 + 7, MOD2 = 998244353, LOG = 18; const long double EPS = 1e-9, PI = acos(-1); struct fenwick { long long n; vector<long long> t; fenwick(long long in) { n = in; t.resize(n + 1); } void upd(long long k, long long x) { k++; for (; k <= n; k += k & -k) { t[k] += x; } } long long get(long long k) { k++; long long sum = 0; for (; k > 0; k -= k & -k) { sum += t[k]; } return sum; } void reset() { t.assign(n + 1, 0); } }; void solve() { long long n; vector<long long> v, pos; cin >> n; v.resize(n); pos.resize(n); for (long long i = 0; i < n; i++) { cin >> v[i]; v[i]--; pos[v[i]] = i; } vector<vector<long long>> inv(n, vector<long long>(n, -1)); fenwick ft(n); for (long long l = 0; l < n; l++) { inv[l][l] = 0; ft.upd(pos[l], 1); for (long long r = l + 1; r < n; r++) { inv[l][r] = inv[l][r - 1] + ft.get(pos[r]); ft.upd(pos[r], 1); } ft.reset(); } vector<long long> dp(n + 1, INF), suminv(n + 1), inside(n + 1); dp[n] = 0; suminv[n] = 0; inside[n] = 0; for (long long i = n - 1; i > -1; i--) { for (long long j = i; j <= n - 1; j++) { long long raw = inv[i][j] + suminv[j + 1]; long long bl = inv[i][n - 1] - raw; long long onlyin = (j - i + 1) * (j - i) / 2 + inside[j + 1]; long long allbl = (n - i) * (n - i - 1) / 2 - onlyin; long long cur = raw + allbl - bl; if (cur < dp[i]) { dp[i] = cur; suminv[i] = raw; inside[i] = onlyin; } } } cout << dp[0] << "\n"; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); srand(time(NULL)); int tst = 1; //cin >> tst; while (tst--) { solve(); } return 0; } /* <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 ⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⠤⠖⠚⢉⣩⣭⡭⠛⠓⠲⠦⣄⡀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⢀⡴⠋⠁⠀⠀⠊⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠳⢦⡀⠀⠀⠀⠀ ⠀⠀⠀⠀⢀⡴⠃⢀⡴⢳⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⣆⠀⠀⠀ ⠀⠀⠀⠀⡾⠁⣠⠋⠀⠈⢧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢧⠀⠀ ⠀⠀⠀⣸⠁⢰⠃⠀⠀⠀⠈⢣⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣇⠀ ⠀⠀⠀⡇⠀⡾⡀⠀⠀⠀⠀⣀⣹⣆⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⠀ ⠀⠀⢸⠃⢀⣇⡈⠀⠀⠀⠀⠀⠀⢀⡑⢄⡀⢀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⡇ ⠀⠀⢸⠀⢻⡟⡻⢶⡆⠀⠀⠀⠀⡼⠟⡳⢿⣦⡑⢄⠀⠀⠀⠀⠀⠀⠀⠀⢸⡇ ⠀⠀⣸⠀⢸⠃⡇⢀⠇⠀⠀⠀⠀⠀⡼⠀⠀⠈⣿⡗⠂⠀⠀⠀⠀⠀⠀⠀⢸⠁ ⠀⠀⡏⠀⣼⠀⢳⠊⠀⠀⠀⠀⠀⠀⠱⣀⣀⠔⣸⠁⠀⠀⠀⠀⠀⠀⠀⢠⡟⠀ ⠀⠀⡇⢀⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠠⠀⡇⠀⠀⠀⠀⠀⠀⠀⠀⢸⠃⠀ ⠀⢸⠃⠘⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⠁⠀⠀⢀⠀⠀⠀⠀⠀⣾⠀⠀ ⠀⣸⠀⠀⠹⡄⠀⠀⠈⠁⠀⠀⠀⠀⠀⠀⠀⡞⠀⠀⠀⠸⠀⠀⠀⠀⠀⡇⠀⠀ ⠀⡏⠀⠀⠀⠙⣆⠀⠀⠀⠀⠀⠀⠀⢀⣠⢶⡇⠀⠀⢰⡀⠀⠀⠀⠀⠀⡇⠀⠀ ⢰⠇⡄⠀⠀⠀⡿⢣⣀⣀⣀⡤⠴⡞⠉⠀⢸⠀⠀⠀⣿⡇⠀⠀⠀⠀⠀⣧⠀⠀ ⣸⠀⡇⠀⠀⠀⠀⠀⠀⠉⠀⠀⠀⢹⠀⠀⢸⠀⠀⢀⣿⠇⠀⠀⠀⠁⠀⢸⠀⠀ ⣿⠀⡇⠀⠀⠀⠀⠀⢀⡤⠤⠶⠶⠾⠤⠄⢸⠀⡀⠸⣿⣀⠀⠀⠀⠀⠀⠈⣇⠀ ⡇⠀⡇⠀⠀⡀⠀⡴⠋⠀⠀⠀⠀⠀⠀⠀⠸⡌⣵⡀⢳⡇⠀⠀⠀⠀⠀⠀⢹⡀ ⡇⠀⠇⠀⠀⡇⡸⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠮⢧⣀⣻⢂⠀⠀⠀⠀⠀⠀⢧ ⣇⠀⢠⠀⠀⢳⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⡎⣆⠀⠀⠀⠀⠀⠘ ⢻⠀⠈⠰⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠰⠘⢮⣧⡀⠀⠀⠀⠀ ⠸⡆⠀⠀⠇⣾⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⠆⠀⠀⠀⠀⠀⠀⠀⠙⠳⣄⡀⢢⡀ <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 */
#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...