This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |