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>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#define int long long
using namespace std;
int f(int x){
return x * (x - 1) / 2;
}
const int G = 15;
const int N = 1e5 + 11;
int L[G][G][N], R[G][G][N];
int cL[G][N], cR[G][N];
int dp[1 << G];
int32_t main(){
string s; cin >> s;
int n = s.size();
for(int i = 0; i < G; i++){
for(int j = 0; j < G; j++){
// add char i then char j
L[i][j][0] = 0; int m = 0;
for(int k = 0; k < n; k++){
if(s[k] == 'A' + i){
m += 2;
L[i][j][k + 1] = L[i][j][k];
}else if(s[k] == 'A' + j){
L[i][j][k + 1] = L[i][j][k] + m;
}else{
L[i][j][k + 1] = L[i][j][k];
}
}
R[i][j][n] = 0; m = 0;
for(int k = n - 1; k >= 0; k--){
if(s[k] == 'A' + i){
m += 2;
R[i][j][k] = R[i][j][k + 1];
}else if(s[k] == 'A' + j){
R[i][j][k] = R[i][j][k + 1] + m;
}else{
R[i][j][k] = R[i][j][k + 1];
}
}
}
}
for(int i = 0; i < G; i++){
cL[i][0] = 0; int m = 0;
for(int j = 0; j < n; j++){
if(s[j] == 'A' + i){
cL[i][j + 1] = cL[i][j] + m; m++;
}else{
cL[i][j + 1] = cL[i][j];
}
}
cR[i][n] = 0; m = 0;
for(int j = n - 1; j >= 0; j--){
if(s[j] == 'A' + i){
cR[i][j] = cR[i][j + 1] + m; m++;
}else{
cR[i][j] = cR[i][j + 1];
}
}
}
dp[0] = 0; fill(dp + 1, dp + (1 << G), 1LL << 60);
for(int mask = 1; mask < (1 << G); mask++){
for(int j = 0; j < G; j++){
if(mask & (1 << j)){
int cost = 1LL << 60;
for(int x = 0; x <= n; x++){
int c = cL[j][x] + cR[j][x];
for(int k = 0; k < G; k++){
if(j != k && (mask & (1 << k))){
c += L[k][j][x] + R[k][j][x];
}
}
cost = min(cost, c);
}
dp[mask] = min(dp[mask], dp[mask - (1 << j)] + cost);
}
}
}
cout << setprecision(10) << fixed << ((long double) dp[(1 << G) - 1] / 2) << endl;
}
# | 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... |