#include <algorithm>
#include <cassert>
#include <iostream>
#include <limits>
#include <string>
#include <vector>
using namespace std;
using i64 = long long int;
constexpr i64 inf64 = numeric_limits<i64>::max() / 3;
#define ALL(x) (x).begin(), (x).end()
#define REP_3(i, l, r) for (int i = (l); i < (r); ++i)
#define RVP_3(i, l, r) for (int i = (r - 1); i >= (l); --i)
#define REP(i, N) REP_3(i, 0, N)
#define RVP(i, N) RVP_3(i, 0, N)
void answer(const i64 x) {
cout << x / 2;
if (x % 2 == 1) cout << ".5" << endl;
}
template <typename T> void chmin(T &a, const T b) {
if (a > b) a = b;
}
int main() {
string s;
cin >> s;
vector<int> S;
for (const int e : s) S.push_back(e - 'A');
const int N = (int)S.size();
const int G = *max_element(ALL(S)) + 1;
vector<i64> dp(1 << G, inf64);
dp[0] = 0;
auto calc_score = [](vector<int> v) {
assert(all_of(ALL(v), [](int e) { return 0 <= e and e <= 2; }));
const int n = (int)v.size();
vector<int> l_sum(n + 1), r_sum(n + 1);
REP(i, n) l_sum[i + 1] = l_sum[i] + v[i];
RVP(i, n) r_sum[i] = r_sum[i + 1] + v[i];
i64 ret = 0;
REP(i, n) if (v[i] == 1) ret += min(l_sum[i], r_sum[i + 1]);
return ret;
};
REP(bit, 1 << G) {
REP(x, G) {
if (bit & (1 << x)) continue;
vector<int> v(N);
REP(i, N) {
if (bit & (1 << S[i])) {
v[i] = 2;
} else if (S[i] == x) {
v[i] = 1;
}
}
const int cost = calc_score(v);
chmin(dp[bit | (1 << x)], dp[bit] + cost);
}
}
answer(dp[(1 << G) - 1]);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
5 ms |
1996 KB |
Output is correct |
7 |
Incorrect |
5 ms |
2380 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
300 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
2 ms |
212 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
0 ms |
212 KB |
Output is correct |
24 |
Correct |
1 ms |
212 KB |
Output is correct |
25 |
Correct |
1 ms |
212 KB |
Output is correct |
26 |
Correct |
1 ms |
212 KB |
Output is correct |
27 |
Correct |
1 ms |
212 KB |
Output is correct |
28 |
Correct |
1 ms |
212 KB |
Output is correct |
29 |
Correct |
1 ms |
212 KB |
Output is correct |
30 |
Correct |
1 ms |
212 KB |
Output is correct |
31 |
Correct |
1 ms |
212 KB |
Output is correct |
32 |
Correct |
1 ms |
212 KB |
Output is correct |
33 |
Correct |
1 ms |
212 KB |
Output is correct |
34 |
Correct |
1 ms |
212 KB |
Output is correct |
35 |
Correct |
67 ms |
512 KB |
Output is correct |
36 |
Correct |
62 ms |
468 KB |
Output is correct |
37 |
Correct |
638 ms |
516 KB |
Output is correct |
38 |
Correct |
321 ms |
520 KB |
Output is correct |
39 |
Correct |
289 ms |
512 KB |
Output is correct |
40 |
Correct |
322 ms |
516 KB |
Output is correct |
41 |
Correct |
354 ms |
516 KB |
Output is correct |
42 |
Correct |
361 ms |
508 KB |
Output is correct |
43 |
Correct |
370 ms |
516 KB |
Output is correct |
44 |
Correct |
361 ms |
516 KB |
Output is correct |
45 |
Correct |
358 ms |
508 KB |
Output is correct |
46 |
Correct |
370 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
5 ms |
1996 KB |
Output is correct |
7 |
Incorrect |
5 ms |
2380 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |