#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans,dp[1<<15]; //2 times expected value
int m,n,g[100005];
vector<int> group[15];
ll cal(ll a) {
return a*(a-1)/2;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
string s; cin>>s;
n=s.size();
for (int i=0; i<(1<<15); ++i) dp[i]=2e15;
map<char,int> mp;
for (int i=0; i<n; ++i) mp[s[i]]=0;
for (auto k : mp) mp[k.first]=m++;
for (int i=0; i<n; ++i) group[mp[s[i]]].push_back(i), g[i]=mp[s[i]];
dp[0]=0;
for (int mask=1; mask<(1<<m); ++mask) {
//find dp[mask]
bool have[15];
for (int i=0; i<m; ++i) {
if (mask&(1<<i)) have[i]=true;
else have[i]=false;
}
for (int i=0; i<m; ++i) {
if (mask&(1<<i)) { //consider case i is the last boarding group to put in
ll cnt_back=0,sum_back=0,cnt_front=0,sum_front=0,cb=0,cf=0;
for (int x=n-1; x>=0; --x) {
if (have[g[x]]) {
if (g[x]!=i) ++cnt_back;
else sum_back+=cnt_back, ++cb;
}
}
for (int x=0; x<n-1; ++x) { //people 0 to x get in from front, x+1 to n-1 get in from back
if (have[g[x]]) {
if (g[x]!=i) {
++cnt_front;
--cnt_back;
} else {
++cf;
--cb;
sum_front+=cnt_front;
sum_back-=cnt_back;
dp[mask]=min(dp[mask],dp[mask^(1<<i)]+cal(cf)+cal(cb)+2*sum_back+2*sum_front);
}
}
}
}
}
}
cout<<dp[(1<<m)-1]/2;
if (dp[(1<<m)-1]%2==1) cout<<".5";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
found '100800.5000000000', expected '100800.5000000000', error '0.0000000000' |
2 |
Incorrect |
1 ms |
468 KB |
1st numbers differ - expected: '0.0000000000', found: '1000000000000000.0000000000', error = '1000000000000000.0000000000' |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
2 |
Correct |
0 ms |
468 KB |
found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
3 |
Correct |
1 ms |
468 KB |
found '1023.0000000000', expected '1023.0000000000', error '0.0000000000' |
4 |
Correct |
0 ms |
468 KB |
found '294.0000000000', expected '294.0000000000', error '0.0000000000' |
5 |
Correct |
1 ms |
468 KB |
found '1087.0000000000', expected '1087.0000000000', error '0.0000000000' |
6 |
Correct |
0 ms |
468 KB |
found '1.5000000000', expected '1.5000000000', error '0.0000000000' |
7 |
Correct |
1 ms |
468 KB |
found '703.0000000000', expected '703.0000000000', error '0.0000000000' |
8 |
Incorrect |
0 ms |
468 KB |
1st numbers differ - expected: '55.5000000000', found: '59.0000000000', error = '0.0630630631' |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
2 |
Correct |
0 ms |
468 KB |
found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
3 |
Correct |
1 ms |
468 KB |
found '1023.0000000000', expected '1023.0000000000', error '0.0000000000' |
4 |
Correct |
0 ms |
468 KB |
found '294.0000000000', expected '294.0000000000', error '0.0000000000' |
5 |
Correct |
1 ms |
468 KB |
found '1087.0000000000', expected '1087.0000000000', error '0.0000000000' |
6 |
Correct |
0 ms |
468 KB |
found '1.5000000000', expected '1.5000000000', error '0.0000000000' |
7 |
Correct |
1 ms |
468 KB |
found '703.0000000000', expected '703.0000000000', error '0.0000000000' |
8 |
Incorrect |
0 ms |
468 KB |
1st numbers differ - expected: '55.5000000000', found: '59.0000000000', error = '0.0630630631' |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
found '100800.5000000000', expected '100800.5000000000', error '0.0000000000' |
2 |
Incorrect |
1 ms |
468 KB |
1st numbers differ - expected: '0.0000000000', found: '1000000000000000.0000000000', error = '1000000000000000.0000000000' |
3 |
Halted |
0 ms |
0 KB |
- |