oj.uz

Submission #852519

# Submission time Handle Problem Language Result Execution time Memory
852519 2023-09-22T00:35:13 Z MinaRagy06 Boarding Passes (BOI22_passes) C++17
55 / 100
 227 ms 4376 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("trapv")
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];
                }
                ll 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 0 ms 344 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 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 0 ms 344 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Runtime error 6 ms 4376 KB Execution killed with signal 6
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 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 348 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 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 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 0 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 0 ms 344 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 1 ms 344 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 348 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 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 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 0 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 0 ms 344 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 1 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 1 ms 344 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 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 0 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 1 ms 344 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 1 ms 348 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 0 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 344 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 0 ms 344 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 0 ms 344 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 223 ms 1440 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 219 ms 1388 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 221 ms 1616 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 227 ms 1368 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 215 ms 1368 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 215 ms 1368 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 216 ms 1420 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 211 ms 1368 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 216 ms 1616 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 216 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 0 ms 344 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 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 0 ms 344 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Runtime error 6 ms 4376 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -