#include <stdio.h>
#include <string.h>
#define N 100000
#define A 15
long long min(long long a, long long b) { return a < b ? a : b; }
int main() {
static char cc[N + 1];
static int ii[A][N], kk[N], ll[A][N];
static long long dp[A][A][N + 1], dq[A][1 << A], dr[1 << A];
int n, h, i, a, a_, b, lower, upper;
long long x;
scanf("%s", cc), n = strlen(cc);
for (i = 0; i < n; i++) {
a = cc[i] - 'A';
for (a_ = 0; a_ < A; a_++)
ll[a_][i] = kk[a_];
ii[a][kk[a]++] = i;
}
for (a = 0; a < A; a++)
for (a_ = 0; a_ < A; a_++) {
for (h = 0; h < kk[a]; h++) {
i = ii[a][h];
dp[a][a_][0] += kk[a_] - ll[a_][i];
}
for (h = 0; h < kk[a]; h++) {
i = ii[a][h];
dp[a][a_][h + 1] = dp[a][a_][h] + ll[a_][i] * 2 - kk[a_];
}
}
for (b = 0; b < 1 << A; b++)
for (a = 0; a < A; a++)
if ((b & 1 << a) == 0) {
lower = -1, upper = kk[a];
while (upper - lower > 1) {
h = (lower + upper) / 2;
i = ii[a][h];
x = h - (kk[a] - 1 - h);
for (a_ = 0; a_ < A; a_++)
if ((b & 1 << a_) != 0)
x += (dp[a][a_][h + 1] - dp[a][a_][h]) * 2;
if (x > 0)
upper = h;
else
lower = h;
}
h = upper;
dq[a][b] = (long long) h * (h - 1) / 2 + (long long) (kk[a] - h) * (kk[a] - h - 1) / 2;
for (a_ = 0; a_ < A; a_++)
if ((b & 1 << a_) != 0)
dq[a][b] += dp[a][a_][h] * 2;
}
memset(dr, 0x3f, (1 << A) * sizeof *dr);
dr[0] = 0;
for (b = 0; b < 1 << A; b++)
for (a = 0; a < A; a++)
if ((b & 1 << a) == 0)
dr[b | 1 << a] = min(dr[b | 1 << a], dr[b] + dq[a][b]);
printf("%lld.%lld\n", dr[(1 << A) - 1] / 2, dr[(1 << A) - 1] % 2 * 5);
return 0;
}
Compilation message
passes.c: In function 'main':
passes.c:16:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
16 | scanf("%s", cc), n = strlen(cc);
| ^~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
20 ms |
4436 KB |
Output is correct |
2 |
Incorrect |
16 ms |
4276 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
19 ms |
4440 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
19 ms |
4440 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
20 ms |
4436 KB |
Output is correct |
2 |
Incorrect |
16 ms |
4276 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |