oj.uz

Submission #725407

# Submission time Handle Problem Language Result Execution time Memory
725407 2023-04-17T11:25:50 Z dxz05 Boarding Passes (BOI22_passes) C++17
60 / 100
 2000 ms 23180 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;

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

            long long mn = 5e18;
            for (int half = 0; half <= sz; half++){
                ll cur = 0;
                for (int d = 0; d < G; d++){
                    if (!(mask & (1 << d))) continue;

                    if (half > 0) cur += pref[c][d][half - 1];
                    if (half < sz) cur += suff[c][d][half];
                }
                cur *= 4;

                cur += exp_inv(half) + exp_inv(sz - half);

                mn = min(mn, cur);
            }

            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 336 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 212 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 1184 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 2 ms 1188 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 2 ms 1300 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 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 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 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 336 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 340 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 344 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 0 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 336 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 340 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 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 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 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 336 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 340 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 344 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 0 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 336 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 340 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 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 336 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 348 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 480 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 1 ms 476 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 65 ms 1848 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 60 ms 1748 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 63 ms 1996 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 64 ms 1748 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 77 ms 1828 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 66 ms 1800 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 64 ms 1748 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 75 ms 1748 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 67 ms 1816 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 64 ms 1748 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
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 336 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 212 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 1184 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 2 ms 1188 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 2 ms 1300 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 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 1 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 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 1 ms 336 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 1 ms 340 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 1 ms 344 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 0 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 336 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 340 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 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 336 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 348 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 480 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 1 ms 476 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 65 ms 1848 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 60 ms 1748 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 63 ms 1996 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 64 ms 1748 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 77 ms 1828 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 66 ms 1800 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 64 ms 1748 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 75 ms 1748 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 67 ms 1816 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 64 ms 1748 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 1 ms 348 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 34 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 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 1 ms 344 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 1 ms 468 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 3 ms 1200 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 2 ms 1308 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 3 ms 1300 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 3 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 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 1 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 1 ms 340 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 1 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 1 ms 336 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 340 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 1 ms 336 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 68 ms 1844 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 65 ms 1812 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 64 ms 1880 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 70 ms 1816 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 63 ms 1816 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 61 ms 1752 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 63 ms 1748 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 63 ms 1804 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 62 ms 1748 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 65 ms 1808 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Execution timed out 2051 ms 23180 KB Time limit exceeded
97 Halted 0 ms 0 KB -