oj.uz

Submission #859035

# Submission time Handle Problem Language Result Execution time Memory
859035 2023-10-09T14:51:20 Z vgtcross Boarding Passes (BOI22_passes) C++17
100 / 100
 301 ms 365928 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 100100;
const int K = 15;

ll p[N][K];
ll q[N][K][K];
ll s[N][K][K];
ll dp[1 << K];
vector<int> pos[K];

void solve() {
    string str;
    cin >> str;
    
    int n = str.size();
    
    vector<int> v(n);
    for (int i = 0; i < n; ++i) {
        v[i] = str[i] - 'A';
        pos[v[i]].push_back(i);
    }
    for (int k = 0; k < K; ++k) pos[k].push_back(n);
    
    for (int i = 0; i < n; ++i) {
        for (int k = 0; k < K; ++k) p[i+1][k] = p[i][k] + (v[i] == k);
        for (int k = 0; k < K; ++k) {
            for (int l = 0; l < K; ++l) q[i+1][k][l] = q[i][k][l] + (v[i] == k) * p[i+1][l];
        }
    }
    for (int i = n-1; i >= 0; --i) {
        for (int k = 0; k < K; ++k) {
            for (int l = 0; l < K; ++l) s[i][k][l] = s[i+1][k][l] + (v[i] == k) * (p[n][l] - p[i][l]);
        }
    }
    
    memset(dp, 0x3f, sizeof dp);
    dp[0] = 0;
    for (int j = 1; j < (1 << K); ++j) {
        for (int i = 0; i < K; ++i) if (j >> i & 1) {
            int a = -1, d = pos[i].size();
            ll ans = 1e18;
            while (d-a > 2) {
                int b = a + (d-a)/3;
                int c = a + 2*(d-a)/3;
                int x = pos[i][b];
                int y = pos[i][c];
                ll ansb = p[x][i]*(p[x][i]-1)/2 + (p[n][i]-p[x][i])*(p[n][i]-p[x][i]-1)/2;
                ll ansc = p[y][i]*(p[y][i]-1)/2 + (p[n][i]-p[y][i])*(p[n][i]-p[y][i]-1)/2;
                for (int k = 0; k < K; ++k) if (i != k && (j >> k & 1)) {
                    ansb += 2*q[x][i][k] + 2*s[x][i][k];
                    ansc += 2*q[y][i][k] + 2*s[y][i][k];
                }
                if (ansb < ansc) {
                    ans = min(ans, ansb);
                    d = c;
                } else {
                    ans = min(ans, ansc);
                    a = b;
                }
            }
            dp[j] = min(dp[j], dp[j ^ (1 << i)] + (p[n][i] > 0) * ans);
        }
    }
    
    cout << (long double) dp[(1 << K) - 1] / 2.0 << '\n';
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    
    cout << fixed << setprecision(6);
    
    solve();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 4440 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 4 ms 856 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 5 ms 724 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 5 ms 752 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 19 ms 4760 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 75 ms 290316 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 83 ms 344300 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 90 ms 365896 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 89 ms 365872 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 604 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 13 ms 3068 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 35 ms 2904 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 33 ms 2908 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 16 ms 2908 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 11 ms 604 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 31 ms 3012 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 19 ms 600 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 20 ms 600 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 19 ms 840 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 20 ms 852 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 19 ms 604 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 20 ms 840 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 21 ms 604 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 20 ms 600 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 19 ms 604 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 20 ms 844 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 604 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 13 ms 3068 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 35 ms 2904 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 33 ms 2908 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 16 ms 2908 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 11 ms 604 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 31 ms 3012 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 19 ms 600 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 20 ms 600 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 19 ms 840 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 20 ms 852 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 19 ms 604 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 20 ms 840 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 21 ms 604 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 20 ms 600 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 19 ms 604 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 20 ms 844 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 7 ms 604 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 11 ms 3068 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 35 ms 2908 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 35 ms 3028 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 18 ms 2904 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 10 ms 600 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 29 ms 2904 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 19 ms 600 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 20 ms 856 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 19 ms 836 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 24 ms 860 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 20 ms 600 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 20 ms 604 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 21 ms 604 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 20 ms 604 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 19 ms 600 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 20 ms 856 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 28 ms 39260 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 24 ms 39260 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 119 ms 39508 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 96 ms 39304 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 32 ms 39356 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 113 ms 39256 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 115 ms 38972 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 115 ms 38964 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 114 ms 39000 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 120 ms 38748 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 116 ms 38972 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 119 ms 38964 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 4440 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 4 ms 856 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 5 ms 724 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 5 ms 752 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 19 ms 4760 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 75 ms 290316 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 83 ms 344300 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 90 ms 365896 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 89 ms 365872 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 7 ms 604 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 13 ms 3068 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 35 ms 2904 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 33 ms 2908 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 16 ms 2908 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 11 ms 604 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 31 ms 3012 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 19 ms 600 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 20 ms 600 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 19 ms 840 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 20 ms 852 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 19 ms 604 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 20 ms 840 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 21 ms 604 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 20 ms 600 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 19 ms 604 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 20 ms 844 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 7 ms 604 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 11 ms 3068 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 35 ms 2908 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 35 ms 3028 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 18 ms 2904 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 10 ms 600 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 29 ms 2904 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 19 ms 600 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 20 ms 856 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 19 ms 836 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 24 ms 860 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 20 ms 600 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 20 ms 604 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 21 ms 604 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 20 ms 604 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 19 ms 600 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 20 ms 856 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 28 ms 39260 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 24 ms 39260 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 119 ms 39508 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 96 ms 39304 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 32 ms 39356 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 113 ms 39256 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 115 ms 38972 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 115 ms 38964 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 114 ms 39000 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 120 ms 38748 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 116 ms 38972 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 119 ms 38964 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 12 ms 600 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 33 ms 604 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 15 ms 4444 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 4 ms 604 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 5 ms 604 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 5 ms 604 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 16 ms 4700 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 77 ms 290168 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 82 ms 344332 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 94 ms 365796 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 91 ms 365828 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 7 ms 604 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 11 ms 2908 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 35 ms 3028 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 35 ms 2908 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 16 ms 2908 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 10 ms 604 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 29 ms 2908 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 19 ms 600 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 20 ms 604 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 18 ms 604 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 19 ms 600 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 19 ms 604 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 19 ms 840 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 24 ms 852 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 19 ms 604 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 19 ms 604 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 20 ms 840 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 25 ms 39216 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 25 ms 39260 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 117 ms 39332 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 100 ms 39300 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 32 ms 39256 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 113 ms 39260 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 121 ms 38744 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 117 ms 38964 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 117 ms 38972 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 149 ms 38956 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 115 ms 38748 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 124 ms 38968 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 301 ms 365708 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 34 ms 720 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 242 ms 365616 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 105 ms 365928 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 22 ms 812 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 264 ms 365676 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 281 ms 365724 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 287 ms 364368 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 259 ms 364312 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 281 ms 364372 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 260 ms 364372 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 265 ms 364372 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 269 ms 363864 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 259 ms 364356 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'