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;
const int MAXN=1e5, MAXK=15;
const long long INF=1e18;
string s;
int n, k;
vector<vector<int> > groups;
double memo[(1<<MAXK)];
double inv[MAXN+1];
double dp(int mask)
{
if (memo[mask]!=-1)
return memo[mask];
if (mask==(1<<k)-1)
return memo[mask]=0;
int prefix[n]={0};
for (int i=0; i<k; i++)
{
if (!(mask&(1<<i)))
continue;
for (auto x : groups[i])
prefix[x]=1;
}
for (int i=1; i<n; i++)
prefix[i]=prefix[i-1]+prefix[i];
int m=prefix[n-1];
double answer=INF;
for (int i=0; i<k; i++)
{
if (mask&(1<<i))
continue;
double mintotal=INF;
long long maininv=0;
int g=groups[i].size();
for (auto x : groups[i])
if (x!=0)
maininv=maininv+prefix[x-1];
mintotal=min(mintotal, inv[g]+maininv);
for (int j=g-1; j>=0; j--)
{
int x=groups[i][j];
if (x!=0)
maininv=maininv-prefix[x-1];
maininv=maininv+(m-prefix[x]);
mintotal=min(mintotal, inv[j]+inv[g-j]+maininv);
}
answer=min(answer, dp(mask|(1<<i))+mintotal);
}
return memo[mask]=answer;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> s;
n=s.size();
map<char, vector<int> > groupsbychar;
for (int i=0; i<n; i++)
groupsbychar[s[i]].push_back(i);
for (auto t : groupsbychar)
groups.push_back(t.second);
k=groups.size();
for (int i=0; i<=n; i++)
inv[i]=(double)i*(i-1)/4;
for (int i=0; i<(1<<k); i++)
memo[i]=-1;
cout << fixed << setprecision(5) << dp(0);
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... |