oj.uz

Submission #725413

# Submission time Handle Problem Language Result Execution time Memory
725413 2023-04-17T11:33:34 Z dxz05 Boarding Passes (BOI22_passes) C++17
100 / 100
 391 ms 23416 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define all(x) (x).begin(), (x).end()
#define MP make_pair
const int N = 100500;

long long exp_inv(ll n){
    return (long long) n * (n - 1); // should be divided by 4
}

ll dp[1 << 15];
vector<ll> pref[16][16];
vector<ll> suff[16][16];

void solve(){
    string str;
    cin >> str;
    int n = (int)str.size();

    vector<vector<int>> pos;
    map<char, int> id;

    for (int i = 0; i < n; i++){
        if (id.find(str[i]) == id.end()){
            id[str[i]] = (int) id.size();
            pos.emplace_back();
        }
        pos[id[str[i]]].push_back(i);
    }

    int G = (int) pos.size();

    for (int x = 0; x < G; x++){
        int sz_x = (int) pos[x].size();

        for (int y = 0; y < G; y++){
            if (x == y) continue;
            int sz_y = (int) pos[y].size();

            vector<ll> &p = pref[x][y], &s = suff[x][y];

            p.resize(sz_x);
            s.resize(sz_x);

            int j = 0;
            for (int i = 0; i < sz_x; i++){
                while (j < sz_y && pos[y][j] <= pos[x][i]) j++;
                p[i] = j;
            }

            j = sz_y - 1;
            for (int i = sz_x - 1; i >= 0; i--){
                while (j >= 0 && pos[y][j] >= pos[x][i]) j--;
                s[i] = sz_y - j - 1;
            }

            for (int i = 1; i < sz_x; i++) p[i] += p[i - 1];
            for (int i = sz_x - 2; i >= 0; i--) s[i] += s[i + 1];

        }
    }

    function<long long(int, int, int)> cost = [&](int mask, int c, int wall){
        int sz = (int) pos[c].size();

        long long res = 0;
        for (int d = 0; d < G; d++){
            if (!(mask & (1 << d))) continue;

            if (wall > 0) res += pref[c][d][wall - 1];
            if (wall < sz) res += suff[c][d][wall];
        }

        res *= 4;
        res += exp_inv(wall) + exp_inv(sz - wall);

        return res;
    };

    fill(dp, dp + (1 << G), 5e18);

    dp[0] = 0;

    for (int mask = 0; mask < (1 << G); mask++){
        if (dp[mask] >= 1e18) continue;

        for (int c = 0; c < G; c++){
            if (mask & (1 << c)) continue;

            int sz = (int) pos[c].size();

            long long mn = 5e18;

            int l = 0, r = sz;
            while (r - l >= 3){
                int m1 = (2 * l + r) / 3, m2 = (l + 2 * r) / 3;
                ll f1 = cost(mask, c, m1), f2 = cost(mask, c, m2);

                mn = min({mn, f1, f2});
                if (f1 < f2){
                    r = m2;
                } else {
                    l = m1;
                }
            }

            for (int i = l; i <= r; i++) mn = min(mn, cost(mask, c, i));

            int new_mask = mask | (1 << c);
            dp[new_mask] = min(dp[new_mask], dp[mask] + mn);
        }

    }

    cout << dp[(1 << G) - 1] / 4;

    if (dp[(1 << G) - 1] % 4 != 0) cout << ".5";

    cout << endl;

}

int main() {
    ios_base::sync_with_stdio(false);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    solve();

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 340 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 340 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 340 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 2 ms 1172 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 2 ms 1300 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 2 ms 1308 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 2 ms 1300 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 340 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 344 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 384 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 340 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 340 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 340 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 340 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 340 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 340 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 340 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 340 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 340 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 336 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 340 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 344 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 384 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 340 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 340 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 340 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 340 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 340 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 340 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 340 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 340 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 340 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 336 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 1 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 1 ms 340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 1 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 1 ms 340 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 1 ms 340 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 1 ms 340 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 1 ms 340 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 1 ms 340 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 1 ms 340 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 340 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 1 ms 340 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 1 ms 340 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 1 ms 340 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 1 ms 340 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 1 ms 340 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 1 ms 340 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 1 ms 468 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 1 ms 468 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 7 ms 1872 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 5 ms 1748 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 5 ms 1876 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 6 ms 1748 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 6 ms 1836 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 5 ms 1752 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 7 ms 1748 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 6 ms 1752 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 6 ms 1748 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 6 ms 1748 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 340 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 340 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 340 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 2 ms 1172 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 2 ms 1300 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 2 ms 1308 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 2 ms 1300 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 1 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 1 ms 340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 1 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 1 ms 340 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 1 ms 344 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 1 ms 384 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 1 ms 340 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 1 ms 340 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 1 ms 340 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 1 ms 340 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 1 ms 340 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 1 ms 340 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 1 ms 340 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 1 ms 340 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 1 ms 340 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 1 ms 336 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 1 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 1 ms 340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 1 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 1 ms 340 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 1 ms 340 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 1 ms 340 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 1 ms 340 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 1 ms 340 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 1 ms 340 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 1 ms 340 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 1 ms 340 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 1 ms 340 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 1 ms 340 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 1 ms 340 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 1 ms 340 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 1 ms 340 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 1 ms 468 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 1 ms 468 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 7 ms 1872 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 5 ms 1748 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 5 ms 1876 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 6 ms 1748 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 6 ms 1836 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 5 ms 1752 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 7 ms 1748 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 6 ms 1752 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 6 ms 1748 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 6 ms 1748 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 1 ms 340 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 32 ms 596 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 1 ms 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 1 ms 340 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 1 ms 340 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 1 ms 336 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 2 ms 1172 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 2 ms 1300 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 2 ms 1300 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 2 ms 1300 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 1 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 1 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 1 ms 468 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 1 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 1 ms 340 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 1 ms 340 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 1 ms 340 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 1 ms 340 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 1 ms 340 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 1 ms 340 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 1 ms 340 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 1 ms 340 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 1 ms 340 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 1 ms 340 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 1 ms 340 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 1 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 1 ms 340 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 1 ms 468 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 1 ms 468 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 7 ms 1748 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 5 ms 1748 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 4 ms 1876 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 6 ms 1748 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 6 ms 1748 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 6 ms 1748 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 6 ms 1748 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 5 ms 1748 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 6 ms 1748 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 5 ms 1748 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 391 ms 23160 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 26 ms 468 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 332 ms 23308 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 84 ms 23416 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 28 ms 596 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 279 ms 23256 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 318 ms 23268 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 282 ms 23096 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 344 ms 23200 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 324 ms 23220 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 297 ms 23180 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 286 ms 23172 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 184 ms 21324 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 284 ms 23244 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'