Submission #1230657

#TimeUsernameProblemLanguageResultExecution timeMemory
1230657biankGroup Photo (JOI21_ho_t3)C++20
12 / 100
1369 ms410848 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; vector<vll> cost(1 << n, vll(n, 0LL)); forn(mask, 1 << n) forn(i, n) { forn(j, n) { if (mask >> j & 1) continue; cost[mask][i] += pos[j] < pos[i]; } } vector<vll> dp(1 << n, vll(n, INF)); forn(i, n) { dp[1 << i][i] = cost[0][i]; } forn(mask, 1 << n) forn(i, n) { forn(j, n) if (i < j + 2) { dp[mask ^ (1 << j)][j] = min(dp[mask ^ (1 << j)][j], dp[mask][i] + cost[mask][j]); } } ll ret = INF; forn(i, n) ret = min(ret, dp[(1 << n) - 1][i]); cout << ret << '\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...