oj.uz

Submission #1079046

# Submission time Handle Problem Language Result Execution time Memory
1079046 2024-08-28T09:56:43 Z hcng Boarding Passes (BOI22_passes) C++14
100 / 100
 567 ms 365908 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define INF 0x3f3f3f3f3f3f3f3f

const int G = 15;
int n;
string s;
int psum[100010][G];
int pisum[100010][G][G], sisum[100010][G][G];
int dp[1 << G];
vector<int> pos[G];

int calc(int M, int p, int c) {
    int x = psum[M][c], y = psum[n][c];
    int r = x * (x - 1) / 2 + (y - x) * (y - x - 1) / 2;
    for (int i = 0; i < G; i++) {
        if (i == c) continue;
        if ((p >> i) & 1) {
            r += 2 * pisum[M][i][c];
            r += 2 * sisum[M + 1][c][i];
        }
    }
    return r;
}

bool calc2(int M, int p, int c) {
    int x = psum[M][c], y = psum[n][c];
    int r1 = x * (x - 1) / 2;
    int r2 = (y - x) * (y - x - 1) / 2;
    for (int i = 0; i < G; i++) {
        if (i == c) continue;
        if ((p >> i) & 1) {
            r1 += 2 * pisum[M][i][c];
            r2 += 2 * sisum[M + 1][c][i];
        }
    }
    return r1 < r2;
}


