Submission #599608

#TimeUsernameProblemLanguageResultExecution timeMemory
599608fvogel499Boarding Passes (BOI22_passes)C++17
60 / 100
2058 ms10032 KiB
/* * File created on 07/19/2022 at 18:21:46. * Link to problem: * Description: * Time complexity: O() * Space complexity: O() * Status: --- * Copyright: Ⓒ 2022 Francois Vogel */ #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define pii pair<int, int> #define f first #define s second #define vi vector<int> #define all(x) x.begin(), x.end() #define size(x) (int)((x).size()) #define pb push_back #define ins insert #define cls clear #define int ll #define ll long long #define ld long double typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; const int inf = 1e18; signed main() { cin.tie(0); ios_base::sync_with_stdio(0); cout.precision(20); string b; cin >> b; const int n = size(b); int gK = 0; for (char i : b) if (i-'A'+1 > gK) gK = i-'A'+1; vi per [gK]; for (int i = 0; i < n; i++) { per[b[i]-'A'].pb(i); } ld cost [gK][1<<gK]; for (int i = 0; i < gK; i++) for (int j = 0; j < (1<<gK); j++) if (!((j>>i)&1)) { int pref [n]; for (int k = 0; k < n; k++) pref[k] = (j>>(b[k]-'A'))&1; for (int k = 1; k < n; k++) pref[k] += pref[k-1]; cost[i][j] = 0; for (int k = 0; k < size(per[i]); k++) { ld dl = k; ld dr = size(per[i])-k-1; ld cl = 0; if (per[i][k]) cl = pref[per[i][k]-1]; ld cr = pref[n-1]-pref[per[i][k]]; cost[i][j] += min(cl+dl/(ld)(2), cr+dr/(ld)(2)); } } ld dp [1<<gK]; dp[(1<<gK)-1] = 0; for (int i = (1<<gK)-2; i >= 0; i--) { dp[i] = inf; for (int j = 0; j < gK; j++) if (!((i>>j)&1)) { dp[i] = min(dp[i], dp[i|(1<<j)]+cost[j][i]); } } cout << dp[0]; cout.flush(); int d = 0; d++; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...