oj.uz

Submission #725430

# Submission time Handle Problem Language Result Execution time Memory
725430 2023-04-17T12:02:50 Z dxz05 Boarding Passes (BOI22_passes) C++17
100 / 100
 266 ms 23312 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];

        }
    }

    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;

            function<long long(int)> cost = [&](int wall){
                int sz = (int) pos[c].size();
                if (wall > sz) return (ll)1e9;

                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;
            };

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

            int l = 0, r = sz;
            while (l <= r){
                int m = (l + r) >> 1;
                if (cost(m) > cost(m + 1)){
                    l = m + 1;
                } else {
                    r = m - 1;
                }
            }

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

    }

    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 0 ms 340 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 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 1172 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 2 ms 1172 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 2 ms 1172 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 0 ms 212 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 456 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 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 340 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 212 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 212 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 212 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 212 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 0 ms 212 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 456 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 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 340 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 212 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 212 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 212 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 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 1 ms 212 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 212 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 212 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 212 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 288 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 0 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 340 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 8 ms 1748 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 3 ms 1876 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 5 ms 1820 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 4 ms 1748 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 5 ms 1748 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 5 ms 1748 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 6 ms 1748 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 5 ms 1876 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 5 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 0 ms 340 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 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 1172 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 2 ms 1172 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 2 ms 1172 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 0 ms 212 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 456 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 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 1 ms 340 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 212 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 212 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 212 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 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 1 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 1 ms 212 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 212 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 212 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 212 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 288 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 0 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 340 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 8 ms 1748 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 3 ms 1876 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 5 ms 1820 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 4 ms 1748 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 5 ms 1748 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 5 ms 1748 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 6 ms 1748 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 5 ms 1876 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 5 ms 1748 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 0 ms 212 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 52 ms 596 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 0 ms 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 1 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 1 ms 340 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 1172 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 2 ms 1172 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 2 ms 1172 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 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 0 ms 340 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 0 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 0 ms 340 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 1 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 1 ms 212 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 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 0 ms 340 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 340 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 1 ms 340 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 3 ms 1876 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 4 ms 1748 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 5 ms 1748 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 4 ms 1748 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 4 ms 1748 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 6 ms 1812 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 5 ms 1816 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 232 ms 23184 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 33 ms 468 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 208 ms 23132 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 85 ms 23312 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 43 ms 596 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 176 ms 23156 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 189 ms 23168 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 266 ms 23116 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 196 ms 23088 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 196 ms 23120 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 207 ms 22964 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 187 ms 23124 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 96 ms 21264 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 189 ms 23120 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'