oj.uz

Submission #852517

# Submission time Handle Problem Language Result Execution time Memory
852517 2023-09-22T00:32:35 Z MinaRagy06 Boarding Passes (BOI22_passes) C++17
55 / 100
 28 ms 2324 KB 
#include <bits/stdc++.h>
using namespace std;
typedef int64_t ll;

vector<int> 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];
                }
                int ttl = idx[i].size();
                cur += s * (s - 1) / 4.0 + (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
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 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 0 ms 344 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 352 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Incorrect 3 ms 2324 KB 1st numbers differ - expected: '772893586.0000000000', found: '-276172925.5000000000', error = '1.3573233502'
7 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 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 0 ms 344 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 600 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 0 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 348 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 0 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 1 ms 344 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 468 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 344 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 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 0 ms 344 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 600 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 0 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 348 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 0 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 1 ms 344 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 468 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 ms 344 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 1 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 0 ms 464 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 1 ms 448 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 0 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 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 0 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 0 ms 348 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 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 604 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 26 ms 1372 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 26 ms 1368 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 26 ms 1368 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 26 ms 1428 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 28 ms 1616 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 26 ms 1368 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 28 ms 1372 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 26 ms 1248 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 27 ms 1472 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 28 ms 1368 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 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 0 ms 344 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 352 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Incorrect 3 ms 2324 KB 1st numbers differ - expected: '772893586.0000000000', found: '-276172925.5000000000', error = '1.3573233502'
7 Halted 0 ms 0 KB -