제출 #1121557

#제출 시각아이디문제언어결과실행 시간메모리
1121557vjudge1Boarding Passes (BOI22_passes)C++17
60 / 100
2071 ms10844 KiB
#include <bits/stdc++.h> using namespace std; int n, g; string s; long double get(long double x) { return x * (x-1)/4; } int used[1111]; long double pref[100100]; long double suf[100100]; int was[1<<16][16]; long double dp[1<<16][16]; long double calc(int mask, int x) { if(was[mask][x]) return dp[mask][x]; was[mask][x] = 1; int A = 0; int X = 0; for(int i = 0; i < n; i++) { pref[i+1] = pref[i]; if(s[i] == 'A' + x) { pref[i+1] += A + X*0.5; X++; } else if(used[s[i] - 'A']) { A++; } } X = 0; A = 0; for(int i = n-1; i >= 0; i--) { suf[i] = suf[i+1]; if(s[i] == 'A' + x) { suf[i] += A + X * 0.5; X++; } else if(used[s[i] - 'A']){ A++; } } long double ans = 1e18; for(int i = 0; i < n; i++) { ans = min(ans, pref[i] + suf[i]); } dp[mask][x] = ans; return ans; } int main() { cin >> s; n = s.size(); for(int i = 0; i < n; i++) { g = max(s[i] - 'A', g); } vector<int> p; for(int i = 0; i <= g; i++) { p.push_back(i); } //cout << g << "\n"; long double ans = 1e18; do{ for(int i = 0; i <= g; i++) { used[i] = 0; } long double cur = 0; int mask = 0; for(int x: p) { cur += calc(mask, x); mask |= (1<<x); used[x] = 1; } ans = min(ans, cur); }while(next_permutation(p.begin(), p.end())); cout << fixed << setprecision(12) << ans << "\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...