oj.uz

Submission #853274

# Submission time Handle Problem Language Result Execution time Memory
853274 2023-09-23T20:48:57 Z MinaRagy06 Boarding Passes (BOI22_passes) C++17
100 / 100
 168 ms 19816 KB 
#include <bits/stdc++.h>
using namespace std;
typedef int64_t ll;

vector<ll> val[16][16];
vector<int> idx[16];
int prfx[16][100'005];
double dp[1 << 16];
int sum(int g, int l, int r) {
    return prfx[g][r + 1] - prfx[g][l];
}
int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cout << fixed << setprecision(3);
    string in;
    cin >> in;
    int n = in.size();
    set<int> chars;
    for (auto i : in) {
        chars.insert(i);
    }
    int mp[255]{}, ctr = 0;
    for (auto i : chars) {
        mp[i] = ctr++;
    }
    int m = chars.size();
    int a[n];
    for (int i = 0; i < n; i++) {
        a[i] = mp[(int)in[i]];
    }
    for (int i = 0; i < n; i++) {
        idx[a[i]].push_back(i);
        for (int j = 0; j < m; j++) {
            prfx[j][i + 1] = prfx[j][i];
        }
        prfx[a[i]][i + 1]++;
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < m; j++) {
            vector<int> cur = idx[j];
            val[i][j].resize(cur.size() + 1);
            reverse(cur.begin(), cur.end());
            val[i][j][0] = 0;
            for (auto l : cur) {
                val[i][j][0] += sum(i, l, n - 1);
            }
            for (int k = 1; k <= (int) idx[j].size(); k++) {
                val[i][j][k] = val[i][j][k - 1];
                val[i][j][k] -= sum(i, cur.back(), n - 1);
                val[i][j][k] += sum(i, 0, cur.back());
                cur.pop_back();
            }
        }
    }
    dp[(1 << m) - 1] = 0;
    for (int msk = (1 << m) - 2; msk >= 0; msk--) {
        vector<int> bits[2];
        for (int i = 0; i < m; i++) {
            bits[(msk >> i) & 1].push_back(i);
        }
        dp[msk] = 1e10;
        for (auto i : bits[0]) {
            auto calc = [&] (int s) {
                double cur = 0;
                for (auto j : bits[1]) {
                    cur += val[j][i][s];
                }
                ll ttl = idx[i].size();
                cur += 1ll * s * (s - 1) / 4.0 + 1ll * (ttl - s) * (ttl - s - 1) / 4.0;
                return cur;
            };
            double mn = 1e10;
            int l = 0, r = idx[i].size();
            while (r - l > 3) {
                int md1 = l + (r - l) / 3, md2 = r - (r - l) / 3;
                if (calc(md1) <= calc(md2)) {
                    r = md2;
                } else {
                    l = md1;
                }
            }
            for (int s = l; s <= r; s++) {
                mn = min(mn, calc(s));
            }
            dp[msk] = min(dp[msk], mn + dp[msk | (1 << i)]);
        }
    }
    cout << dp[0] << '\n';
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 344 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 344 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 344 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 2 ms 2584 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 3 ms 3092 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 5 ms 3092 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 3 ms 3092 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 344 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 344 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 344 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 344 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 344 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 0 ms 344 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 344 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 344 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 0 ms 344 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 344 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 344 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 344 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 0 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 344 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 344 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 344 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 344 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 344 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 0 ms 344 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 344 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 344 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 0 ms 344 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 344 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 344 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 344 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 0 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 0 ms 344 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 1 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 1 ms 344 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 0 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 2 ms 344 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 0 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 1 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 1 ms 344 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 1 ms 600 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 1 ms 344 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 344 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 1 ms 344 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 1 ms 344 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 1 ms 344 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 1 ms 344 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 1 ms 344 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 1 ms 344 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 1 ms 732 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 1 ms 600 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 4 ms 1624 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 4 ms 1624 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 2 ms 1624 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 4 ms 1628 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 3 ms 1624 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 4 ms 1624 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 4 ms 1624 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 4 ms 1624 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 4 ms 1624 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 3 ms 1624 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 600 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 344 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 344 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 344 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 2 ms 2584 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 3 ms 3092 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 5 ms 3092 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 3 ms 3092 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 0 ms 344 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 1 ms 344 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 1 ms 344 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 1 ms 344 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 1 ms 344 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 344 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 0 ms 344 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 1 ms 344 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 1 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 1 ms 344 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 0 ms 344 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 1 ms 344 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 1 ms 344 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 1 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 1 ms 344 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 0 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 0 ms 344 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 1 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 1 ms 344 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 0 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 2 ms 344 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 0 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 1 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 1 ms 344 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 1 ms 600 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 1 ms 344 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 1 ms 344 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 1 ms 344 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 1 ms 344 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 1 ms 344 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 1 ms 344 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 1 ms 344 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 1 ms 344 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 1 ms 732 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 1 ms 600 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 4 ms 1624 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 4 ms 1624 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 2 ms 1624 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 4 ms 1628 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 3 ms 1624 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 4 ms 1624 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 4 ms 1624 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 4 ms 1624 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 4 ms 1624 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 3 ms 1624 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 1 ms 344 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 18 ms 600 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 1 ms 344 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 0 ms 344 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 0 ms 344 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 1 ms 344 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 1 ms 344 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 2 ms 2580 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 4 ms 3092 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 3 ms 3092 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 3 ms 3092 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 0 ms 344 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 0 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 1 ms 344 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 0 ms 344 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 1 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 0 ms 344 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 1 ms 344 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 0 ms 344 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 1 ms 344 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 0 ms 344 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 1 ms 344 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 0 ms 344 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 0 ms 344 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 1 ms 344 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 0 ms 344 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 1 ms 344 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 1 ms 344 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 1 ms 604 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 1 ms 604 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 4 ms 1624 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 5 ms 1624 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 2 ms 1624 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 3 ms 1624 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 4 ms 1628 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 4 ms 1624 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 3 ms 1624 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 3 ms 1624 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 3 ms 1624 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 3 ms 1624 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 163 ms 19632 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 10 ms 600 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 152 ms 19280 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 42 ms 19816 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 15 ms 600 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 145 ms 19280 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 146 ms 19536 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 168 ms 19536 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 153 ms 19536 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 158 ms 19536 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 167 ms 19296 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 167 ms 19452 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 76 ms 18168 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 151 ms 19464 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'