oj.uz

Submission #852523

# Submission time Handle Problem Language Result Execution time Memory
852523 2023-09-22T00:38:12 Z MinaRagy06 Boarding Passes (BOI22_passes) C++17
60 / 100
 2000 ms 19268 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("trapv")
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();
            }
        }
    }
//    for (int i = 0; i < m; i++) {
//        for (int j = 0; j < m; j++) {
//            for (int k = 0; k <= (int) idx[j].size(); k++) {
//                cout << "if we include the first " << k << " in " << j << " passes by " << i << ": " << val[i][j][k] << " times\n";
//            }
//        }
//    }
    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]) {
            double mn = 1e10;
            for (int s = 0; s <= (int) idx[i].size(); 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;
                mn = min(mn, cur);
            }
            dp[msk] = min(dp[msk], mn + dp[msk | (1 << i)]);
        }
    }
    cout << dp[0] << '\n';
    /*
    for (int j = 0; j <= n; j++) {
        ans = min(ans, 1.0 * j * (j - 1) / 4.0 + 1.0 * (n - j) * (n - j - 1) / 4.0);
    }
    */
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 344 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 6 ms 2580 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 7 ms 2836 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 7 ms 3300 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 8 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 600 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 348 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 1 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 344 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 1 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 344 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 0 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 344 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 600 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 348 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 1 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 344 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 1 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 344 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 0 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 344 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 0 ms 344 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 1 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 1 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 1 ms 344 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 1 ms 344 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 1 ms 548 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 0 ms 344 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 348 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 348 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 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 1 ms 600 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 219 ms 1624 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 216 ms 1872 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 213 ms 1624 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 213 ms 1624 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 209 ms 1624 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 211 ms 1624 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 211 ms 1784 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 209 ms 1784 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 208 ms 1624 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 213 ms 1624 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 344 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 344 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 6 ms 2580 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 7 ms 2836 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 7 ms 3300 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 8 ms 3092 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 0 ms 600 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 348 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 1 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 344 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 1 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 344 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 0 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 1 ms 344 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 0 ms 344 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 1 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 1 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 1 ms 344 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 1 ms 344 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 1 ms 548 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 0 ms 344 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 348 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 348 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 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 1 ms 600 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 219 ms 1624 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 216 ms 1872 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 213 ms 1624 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 213 ms 1624 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 209 ms 1624 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 211 ms 1624 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 211 ms 1784 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 209 ms 1784 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 208 ms 1624 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 213 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 57 ms 600 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 0 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 0 ms 344 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 0 ms 344 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 6 ms 2580 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 7 ms 2840 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 7 ms 3092 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 7 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 1 ms 344 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 1 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 1 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 1 ms 344 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 1 ms 348 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 1 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 1 ms 344 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 0 ms 344 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 1 ms 548 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 1 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 348 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 600 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 1 ms 600 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 216 ms 1816 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 215 ms 1772 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 219 ms 1628 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 213 ms 1624 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 220 ms 1784 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 210 ms 1808 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 209 ms 1788 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 209 ms 1780 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 213 ms 1780 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 212 ms 1808 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Execution timed out 2045 ms 19268 KB Time limit exceeded
97 Halted 0 ms 0 KB -