#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const int N = 100000;
const int C = 15;
ll dp[N+5];
vector <int> vec[C+1];
ll levo[C+1][N+5];
ll desno[C+1][N+5];
ll plevo[C+1][N+5];
ll pdesno[C+1][N+5];
int main(){
ios_base::sync_with_stdio(false), cin.tie(0);
cout.precision(1);
cout << fixed;
string s;
cin >> s;
int n = s.size();
for(int i=0; i<n; i++){
vec[s[i] - 'A'].push_back(i + 1);
}
for(int i=0; i<C; i++){
for(int j=0; j<C; j++){
if(i == j){
ll p = 0;
for(int k=0; k<vec[j].size(); k++){
levo[i][vec[j][k]] = p;
plevo[i][vec[j][k]] = p*(p+1)/2;
p++;
}
p = 0;
for(int k=int(vec[j].size())-1; k>=0; k--){
desno[i][vec[j][k]] = p;
pdesno[i][vec[j][k]] = p*(p+1)/2;
p++;
}
}
else{
ll tr = 0;
int d = 0;
for(int k=0; k<vec[j].size(); k++){
while(d < vec[i].size() && vec[i][d] < vec[j][k]){
d++;
}
levo[i][vec[j][k]] = 2*d;
tr += 2*d;
plevo[i][vec[j][k]] = tr;
}
tr = 0, d = int(vec[i].size()) - 1;
for(int k=int(vec[j].size())-1; k>=0; k--){
while(d >= 0 && vec[i][d] > vec[j][k]){
d--;
}
desno[i][vec[j][k]] = 2*(int(vec[i].size()) - d - 1);
tr += 2*(int(vec[i].size()) - d - 1);
pdesno[i][vec[j][k]] = tr;
}
}
}
}
for(int mask=1; mask<(1<<C); mask++){
dp[mask] = 1e18;
bool em = 0;
for(int i=0; i<C; i++){
if((mask & (1 << i)) && vec[i].size() == 0){
dp[mask] = dp[mask ^ (1 << i)];
em = 1;
break;
}
}
if(em) continue;
for(int i=0; i<C; i++){
if(!((1 << i) & mask)) continue;
int sub = mask ^ (1 << i);
int l = 0, r = vec[i].size() - 1, d = -1;
while(l <= r){
int mid = (l+r)/2;
ll ul = 0, ud = 0;
for(int j=0; j<C; j++){
if(mask & (1 << j)){
ul += levo[j][vec[i][mid]];
ud += desno[j][vec[i][mid]];
}
}
if(ul <= ud){
d = mid;
l = mid + 1;
}
else r = mid - 1;
}
ll tot = 0;
for(int j=0; j<C; j++){
if(mask & (1 << j)){
if(d >= 0) tot += plevo[j][vec[i][d]];
if(d < int(vec[i].size()) - 1) tot += pdesno[j][vec[i][d+1]];
}
}
dp[mask] = min(dp[mask], dp[sub] + tot);
}
}
ll k = dp[(1<<C)-1];
if(k%2 == 0) cout << k/2 << "\n";
else cout << 1.0*k/2 << "\n";
return 0;
}
Compilation message
passes.cpp: In function 'int main()':
passes.cpp:34:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | for(int k=0; k<vec[j].size(); k++){
| ~^~~~~~~~~~~~~~
passes.cpp:49:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for(int k=0; k<vec[j].size(); k++){
| ~^~~~~~~~~~~~~~
passes.cpp:50:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | while(d < vec[i].size() && vec[i][d] < vec[j][k]){
| ~~^~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1236 KB |
Output is correct |
2 |
Correct |
1 ms |
852 KB |
Output is correct |
3 |
Correct |
1 ms |
852 KB |
Output is correct |
4 |
Correct |
1 ms |
852 KB |
Output is correct |
5 |
Correct |
1 ms |
1364 KB |
Output is correct |
6 |
Correct |
21 ms |
38316 KB |
Output is correct |
7 |
Correct |
26 ms |
45596 KB |
Output is correct |
8 |
Correct |
29 ms |
48264 KB |
Output is correct |
9 |
Correct |
31 ms |
48268 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
852 KB |
Output is correct |
2 |
Correct |
1 ms |
852 KB |
Output is correct |
3 |
Correct |
1 ms |
852 KB |
Output is correct |
4 |
Correct |
1 ms |
968 KB |
Output is correct |
5 |
Correct |
2 ms |
852 KB |
Output is correct |
6 |
Correct |
1 ms |
852 KB |
Output is correct |
7 |
Correct |
2 ms |
852 KB |
Output is correct |
8 |
Correct |
1 ms |
852 KB |
Output is correct |
9 |
Correct |
2 ms |
852 KB |
Output is correct |
10 |
Correct |
2 ms |
852 KB |
Output is correct |
11 |
Correct |
2 ms |
852 KB |
Output is correct |
12 |
Correct |
1 ms |
852 KB |
Output is correct |
13 |
Correct |
1 ms |
852 KB |
Output is correct |
14 |
Correct |
2 ms |
852 KB |
Output is correct |
15 |
Correct |
1 ms |
852 KB |
Output is correct |
16 |
Correct |
2 ms |
852 KB |
Output is correct |
17 |
Correct |
2 ms |
852 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
852 KB |
Output is correct |
2 |
Correct |
1 ms |
852 KB |
Output is correct |
3 |
Correct |
1 ms |
852 KB |
Output is correct |
4 |
Correct |
1 ms |
968 KB |
Output is correct |
5 |
Correct |
2 ms |
852 KB |
Output is correct |
6 |
Correct |
1 ms |
852 KB |
Output is correct |
7 |
Correct |
2 ms |
852 KB |
Output is correct |
8 |
Correct |
1 ms |
852 KB |
Output is correct |
9 |
Correct |
2 ms |
852 KB |
Output is correct |
10 |
Correct |
2 ms |
852 KB |
Output is correct |
11 |
Correct |
2 ms |
852 KB |
Output is correct |
12 |
Correct |
1 ms |
852 KB |
Output is correct |
13 |
Correct |
1 ms |
852 KB |
Output is correct |
14 |
Correct |
2 ms |
852 KB |
Output is correct |
15 |
Correct |
1 ms |
852 KB |
Output is correct |
16 |
Correct |
2 ms |
852 KB |
Output is correct |
17 |
Correct |
2 ms |
852 KB |
Output is correct |
18 |
Correct |
1 ms |
852 KB |
Output is correct |
19 |
Correct |
1 ms |
852 KB |
Output is correct |
20 |
Correct |
2 ms |
852 KB |
Output is correct |
21 |
Correct |
2 ms |
852 KB |
Output is correct |
22 |
Correct |
2 ms |
852 KB |
Output is correct |
23 |
Correct |
2 ms |
852 KB |
Output is correct |
24 |
Correct |
2 ms |
852 KB |
Output is correct |
25 |
Correct |
1 ms |
852 KB |
Output is correct |
26 |
Correct |
2 ms |
852 KB |
Output is correct |
27 |
Correct |
1 ms |
852 KB |
Output is correct |
28 |
Correct |
1 ms |
852 KB |
Output is correct |
29 |
Correct |
1 ms |
852 KB |
Output is correct |
30 |
Correct |
1 ms |
852 KB |
Output is correct |
31 |
Correct |
1 ms |
852 KB |
Output is correct |
32 |
Correct |
1 ms |
852 KB |
Output is correct |
33 |
Correct |
1 ms |
852 KB |
Output is correct |
34 |
Correct |
1 ms |
852 KB |
Output is correct |
35 |
Correct |
4 ms |
5716 KB |
Output is correct |
36 |
Correct |
4 ms |
5716 KB |
Output is correct |
37 |
Correct |
8 ms |
5620 KB |
Output is correct |
38 |
Correct |
7 ms |
5588 KB |
Output is correct |
39 |
Correct |
5 ms |
5716 KB |
Output is correct |
40 |
Correct |
6 ms |
5588 KB |
Output is correct |
41 |
Correct |
6 ms |
5616 KB |
Output is correct |
42 |
Correct |
7 ms |
5588 KB |
Output is correct |
43 |
Correct |
6 ms |
5588 KB |
Output is correct |
44 |
Correct |
7 ms |
5588 KB |
Output is correct |
45 |
Correct |
7 ms |
5588 KB |
Output is correct |
46 |
Correct |
6 ms |
5588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1236 KB |
Output is correct |
2 |
Correct |
1 ms |
852 KB |
Output is correct |
3 |
Correct |
1 ms |
852 KB |
Output is correct |
4 |
Correct |
1 ms |
852 KB |
Output is correct |
5 |
Correct |
1 ms |
1364 KB |
Output is correct |
6 |
Correct |
21 ms |
38316 KB |
Output is correct |
7 |
Correct |
26 ms |
45596 KB |
Output is correct |
8 |
Correct |
29 ms |
48264 KB |
Output is correct |
9 |
Correct |
31 ms |
48268 KB |
Output is correct |
10 |
Correct |
1 ms |
852 KB |
Output is correct |
11 |
Correct |
1 ms |
852 KB |
Output is correct |
12 |
Correct |
1 ms |
852 KB |
Output is correct |
13 |
Correct |
1 ms |
968 KB |
Output is correct |
14 |
Correct |
2 ms |
852 KB |
Output is correct |
15 |
Correct |
1 ms |
852 KB |
Output is correct |
16 |
Correct |
2 ms |
852 KB |
Output is correct |
17 |
Correct |
1 ms |
852 KB |
Output is correct |
18 |
Correct |
2 ms |
852 KB |
Output is correct |
19 |
Correct |
2 ms |
852 KB |
Output is correct |
20 |
Correct |
2 ms |
852 KB |
Output is correct |
21 |
Correct |
1 ms |
852 KB |
Output is correct |
22 |
Correct |
1 ms |
852 KB |
Output is correct |
23 |
Correct |
2 ms |
852 KB |
Output is correct |
24 |
Correct |
1 ms |
852 KB |
Output is correct |
25 |
Correct |
2 ms |
852 KB |
Output is correct |
26 |
Correct |
2 ms |
852 KB |
Output is correct |
27 |
Correct |
1 ms |
852 KB |
Output is correct |
28 |
Correct |
1 ms |
852 KB |
Output is correct |
29 |
Correct |
2 ms |
852 KB |
Output is correct |
30 |
Correct |
2 ms |
852 KB |
Output is correct |
31 |
Correct |
2 ms |
852 KB |
Output is correct |
32 |
Correct |
2 ms |
852 KB |
Output is correct |
33 |
Correct |
2 ms |
852 KB |
Output is correct |
34 |
Correct |
1 ms |
852 KB |
Output is correct |
35 |
Correct |
2 ms |
852 KB |
Output is correct |
36 |
Correct |
1 ms |
852 KB |
Output is correct |
37 |
Correct |
1 ms |
852 KB |
Output is correct |
38 |
Correct |
1 ms |
852 KB |
Output is correct |
39 |
Correct |
1 ms |
852 KB |
Output is correct |
40 |
Correct |
1 ms |
852 KB |
Output is correct |
41 |
Correct |
1 ms |
852 KB |
Output is correct |
42 |
Correct |
1 ms |
852 KB |
Output is correct |
43 |
Correct |
1 ms |
852 KB |
Output is correct |
44 |
Correct |
4 ms |
5716 KB |
Output is correct |
45 |
Correct |
4 ms |
5716 KB |
Output is correct |
46 |
Correct |
8 ms |
5620 KB |
Output is correct |
47 |
Correct |
7 ms |
5588 KB |
Output is correct |
48 |
Correct |
5 ms |
5716 KB |
Output is correct |
49 |
Correct |
6 ms |
5588 KB |
Output is correct |
50 |
Correct |
6 ms |
5616 KB |
Output is correct |
51 |
Correct |
7 ms |
5588 KB |
Output is correct |
52 |
Correct |
6 ms |
5588 KB |
Output is correct |
53 |
Correct |
7 ms |
5588 KB |
Output is correct |
54 |
Correct |
7 ms |
5588 KB |
Output is correct |
55 |
Correct |
6 ms |
5588 KB |
Output is correct |
56 |
Correct |
1 ms |
852 KB |
Output is correct |
57 |
Correct |
34 ms |
852 KB |
Output is correct |
58 |
Correct |
1 ms |
1236 KB |
Output is correct |
59 |
Correct |
1 ms |
852 KB |
Output is correct |
60 |
Correct |
1 ms |
852 KB |
Output is correct |
61 |
Correct |
1 ms |
852 KB |
Output is correct |
62 |
Correct |
1 ms |
1364 KB |
Output is correct |
63 |
Correct |
24 ms |
38288 KB |
Output is correct |
64 |
Correct |
26 ms |
45604 KB |
Output is correct |
65 |
Correct |
29 ms |
48236 KB |
Output is correct |
66 |
Correct |
30 ms |
48272 KB |
Output is correct |
67 |
Correct |
1 ms |
852 KB |
Output is correct |
68 |
Correct |
1 ms |
852 KB |
Output is correct |
69 |
Correct |
1 ms |
852 KB |
Output is correct |
70 |
Correct |
1 ms |
852 KB |
Output is correct |
71 |
Correct |
1 ms |
852 KB |
Output is correct |
72 |
Correct |
1 ms |
852 KB |
Output is correct |
73 |
Correct |
1 ms |
852 KB |
Output is correct |
74 |
Correct |
1 ms |
852 KB |
Output is correct |
75 |
Correct |
1 ms |
852 KB |
Output is correct |
76 |
Correct |
2 ms |
852 KB |
Output is correct |
77 |
Correct |
2 ms |
852 KB |
Output is correct |
78 |
Correct |
1 ms |
852 KB |
Output is correct |
79 |
Correct |
2 ms |
852 KB |
Output is correct |
80 |
Correct |
2 ms |
852 KB |
Output is correct |
81 |
Correct |
1 ms |
852 KB |
Output is correct |
82 |
Correct |
2 ms |
880 KB |
Output is correct |
83 |
Correct |
1 ms |
852 KB |
Output is correct |
84 |
Correct |
4 ms |
5716 KB |
Output is correct |
85 |
Correct |
4 ms |
5716 KB |
Output is correct |
86 |
Correct |
7 ms |
5588 KB |
Output is correct |
87 |
Correct |
7 ms |
5588 KB |
Output is correct |
88 |
Correct |
6 ms |
5716 KB |
Output is correct |
89 |
Correct |
7 ms |
5556 KB |
Output is correct |
90 |
Correct |
8 ms |
5588 KB |
Output is correct |
91 |
Correct |
7 ms |
5588 KB |
Output is correct |
92 |
Correct |
6 ms |
5588 KB |
Output is correct |
93 |
Correct |
7 ms |
5496 KB |
Output is correct |
94 |
Correct |
6 ms |
5588 KB |
Output is correct |
95 |
Correct |
6 ms |
5612 KB |
Output is correct |
96 |
Correct |
166 ms |
48132 KB |
Output is correct |
97 |
Correct |
20 ms |
844 KB |
Output is correct |
98 |
Correct |
186 ms |
48212 KB |
Output is correct |
99 |
Correct |
69 ms |
48296 KB |
Output is correct |
100 |
Correct |
29 ms |
844 KB |
Output is correct |
101 |
Correct |
111 ms |
48128 KB |
Output is correct |
102 |
Correct |
126 ms |
48176 KB |
Output is correct |
103 |
Correct |
126 ms |
48204 KB |
Output is correct |
104 |
Correct |
130 ms |
48180 KB |
Output is correct |
105 |
Correct |
127 ms |
48132 KB |
Output is correct |
106 |
Correct |
124 ms |
48168 KB |
Output is correct |
107 |
Correct |
131 ms |
48248 KB |
Output is correct |
108 |
Correct |
91 ms |
48236 KB |
Output is correct |
109 |
Correct |
129 ms |
48228 KB |
Output is correct |