#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int MAXN = 1e5 + 2;
const int G = 15;
int n, g, cmp[27], pre[MAXN][G], suf[MAXN][G];
bool bio[27];
string s;
ll dp[1 << 15];
vector<int> group[MAXN];
ll f(int x){
return (ll)x * (x - 1);
}
int cnt_lower(int i, int mask){
int ret = 0;
for(int j = 0; j < g; ++j){
if(mask & 1 << j) ret += pre[i][j];
}
return 4 * ret;
}
int cnt_higher(int i, int mask){
int ret = 0;
for(int j = 0; j < g; ++j){
if(mask & 1 << j) ret += suf[i][j];
}
return 4 * ret;
}
int main(){
cin >> s;
n = s.length();
for(char c : s) bio[c - 'A'] = 1;
for(int i = 0; i < 26; ++i){
if(bio[i]) cmp[i] = g++;
}
for(int i = 0; i < n; ++i) group[cmp[s[i] - 'A']].push_back(i);
pre[0][cmp[s[0] - 'A']] = 1;
suf[n - 1][cmp[s[n - 1] - 'A']] = 1;
for(int i = 1; i < n; ++i){
for(int j = 0; j < n; ++j) pre[i][j] = pre[i - 1][j];
++pre[i][cmp[s[i] - 'A']];
}
for(int i = n - 2; i >= 0; --i){
for(int j = 0; j < n; ++j) suf[i][j] = suf[i + 1][j];
++suf[i][cmp[s[i] - 'A']];
}
dp[0] = 0;
for(int i = 1; i < (1 << g); ++i){
dp[i] = 1e18;
for(int j = 0; j < g; ++j){
if(i & 1 << j){
ll cur = 1e18;
int sz = group[j].size();
assert(sz);
vector<ll> lower (sz), higher (sz);
lower[0] = cnt_lower(group[j][0], i ^ 1 << j);
higher[sz - 1] = cnt_higher(group[j][sz - 1], i ^ 1 << j);
for(int idx = 1; idx < sz; ++idx){
lower[idx] = lower[idx - 1] + cnt_lower(group[j][idx], i ^ 1 << j);
}
for(int idx = sz - 2; idx >= 0; --idx){
higher[idx] = higher[idx + 1] + cnt_higher(group[j][idx], i ^ 1 << j);
}
cur = min(higher[0], lower[sz - 1]) + f(sz);
for(int idx = 0; idx < sz - 1; ++idx){
cur = min(cur, lower[idx] + higher[idx + 1] + f(idx + 1) + f(sz - idx - 1));
}
cur += dp[i ^ 1 << j];
dp[i] = min(dp[i], cur);
}
}
}
ll ans = dp[(1 << g) - 1];
cout << fixed << setprecision(7) << (long double)ans / 4LL;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2772 KB |
found '100800.5000000000', expected '100800.5000000000', error '0.0000000000' |
2 |
Correct |
1 ms |
2604 KB |
found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
3 |
Correct |
1 ms |
2644 KB |
found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
4 |
Correct |
1 ms |
2644 KB |
found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
5 |
Correct |
2 ms |
2772 KB |
found '124002.0000000000', expected '124002.0000000000', error '0.0000000000' |
6 |
Execution timed out |
2063 ms |
8564 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
2 |
Correct |
2 ms |
2800 KB |
found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
3 |
Incorrect |
2 ms |
2648 KB |
1st numbers differ - expected: '1023.0000000000', found: '253.0000000000', error = '0.7526881720' |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
2 |
Correct |
2 ms |
2800 KB |
found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
3 |
Incorrect |
2 ms |
2648 KB |
1st numbers differ - expected: '1023.0000000000', found: '253.0000000000', error = '0.7526881720' |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2772 KB |
found '100800.5000000000', expected '100800.5000000000', error '0.0000000000' |
2 |
Correct |
1 ms |
2604 KB |
found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
3 |
Correct |
1 ms |
2644 KB |
found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
4 |
Correct |
1 ms |
2644 KB |
found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
5 |
Correct |
2 ms |
2772 KB |
found '124002.0000000000', expected '124002.0000000000', error '0.0000000000' |
6 |
Execution timed out |
2063 ms |
8564 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |