Submission #874974

#TimeUsernameProblemLanguageResultExecution timeMemory
874974makravGroup Photo (JOI21_ho_t3)C++14
100 / 100
441 ms337564 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef vector<int> vei; typedef vector<vei> vevei; #define coa \ for (auto i : a) { \ cout << i << ' '; \ } \ cout << '\n'; #define cia \ for (auto& i : a) { \ cin >> a; \ } #define cna \ int n; \ cin >> n; \ vector<int> a(n); \ for (int i = 0; i < n; i++) { \ cin >> a[i]; \ } #define cnka \ int n, k; \ cin >> n >> k; \ vector<int> a(n); \ for (int i = 0; i < n; i++) { \ cin >> a[i]; \ } #define cnab \ int n; \ cin >> n; \ vector<int> a(n); \ for (int i = 0; i < n; i++) { \ cin >> a[i]; \ } \ vector<int> b(n); \ for (int i = 0; i < n; i++) { \ cin >> b[i]; \ } #define all(a) (a).begin(), (a).end() #define sz(a) (int) a.size() #define con cout << "No\n" #define coe cout << "Yes\n"; #define str string #define pb push_back #define ff first #define sc second #define pii pair<ll, ll> #define mxe max_element #define mne min_element #define stf shrink_to_fit #define f(i, l, r) for (int i = (l); i < (r); i++) #define double ld #define int ll int pereh[5001][5001], dp[5001][5001]; struct fenwick { int n; vector<int> t; fenwick() = default; fenwick(int n_) { n = n_; t.assign(n + 1, 0); } void clear() { t.assign(n + 1, 0); } int sum(int x) { int ans = 0; for (int i = x; i >= 0; i = (i & (i + 1)) - 1) { ans += t[i]; } return ans; } void upd(int pos, int delta) { for (int i = pos; i < n; i = i | (i + 1)) { t[i] += delta; } } }; signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n; cin >> n; vector<int> a(n); for (auto& u : a) cin >> u; vector<int> pos(n + 1); f(i, 0, n)pos[a[i]] = i; fenwick fw(n), fw2(n); f(i, 1, n + 1)fw.upd(i, 1); f(i, 1, n + 1) { fw2.clear(); for (int j = i; j <= n; j++) { pereh[i][j] = pereh[i][j - 1] + fw.sum(pos[j]) + fw2.sum(pos[j]) - (j - i); //cout << i << ' ' << j << ' ' << pereh[i][j] << '\n'; fw2.upd(pos[j] + 1, 1); } fw.upd(pos[i] + 1, -1); } vector<int> best_dp(n + 1, 1e18); best_dp[0] = 0; f(i, 1, n + 1) { for (int j = 1; j <= i; j++) { dp[i][j] = pereh[j][i] + best_dp[j - 1]; //cout << i << ' ' << j << ' ' << dp[i][j] << '\n'; best_dp[i] = min(best_dp[i], dp[i][j]); } } cout << best_dp[n] << '\n'; return 0; }
#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...