int tsearch(int p, int c) {
    int L = 0, R = pos[c].size() - 1;
    int mn = INF;
    while (L + 5 < R) {
        int M1 = L + (R - L) / 3, M2 = R - (R - L) / 3;
        int C1 = calc(pos[c][M1] - 1, p, c);
        int C2 = calc(pos[c][M2] - 1, p, c);
        if (C1 > C2) L = M1;
        else R = M2;
    }
    for (int i = L; i <= R; i++) {
        mn = min(mn, calc(pos[c][i] - 1, p, c));
    }
    return mn;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    cin >> s;
    n = s.size();
    s = ' ' + s;
    
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < G; j++) {
            psum[i][j] = psum[i - 1][j];
        }
        psum[i][s[i] - 'A']++;
        pos[s[i] - 'A'].push_back(i);
    }
    for (int i = 0; i < G; i++) {
        pos[i].push_back(n + 1);
    }
    
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < G; j++) {
            for (int k = 0; k < G; k++) {
                pisum[i][j][k] = pisum[i - 1][j][k];
            }
        }
        for (int j = 0; j < G; j++) {
            if (s[i] - 'A' == j) continue;
            pisum[i][j][s[i] - 'A'] += psum[i - 1][j];
        }
    }
    
    for (int i = n; i >= 1; i--) {
        for (int j = 0; j < G; j++) {
            for (int k = 0; k < G; k++) {
                sisum[i][j][k] = sisum[i + 1][j][k];
            }
        }
        for (int j = 0; j < G; j++) {
            if (s[i] - 'A' == j) continue;
            sisum[i][s[i] - 'A'][j] += psum[n][j] - psum[i][j];
        }
    }
    
    memset(dp, 0x3f, sizeof(dp));
    dp[0] = 0;
    for (int i = 1; i < (1 << G); i++) {
        for (int j = 0; j < G; j++) {
            if (!((i >> j) & 1)) continue;
            int p = i ^ (1 << j);
            dp[i] = min(dp[i], dp[p] + tsearch(p, j));
        }
    }
    
    printf("%.1lf\n", dp[(1 << G) - 1] / (double)2);
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 4520 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 14 ms 604 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 15 ms 748 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 20 ms 604 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 28 ms 4696 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 159 ms 287684 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 184 ms 343228 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 206 ms 365752 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 182 ms 365760 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 604 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 26 ms 860 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 60 ms 1112 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 81 ms 1084 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 29 ms 860 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 22 ms 604 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 56 ms 860 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 34 ms 604 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 33 ms 600 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 41 ms 604 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 33 ms 604 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 34 ms 604 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 31 ms 724 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 33 ms 600 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 34 ms 848 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 32 ms 604 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 32 ms 604 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 604 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 26 ms 860 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 60 ms 1112 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 81 ms 1084 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 29 ms 860 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 22 ms 604 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 56 ms 860 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 34 ms 604 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 33 ms 600 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 41 ms 604 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 33 ms 604 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 34 ms 604 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 31 ms 724 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 33 ms 600 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 34 ms 848 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 32 ms 604 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 32 ms 604 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 21 ms 768 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 29 ms 860 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 65 ms 1092 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 58 ms 860 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 28 ms 860 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 21 ms 780 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 64 ms 860 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 31 ms 604 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 35 ms 720 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 32 ms 860 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 31 ms 604 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 33 ms 604 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 43 ms 600 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 31 ms 604 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 31 ms 600 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 33 ms 824 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 34 ms 604 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 49 ms 38812 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 47 ms 38744 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 180 ms 38748 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 187 ms 38688 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 52 ms 38744 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 199 ms 38564 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 186 ms 38028 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 185 ms 37976 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 189 ms 37976 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 192 ms 37996 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 195 ms 38016 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 194 ms 38008 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 4520 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 14 ms 604 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 15 ms 748 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 20 ms 604 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 28 ms 4696 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 159 ms 287684 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 184 ms 343228 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 206 ms 365752 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 182 ms 365760 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 18 ms 604 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 26 ms 860 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 60 ms 1112 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 81 ms 1084 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 29 ms 860 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 22 ms 604 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 56 ms 860 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 34 ms 604 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 33 ms 600 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 41 ms 604 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 33 ms 604 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 34 ms 604 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 31 ms 724 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 33 ms 600 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 34 ms 848 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 32 ms 604 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 32 ms 604 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 21 ms 768 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 29 ms 860 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 65 ms 1092 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 58 ms 860 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 28 ms 860 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 21 ms 780 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 64 ms 860 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 31 ms 604 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 35 ms 720 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 32 ms 860 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 31 ms 604 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 33 ms 604 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 43 ms 600 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 31 ms 604 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 31 ms 600 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 33 ms 824 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 34 ms 604 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 49 ms 38812 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 47 ms 38744 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 180 ms 38748 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 187 ms 38688 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 52 ms 38744 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 199 ms 38564 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 186 ms 38028 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 185 ms 37976 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 189 ms 37976 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 192 ms 37996 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 195 ms 38016 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 194 ms 38008 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 26 ms 604 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 39 ms 604 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 32 ms 4700 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 15 ms 600 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 17 ms 752 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 17 ms 604 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 29 ms 4696 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 166 ms 287688 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 190 ms 343232 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 210 ms 365752 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 197 ms 365756 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 18 ms 604 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 24 ms 1116 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 63 ms 860 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 58 ms 856 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 28 ms 1116 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 21 ms 600 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 57 ms 860 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 30 ms 604 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 31 ms 600 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 31 ms 604 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 37 ms 600 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 39 ms 604 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 31 ms 600 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 31 ms 604 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 31 ms 600 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 30 ms 604 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 31 ms 604 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 50 ms 38744 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 48 ms 38748 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 189 ms 38748 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 193 ms 38488 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 53 ms 38744 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 176 ms 38488 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 185 ms 37884 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 174 ms 37976 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 181 ms 37996 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 186 ms 37980 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 178 ms 38012 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 177 ms 37980 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 523 ms 365904 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 41 ms 856 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 567 ms 365716 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 214 ms 365740 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 33 ms 800 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 534 ms 365784 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 523 ms 365908 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 502 ms 364640 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 508 ms 364620 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 525 ms 364624 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 524 ms 364532 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 522 ms 364600 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 487 ms 364108 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 515 ms 364704 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'