Submission #1230663

#TimeUsernameProblemLanguageResultExecution timeMemory
1230663biankGroup Photo (JOI21_ho_t3)C++20
64 / 100
5097 ms98376 KiB
#include <bits/stdc++.h> using namespace std; #define forsn(i, s, n) for (int i = int(s); i < int(n); i++) #define forn(i, n) forsn(i, 0, n) #define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--) #define dforn(i, n) dforsn(i, 0, n) #define sz(x) int(x.size()) #define all(x) begin(x), end(x) using ll = long long; using ld = long double; using vi = vector<int>; using vb = vector<bool>; using vll = vector<ll>; using ii = pair<int, int>; using iii = tuple<int, int, int>; #define fst first #define snd second #define pb push_back #define eb emplace_back const ll INF = 1e18; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; vi h(n); forn(i, n) cin >> h[i], --h[i]; vi pos(n); forn(i, n) pos[h[i]] = i; vll dp(n + 1, INF); dp[0] = 0LL; vector<vi> pref(n, vi(n + 1)); forn(i, n) forn(j, n) { pref[i][j + 1] = pref[i][j] + (pos[j] < pos[i]); } forsn(i, 1, n + 1) { forn(j, i) { ll cost = 0LL; forsn(k, j, i) { cost += pref[k][n] - pref[k][j]; cost -= pref[k][i] - pref[k][k]; } dp[i] = min(dp[i], dp[j] + cost); } } cout << 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...