제출 #598529

#제출 시각아이디문제언어결과실행 시간메모리
598529SuffixAutomataBoarding Passes (BOI22_passes)C++17
0 / 100
1 ms340 KiB
#include <bits/stdc++.h> using namespace std; #define all(a) a.begin(), a.end() #define fi first #define se second #define pb push_back #define mp make_pair using ll = long long; using pii = pair<int, int>; //#define int ll const int MOD = 1000000007; ll wt[15][1 << 15]; ll dp[1 << 15]; int id[100005]; int con[100005][15]; signed main() { ios_base::sync_with_stdio(false); cin.tie(0); string s; cin >> s; int n = s.size(); int S = 0; for (int i = 0; i < n; i++) S = max(S, id[i] = s[i] - 'A'); S++; for (int i = 0; i < S; i++) { // todo: optimize this vector<int> pos; for (int j = 0; j < n; j++) if (id[j] == i) pos.push_back(j); ll cnt = pos.size(); for (int k = 0; k <= cnt; k++) for (int j = 0; j < S; j++) con[k][j] = 0; int x = 0; for (int j = 0; j < n; j++) { if (x != cnt && j == pos[x]) { x++; continue; } con[x][id[j]]++; } for (int j = 0; j < S; j++) { int ds = 0, L = 0, R = 0; for (int k = 0; k <= cnt; k++) ds += k * con[k][j], R += con[k][j]; for (int k = 0; k <= cnt; k++) { R -= con[k][j], L += con[k][j]; con[k][j] = ds * 2; ds += L - R; } } for (int m = 0; m < (1 << S); m++) { if (m & (1 << i)) continue; ll ans = 1e18; auto qry = [&](ll j) { if (j > cnt) return 1ll << 60; ll tmp = (j * (j - 1) + (cnt - j) * (cnt - j - 1)) / 2; for (int k = 0; k < S; k++) if (m & (1 << k)) tmp += con[j][k]; ans = min(ans, tmp); return tmp; }; ll lo = 0, hi = cnt; while (lo <= hi) { ll mi = (lo + hi) / 2; if (qry(mi) <= qry(mi + 1)) hi = mi - 1; else lo = mi + 1; } wt[i][m] = ans; } } dp[0] = 0; for (int i = 1; i < (1 << S); i++) { dp[i] = 1e18; for (int j = 0; j < S; j++) if (i & (1 << j)) dp[i] = min(dp[i], dp[i ^ (1 << j)] + wt[j][i ^ (1 << j)]); } cout << fixed << setprecision(1) << dp[(1 << S) - 1] / 2.0 << endl; 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...