제출 #1121627

#제출 시각아이디문제언어결과실행 시간메모리
1121627vjudge1Boarding Passes (BOI22_passes)C++17
100 / 100
1075 ms411988 KiB
#include <bits/stdc++.h> using namespace std; int n, g; string s; long double get(long double x) { return x * (x-1)/4; } long double pref[100100]; long double suf[100100]; long double dp[1<<16]; vector<int> pos[1111]; long double C[100100][16][16]; int cnt[100100][16]; long double get(int mask, int d, int x) { long double ans = 0; for(int i = 0; i < g; i++) { if(mask & (1<<i)) { ans += C[d][x][i]; } } long double cc = cnt[d][x]; long double ALL = cnt[n][x]; return ans + get(cc) + get(ALL-cc); } long double calc(int mask, int x) { if(pos[x].size() == 1) return 0; int l = 0, r = pos[x].size() - 1; while(l + 3 < r) { int mid = (l + r)/2; if(get(mask, pos[x][mid], x) < get(mask, pos[x][mid+1], x)) { r = mid; } else { l = mid; } } long double ans = 1e18; for(int i = l; i <= r; i++) { ans = min(ans, get(mask, pos[x][i], x)); } return ans; } void precalc(int x, int y) { 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++; } else if(s[i] == 'A'+y) { 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++; } else if(s[i] == 'A' + y){ A++; } } for(int i = 0; i <= n; i++) { C[i][x][y] = pref[i] + suf[i]; } } int main() { cin >> s; n = s.size(); for(int i = 0; i < 16; i++) { pos[i].push_back(0); } for(int i = 0; i < n; i++) { g = max(s[i] - 'A' + 1, g); pos[s[i] - 'A'].push_back(i + 1); } for(int c = 0; c < g; c++) { for(int i = 1; i <= n; i++) { cnt[i][c] = cnt[i-1][c] + (s[i-1] - 'A' == c); } } for(int i = 0; i < g; i++) { for(int j = 0; j < g; j++) { if(i == j) continue; precalc(i, j); } } for(int i = 0; i < (1<<g); i++) { dp[i] = 1e18; } dp[0] = 0; for(int mask = 0; mask < (1<<g); mask++) { for(int i = 0; i < g; i++) { int nmask = mask | (1<<i); if(nmask != mask) { dp[nmask] = min(dp[mask] + calc(mask, i), dp[nmask]); } } } cout << fixed << setprecision(12) << dp[(1<<g)-1] << "\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...