// author: erray
#undef DEBUG
#include <bits/stdc++.h>
#ifdef DEBUG
#include "debug.h"
#else
#define debug(...) void(37)
#endif
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
string S;
cin >> S;
int N = int(S.size());
int G = (*max_element(S.begin(), S.end())) - 'A' + 1;
vector<vector<int>> pref(G, vector<int>(N + 1));
vector<vector<int>> occ(G);
vector<vector<vector<long long>>> contrib(G, vector<vector<long long>>(G, vector<long long>(N + 1)));
for (int l = 0; l < G; ++l) {
for (int i = 0; i < N; ++i) {
bool me = S[i] == ('A' + l);
if (me) {
occ[l].push_back(i);
}
pref[l][i + 1] = pref[l][i] + me;
}
}
for (int l = 0; l < G; ++l) {
for (int i = 0; i < N; ++i) {
bool me = S[i] == ('A' + l);
for (int j = 0; j < G; ++j) {
contrib[j][l][i + 1] = contrib[j][l][i];
if (me) {
contrib[j][l][i + 1] += pref[j][i];
}
}
}
}
debug(pref, contrib);
auto Sq = [&](int x) {
return 1LL * x * (x - 1) / 2;
};
vector<long long> best(1 << G, 1LL * N * N);
best[0] = 0;
vector<int> lg(1 << G);
for (int m = 0; m < (1 << G); ++m) {
if (m > 0) { lg[m] = __lg(m); }
for (int i = 0; i < G; ++i) {
if ((m >> i) % 2 == 0) {
auto E = [&](int s) {
int x = 0;
if (s > 0) {
x = occ[i][s - 1] + 1;
}
int cm = m;
long long res = 0;
while (cm > 0) {
int l = lg[cm];
debug(l, i);
long long add = 2 * (contrib[l][i][x] + (contrib[i][l][N] - contrib[i][l][x] - 1LL * s * (pref[l][N] - pref[l][x])));
assert(add >= 0);
res += add;
cm ^= 1 << l;
}
res += Sq(s) + Sq(pref[i][N] - s);
return res;
};
int low = 0, high = int(occ[i].size());
while (low < high) {
int mid = (low + high) >> 1;
debug(mid, E(mid), E(mid + 1));
if (E(mid) > E(mid + 1)) {
low = mid + 1;
} else {
high = mid;
}
}
debug(m, i, low, E(low));
int next = m | (1 << i);
best[next] = min(best[next], best[m] + E(low));
}
}
}
long long ans = best[(1 << G) - 1];
cout << setprecision(2) << (long double) 0.5 * ans << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
320 KB |
1st numbers differ - expected: '100800.5000000000', found: '100000.0000000000', error = '0.0079414289' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
324 KB |
found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
2 |
Incorrect |
1 ms |
212 KB |
1st numbers differ - expected: '1225.0000000000', found: '1200.0000000000', error = '0.0204081633' |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
324 KB |
found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
2 |
Incorrect |
1 ms |
212 KB |
1st numbers differ - expected: '1225.0000000000', found: '1200.0000000000', error = '0.0204081633' |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
320 KB |
1st numbers differ - expected: '100800.5000000000', found: '100000.0000000000', error = '0.0079414289' |
2 |
Halted |
0 ms |
0 KB |
- |