(UPD: 2024-12-04 14:48 UTC) Judge is not working due to Cloudflare incident. (URL) We can do nothing about it, sorry. After the incident is resolved, we will grade all submissions.

제출 #1122186

#제출 시각아이디문제언어결과실행 시간메모리
1122186vjudge1Group Photo (JOI21_ho_t3)C++17
100 / 100
353 ms196520 KiB
#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cmath> #include <vector> #include <set> #include <map> #include <unordered_set> #include <unordered_map> #include <queue> #include <ctime> #include <cassert> #include <complex> #include <string> #include <cstring> #include <chrono> #include <random> #include <bitset> #include <fstream> #include <array> #include <functional> #include <stack> #include <memory> #ifdef LOCAL #define _GLIBCXX_DEBUG #endif using namespace std; #define int long long #define app push_back #define all(x) x.begin(), x.end() #ifdef LOCAL #define debug(...) [](auto...a){ ((cout << a << ' '), ...) << endl; }(#__VA_ARGS__, ":", __VA_ARGS__) #define debugv(v) do { cout << #v << ": "; for (auto x : v) cout << x << ' '; cout << endl; } while(0) #else #define debug(...) #define debugv(v) #endif int32_t main() { cin.tie(0);ios_base::sync_with_stdio(0); int n; cin >> n; vector <int> h(n), q(n + 1); for (int i = 0; i < n; ++i) { cin >> h[i]; h[i]--; q[h[i]]=i; } vector <vector <int> > pre(n + 1, vector <int> (n + 1)); for (int x = 0; x < n; ++x) { for (int y = 0; y < x; ++y) { if (q[x] < q[y]) { pre[x + 1][y + 1]++; } } } for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { pre[i + 1][j + 1] += pre[i + 1][j] + pre[i][j + 1] - pre[i][j]; } } auto inv = [&] (int y1, int y2, int x1, int x2) { return pre[x2][y2] - pre[x1][y2] - pre[x2][y1] + pre[x1][y1]; }; auto c2 = [&] (int k) { return k * (k - 1) / 2; }; vector <int> dp(n + 1, n * n); dp.front() = 0; for (int l = 0; l < n; ++l) { for (int r = l + 1; r <= n; ++r) { dp[r] = min(dp[r], dp[l] + inv(0, l, l, r) + (c2(r - l) - inv(l, r, l, r))); } } cout << dp.back() << '\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...