제출 #1121546

#제출 시각아이디문제언어결과실행 시간메모리
1121546vjudge1Boarding Passes (BOI22_passes)C++17
0 / 100
1 ms336 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]; long double calc(int x) { 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 { 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 { A++; } } long double ans = 1e18; for(int i = 0; i < n; i++) { ans = min(ans, pref[i] + suf[i]); } 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 = 0; do{ for(int i = 0; i <= g; i++) { used[i] = 0; } long double cur = 0; for(int x: p) { cur += calc(x); used[x] = 1; } ans = min(ans, cur); }while(next_permutation(p.begin(), p.end())); cout << 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...