# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
868028 | 2023-10-30T08:53:36 Z | TAhmed33 | Boarding Passes (BOI22_passes) | C++ | 2000 ms | 21844 KB |
#include <bits/stdc++.h> using namespace std; typedef long double ld; typedef long long ll; string s; int n; vector <int> pos[26]; int val[100001][26]; int val2[100001][26]; ld dp[(1 << 15)]; vector <int> dd; int cnt; ld ans (int mask) { ld &ret = dp[mask]; if (ret == ret) return ret; ret = 1e18; if (mask == (1 << cnt) - 1) return ret = 0; for (int i = 0; i < cnt; i++) { if (mask & (1 << i)) continue; int m = pos[dd[i]].size(); ld sum = 0; for (int j = 0; j < m; j++) { int ret1 = 0, ret2 = 0; for (int k = 0; k < cnt; k++) { if (mask & (1 << k)) { ret1 += val[pos[dd[i]][j]][dd[k]]; ret2 += val2[pos[dd[i]][j]][dd[k]]; } } sum += min(ret1 + j * 0.5, ret2 + (m - j - 1) * 0.5); } ret = min(ret, sum + ans(mask ^ (1 << i))); } return ret; } int main () { memset(dp, -1, sizeof(dp)); cin >> s; n = s.length(); for (int i = 0; i < n; i++) { pos[s[i] - 'A'].push_back(i); } int x = 0; for (int i = 1; i < 26; i++) if (!pos[i].empty()) x = i; for (int i = 0; i <= x; i++) if (!pos[i].empty()) dd.push_back(i); cnt = dd.size(); for (int i = 0; i < n; i++) { for (int j = 0; j < 26; j++) { if (pos[j].empty()) continue; if (s[i] - 'A' == j) continue; int l = 0, r = (int)pos[j].size() - 1, ans = 0; while (l <= r) { int m = (l + r) >> 1; if (pos[j][m] < i) { l = m + 1; ans = m + 1; } else { r = m - 1; } } val[i][j] = ans; val2[i][j] = (int)pos[j].size() - ans; } } cout << fixed << setprecision(6) << ans(0) << '\n'; }
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2652 KB | found '100800.5000000000', expected '100800.5000000000', error '0.0000000000' |
2 | Correct | 0 ms | 2652 KB | found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
3 | Correct | 0 ms | 2652 KB | found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
4 | Correct | 1 ms | 2652 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
5 | Correct | 1 ms | 2652 KB | found '124002.0000000000', expected '124002.0000000000', error '0.0000000000' |
6 | Correct | 5 ms | 3288 KB | found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000' |
7 | Correct | 4 ms | 3288 KB | found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000' |
8 | Correct | 5 ms | 3288 KB | found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000' |
9 | Correct | 5 ms | 3288 KB | found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000' |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 4700 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
2 | Correct | 1 ms | 2652 KB | found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
3 | Correct | 2 ms | 4700 KB | found '1023.0000000000', expected '1023.0000000000', error '0.0000000000' |
4 | Correct | 1 ms | 4700 KB | found '294.0000000000', expected '294.0000000000', error '0.0000000000' |
5 | Correct | 1 ms | 4700 KB | found '1087.0000000000', expected '1087.0000000000', error '0.0000000000' |
6 | Correct | 1 ms | 4700 KB | found '1.5000000000', expected '1.5000000000', error '0.0000000000' |
7 | Correct | 1 ms | 4700 KB | found '703.0000000000', expected '703.0000000000', error '0.0000000000' |
8 | Correct | 1 ms | 4700 KB | found '55.5000000000', expected '55.5000000000', error '0.0000000000' |
9 | Correct | 1 ms | 4700 KB | found '56.0000000000', expected '56.0000000000', error '0.0000000000' |
10 | Correct | 1 ms | 4700 KB | found '45.0000000000', expected '45.0000000000', error '0.0000000000' |
11 | Correct | 1 ms | 4952 KB | found '66.5000000000', expected '66.5000000000', error '0.0000000000' |
12 | Correct | 1 ms | 4700 KB | found '67.0000000000', expected '67.0000000000', error '0.0000000000' |
13 | Correct | 1 ms | 4700 KB | found '66.0000000000', expected '66.0000000000', error '0.0000000000' |
14 | Correct | 1 ms | 4700 KB | found '47.0000000000', expected '47.0000000000', error '0.0000000000' |
15 | Correct | 1 ms | 4700 KB | found '50.0000000000', expected '50.0000000000', error '0.0000000000' |
16 | Correct | 1 ms | 4700 KB | found '49.0000000000', expected '49.0000000000', error '0.0000000000' |
17 | Correct | 1 ms | 4700 KB | found '57.0000000000', expected '57.0000000000', error '0.0000000000' |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 4700 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
2 | Correct | 1 ms | 2652 KB | found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
3 | Correct | 2 ms | 4700 KB | found '1023.0000000000', expected '1023.0000000000', error '0.0000000000' |
4 | Correct | 1 ms | 4700 KB | found '294.0000000000', expected '294.0000000000', error '0.0000000000' |
5 | Correct | 1 ms | 4700 KB | found '1087.0000000000', expected '1087.0000000000', error '0.0000000000' |
6 | Correct | 1 ms | 4700 KB | found '1.5000000000', expected '1.5000000000', error '0.0000000000' |
7 | Correct | 1 ms | 4700 KB | found '703.0000000000', expected '703.0000000000', error '0.0000000000' |
8 | Correct | 1 ms | 4700 KB | found '55.5000000000', expected '55.5000000000', error '0.0000000000' |
9 | Correct | 1 ms | 4700 KB | found '56.0000000000', expected '56.0000000000', error '0.0000000000' |
10 | Correct | 1 ms | 4700 KB | found '45.0000000000', expected '45.0000000000', error '0.0000000000' |
11 | Correct | 1 ms | 4952 KB | found '66.5000000000', expected '66.5000000000', error '0.0000000000' |
12 | Correct | 1 ms | 4700 KB | found '67.0000000000', expected '67.0000000000', error '0.0000000000' |
13 | Correct | 1 ms | 4700 KB | found '66.0000000000', expected '66.0000000000', error '0.0000000000' |
14 | Correct | 1 ms | 4700 KB | found '47.0000000000', expected '47.0000000000', error '0.0000000000' |
15 | Correct | 1 ms | 4700 KB | found '50.0000000000', expected '50.0000000000', error '0.0000000000' |
16 | Correct | 1 ms | 4700 KB | found '49.0000000000', expected '49.0000000000', error '0.0000000000' |
17 | Correct | 1 ms | 4700 KB | found '57.0000000000', expected '57.0000000000', error '0.0000000000' |
18 | Correct | 1 ms | 4696 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
19 | Correct | 1 ms | 2652 KB | found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
20 | Correct | 1 ms | 4700 KB | found '1023.0000000000', expected '1023.0000000000', error '0.0000000000' |
21 | Correct | 1 ms | 4700 KB | found '294.0000000000', expected '294.0000000000', error '0.0000000000' |
22 | Correct | 1 ms | 4696 KB | found '1087.0000000000', expected '1087.0000000000', error '0.0000000000' |
23 | Correct | 1 ms | 4700 KB | found '1.5000000000', expected '1.5000000000', error '0.0000000000' |
24 | Correct | 1 ms | 4700 KB | found '703.0000000000', expected '703.0000000000', error '0.0000000000' |
25 | Correct | 1 ms | 4700 KB | found '55.5000000000', expected '55.5000000000', error '0.0000000000' |
26 | Correct | 1 ms | 4700 KB | found '56.0000000000', expected '56.0000000000', error '0.0000000000' |
27 | Correct | 1 ms | 4700 KB | found '45.0000000000', expected '45.0000000000', error '0.0000000000' |
28 | Correct | 1 ms | 4700 KB | found '66.5000000000', expected '66.5000000000', error '0.0000000000' |
29 | Correct | 1 ms | 4700 KB | found '67.0000000000', expected '67.0000000000', error '0.0000000000' |
30 | Correct | 1 ms | 4696 KB | found '66.0000000000', expected '66.0000000000', error '0.0000000000' |
31 | Correct | 1 ms | 4696 KB | found '47.0000000000', expected '47.0000000000', error '0.0000000000' |
32 | Correct | 1 ms | 4700 KB | found '50.0000000000', expected '50.0000000000', error '0.0000000000' |
33 | Correct | 1 ms | 4704 KB | found '49.0000000000', expected '49.0000000000', error '0.0000000000' |
34 | Correct | 1 ms | 4700 KB | found '57.0000000000', expected '57.0000000000', error '0.0000000000' |
35 | Correct | 1 ms | 2652 KB | found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000' |
36 | Correct | 2 ms | 2652 KB | found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000' |
37 | Correct | 84 ms | 4792 KB | found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000' |
38 | Correct | 54 ms | 5016 KB | found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000' |
39 | Correct | 54 ms | 4832 KB | found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000' |
40 | Correct | 62 ms | 4704 KB | found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000' |
41 | Correct | 71 ms | 4700 KB | found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000' |
42 | Correct | 70 ms | 4800 KB | found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000' |
43 | Correct | 67 ms | 4696 KB | found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000' |
44 | Correct | 64 ms | 4700 KB | found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000' |
45 | Correct | 74 ms | 4700 KB | found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000' |
46 | Correct | 73 ms | 4804 KB | found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000' |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2652 KB | found '100800.5000000000', expected '100800.5000000000', error '0.0000000000' |
2 | Correct | 0 ms | 2652 KB | found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
3 | Correct | 0 ms | 2652 KB | found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
4 | Correct | 1 ms | 2652 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
5 | Correct | 1 ms | 2652 KB | found '124002.0000000000', expected '124002.0000000000', error '0.0000000000' |
6 | Correct | 5 ms | 3288 KB | found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000' |
7 | Correct | 4 ms | 3288 KB | found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000' |
8 | Correct | 5 ms | 3288 KB | found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000' |
9 | Correct | 5 ms | 3288 KB | found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000' |
10 | Correct | 1 ms | 4700 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
11 | Correct | 1 ms | 2652 KB | found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
12 | Correct | 2 ms | 4700 KB | found '1023.0000000000', expected '1023.0000000000', error '0.0000000000' |
13 | Correct | 1 ms | 4700 KB | found '294.0000000000', expected '294.0000000000', error '0.0000000000' |
14 | Correct | 1 ms | 4700 KB | found '1087.0000000000', expected '1087.0000000000', error '0.0000000000' |
15 | Correct | 1 ms | 4700 KB | found '1.5000000000', expected '1.5000000000', error '0.0000000000' |
16 | Correct | 1 ms | 4700 KB | found '703.0000000000', expected '703.0000000000', error '0.0000000000' |
17 | Correct | 1 ms | 4700 KB | found '55.5000000000', expected '55.5000000000', error '0.0000000000' |
18 | Correct | 1 ms | 4700 KB | found '56.0000000000', expected '56.0000000000', error '0.0000000000' |
19 | Correct | 1 ms | 4700 KB | found '45.0000000000', expected '45.0000000000', error '0.0000000000' |
20 | Correct | 1 ms | 4952 KB | found '66.5000000000', expected '66.5000000000', error '0.0000000000' |
21 | Correct | 1 ms | 4700 KB | found '67.0000000000', expected '67.0000000000', error '0.0000000000' |
22 | Correct | 1 ms | 4700 KB | found '66.0000000000', expected '66.0000000000', error '0.0000000000' |
23 | Correct | 1 ms | 4700 KB | found '47.0000000000', expected '47.0000000000', error '0.0000000000' |
24 | Correct | 1 ms | 4700 KB | found '50.0000000000', expected '50.0000000000', error '0.0000000000' |
25 | Correct | 1 ms | 4700 KB | found '49.0000000000', expected '49.0000000000', error '0.0000000000' |
26 | Correct | 1 ms | 4700 KB | found '57.0000000000', expected '57.0000000000', error '0.0000000000' |
27 | Correct | 1 ms | 4696 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
28 | Correct | 1 ms | 2652 KB | found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
29 | Correct | 1 ms | 4700 KB | found '1023.0000000000', expected '1023.0000000000', error '0.0000000000' |
30 | Correct | 1 ms | 4700 KB | found '294.0000000000', expected '294.0000000000', error '0.0000000000' |
31 | Correct | 1 ms | 4696 KB | found '1087.0000000000', expected '1087.0000000000', error '0.0000000000' |
32 | Correct | 1 ms | 4700 KB | found '1.5000000000', expected '1.5000000000', error '0.0000000000' |
33 | Correct | 1 ms | 4700 KB | found '703.0000000000', expected '703.0000000000', error '0.0000000000' |
34 | Correct | 1 ms | 4700 KB | found '55.5000000000', expected '55.5000000000', error '0.0000000000' |
35 | Correct | 1 ms | 4700 KB | found '56.0000000000', expected '56.0000000000', error '0.0000000000' |
36 | Correct | 1 ms | 4700 KB | found '45.0000000000', expected '45.0000000000', error '0.0000000000' |
37 | Correct | 1 ms | 4700 KB | found '66.5000000000', expected '66.5000000000', error '0.0000000000' |
38 | Correct | 1 ms | 4700 KB | found '67.0000000000', expected '67.0000000000', error '0.0000000000' |
39 | Correct | 1 ms | 4696 KB | found '66.0000000000', expected '66.0000000000', error '0.0000000000' |
40 | Correct | 1 ms | 4696 KB | found '47.0000000000', expected '47.0000000000', error '0.0000000000' |
41 | Correct | 1 ms | 4700 KB | found '50.0000000000', expected '50.0000000000', error '0.0000000000' |
42 | Correct | 1 ms | 4704 KB | found '49.0000000000', expected '49.0000000000', error '0.0000000000' |
43 | Correct | 1 ms | 4700 KB | found '57.0000000000', expected '57.0000000000', error '0.0000000000' |
44 | Correct | 1 ms | 2652 KB | found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000' |
45 | Correct | 2 ms | 2652 KB | found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000' |
46 | Correct | 84 ms | 4792 KB | found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000' |
47 | Correct | 54 ms | 5016 KB | found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000' |
48 | Correct | 54 ms | 4832 KB | found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000' |
49 | Correct | 62 ms | 4704 KB | found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000' |
50 | Correct | 71 ms | 4700 KB | found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000' |
51 | Correct | 70 ms | 4800 KB | found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000' |
52 | Correct | 67 ms | 4696 KB | found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000' |
53 | Correct | 64 ms | 4700 KB | found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000' |
54 | Correct | 74 ms | 4700 KB | found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000' |
55 | Correct | 73 ms | 4804 KB | found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000' |
56 | Correct | 1 ms | 4720 KB | found '7.5000000000', expected '7.5000000000', error '0.0000000000' |
57 | Correct | 18 ms | 4728 KB | found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
58 | Correct | 1 ms | 2648 KB | found '100800.5000000000', expected '100800.5000000000', error '0.0000000000' |
59 | Correct | 1 ms | 2676 KB | found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
60 | Correct | 1 ms | 2652 KB | found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
61 | Correct | 1 ms | 2652 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
62 | Correct | 1 ms | 2664 KB | found '124002.0000000000', expected '124002.0000000000', error '0.0000000000' |
63 | Correct | 4 ms | 3544 KB | found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000' |
64 | Correct | 4 ms | 3452 KB | found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000' |
65 | Correct | 5 ms | 3544 KB | found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000' |
66 | Correct | 5 ms | 3544 KB | found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000' |
67 | Correct | 1 ms | 4700 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
68 | Correct | 1 ms | 2652 KB | found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
69 | Correct | 1 ms | 4700 KB | found '1023.0000000000', expected '1023.0000000000', error '0.0000000000' |
70 | Correct | 1 ms | 4700 KB | found '294.0000000000', expected '294.0000000000', error '0.0000000000' |
71 | Correct | 1 ms | 4700 KB | found '1087.0000000000', expected '1087.0000000000', error '0.0000000000' |
72 | Correct | 1 ms | 4700 KB | found '1.5000000000', expected '1.5000000000', error '0.0000000000' |
73 | Correct | 1 ms | 4700 KB | found '703.0000000000', expected '703.0000000000', error '0.0000000000' |
74 | Correct | 1 ms | 4700 KB | found '55.5000000000', expected '55.5000000000', error '0.0000000000' |
75 | Correct | 1 ms | 4700 KB | found '56.0000000000', expected '56.0000000000', error '0.0000000000' |
76 | Correct | 1 ms | 4700 KB | found '45.0000000000', expected '45.0000000000', error '0.0000000000' |
77 | Correct | 1 ms | 4700 KB | found '66.5000000000', expected '66.5000000000', error '0.0000000000' |
78 | Correct | 1 ms | 4700 KB | found '67.0000000000', expected '67.0000000000', error '0.0000000000' |
79 | Correct | 1 ms | 4700 KB | found '66.0000000000', expected '66.0000000000', error '0.0000000000' |
80 | Correct | 1 ms | 4700 KB | found '47.0000000000', expected '47.0000000000', error '0.0000000000' |
81 | Correct | 1 ms | 4700 KB | found '50.0000000000', expected '50.0000000000', error '0.0000000000' |
82 | Correct | 1 ms | 4696 KB | found '49.0000000000', expected '49.0000000000', error '0.0000000000' |
83 | Correct | 1 ms | 4700 KB | found '57.0000000000', expected '57.0000000000', error '0.0000000000' |
84 | Correct | 1 ms | 2652 KB | found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000' |
85 | Correct | 1 ms | 2652 KB | found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000' |
86 | Correct | 70 ms | 4700 KB | found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000' |
87 | Correct | 54 ms | 4700 KB | found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000' |
88 | Correct | 51 ms | 4700 KB | found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000' |
89 | Correct | 65 ms | 4776 KB | found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000' |
90 | Correct | 68 ms | 4804 KB | found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000' |
91 | Correct | 69 ms | 4700 KB | found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000' |
92 | Correct | 68 ms | 4696 KB | found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000' |
93 | Correct | 64 ms | 4700 KB | found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000' |
94 | Correct | 66 ms | 4700 KB | found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000' |
95 | Correct | 87 ms | 4696 KB | found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000' |
96 | Execution timed out | 2035 ms | 21844 KB | Time limit exceeded |
97 | Halted | 0 ms | 0 KB | - |