oj.uz

Submission #862399

# Submission time Handle Problem Language Result Execution time Memory
862399 2023-10-18T07:54:00 Z Trisanu_Das Boarding Passes (BOI22_passes) C++17
100 / 100
 190 ms 177676 KB 
#include <bits/stdc++.h>
using namespace std;
 
const int maxn = 100010, n = 15;
int cnt[n], pre[maxn][n][n], suf[maxn][n][n];
string str;
long long f[1 << n];
vector<int> pos[n];
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> str;
    fill(pos, pos + n, vector<int>{-1});
    for (int i = 0; i < str.size(); i++) {
        pos[str[i] - 'A'].push_back(i);
        if (i) memcpy(pre[i], pre[i - 1], sizeof(pre[i]));
        for (int j = 0; j < n; j++) pre[i][str[i] - 'A'][j] += cnt[j];
        cnt[str[i] - 'A']++;
    }
    fill(cnt, cnt + n, 0);
    for (int i = str.size() - 1; ~i; i--) {
        memcpy(suf[i], suf[i + 1], sizeof(suf[i]));
        for (int j = 0; j < n; j++) suf[i][str[i] - 'A'][j] += cnt[j];
        cnt[str[i] - 'A']++;
    }
    fill(f + 1, f + (1 << n), 1e18);
    for (int S = 0; S < 1 << n; S++) {
        for (int i = 0; i < n; i++) if (!(S >> i & 1)) {
            auto calc = [&](int p) {
                int r = pos[i].size() - p - 1;
                long long s = (1LL * p * (p - 1) + 1LL * r * (r - 1)) / 2;
                p = pos[i][p];
                for (int j = 0; j < n; j++) if (S >> j & 1) {
                    if (~p) s += 2 * pre[p][i][j];
                    s += 2 * suf[p + 1][i][j];
                }
                return s;
            };
            int l = 1, r = pos[i].size() - 1, p = 0;
            while (l <= r) {
                int mid = (l + r) / 2;
                calc(mid) < calc(mid - 1) ? l = (p = mid) + 1 : r = mid - 1;
            }
            f[S | (1 << i)] = min(f[S | (1 << i)], f[S] + calc(p));
        }
    }
    cout << f[(1 << n) - 1] / 2 << (f[(1 << n) - 1] % 2 ? ".5" : "") << "\n";
    return 0;
}

Compilation message

passes.cpp: In function 'int main()':
passes.cpp:14:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     for (int i = 0; i < str.size(); i++) {
      |                     ~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 6748 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 16 ms 4696 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 18 ms 4700 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 18 ms 4696 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 24 ms 6748 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 58 ms 142352 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 68 ms 170212 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 70 ms 177676 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 73 ms 177420 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 4700 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 22 ms 6748 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 47 ms 7000 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 41 ms 6748 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 31 ms 6748 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 26 ms 4740 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 36 ms 4696 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 35 ms 4700 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 37 ms 4700 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 37 ms 4700 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 36 ms 4700 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 37 ms 4712 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 35 ms 4700 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 37 ms 4700 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 37 ms 4696 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 37 ms 4948 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 39 ms 4696 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 4700 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 22 ms 6748 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 47 ms 7000 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 41 ms 6748 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 31 ms 6748 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 26 ms 4740 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 36 ms 4696 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 35 ms 4700 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 37 ms 4700 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 37 ms 4700 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 36 ms 4700 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 37 ms 4712 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 35 ms 4700 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 37 ms 4700 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 37 ms 4696 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 37 ms 4948 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 39 ms 4696 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 23 ms 4696 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 24 ms 6744 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 44 ms 6744 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 41 ms 6748 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 31 ms 6748 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 25 ms 4696 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 36 ms 4700 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 35 ms 4700 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 37 ms 4696 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 39 ms 4700 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 36 ms 4700 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 37 ms 4736 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 35 ms 4700 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 37 ms 4700 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 37 ms 4744 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 36 ms 4700 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 39 ms 4696 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 28 ms 21852 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 29 ms 21848 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 88 ms 21848 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 82 ms 21852 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 41 ms 21852 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 74 ms 21860 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 83 ms 21592 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 84 ms 21592 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 85 ms 21592 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 86 ms 21728 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 103 ms 21744 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 85 ms 21596 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 6748 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 16 ms 4696 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 18 ms 4700 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 18 ms 4696 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 24 ms 6748 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 58 ms 142352 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 68 ms 170212 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 70 ms 177676 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 73 ms 177420 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 21 ms 4700 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 22 ms 6748 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 47 ms 7000 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 41 ms 6748 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 31 ms 6748 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 26 ms 4740 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 36 ms 4696 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 35 ms 4700 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 37 ms 4700 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 37 ms 4700 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 36 ms 4700 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 37 ms 4712 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 35 ms 4700 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 37 ms 4700 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 37 ms 4696 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 37 ms 4948 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 39 ms 4696 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 23 ms 4696 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 24 ms 6744 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 44 ms 6744 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 41 ms 6748 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 31 ms 6748 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 25 ms 4696 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 36 ms 4700 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 35 ms 4700 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 37 ms 4696 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 39 ms 4700 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 36 ms 4700 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 37 ms 4736 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 35 ms 4700 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 37 ms 4700 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 37 ms 4744 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 36 ms 4700 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 39 ms 4696 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 28 ms 21852 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 29 ms 21848 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 88 ms 21848 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 82 ms 21852 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 41 ms 21852 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 74 ms 21860 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 83 ms 21592 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 84 ms 21592 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 85 ms 21592 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 86 ms 21728 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 103 ms 21744 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 85 ms 21596 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 28 ms 4700 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 39 ms 4700 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 25 ms 6800 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 15 ms 4700 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 18 ms 4736 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 18 ms 4740 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 25 ms 6748 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 58 ms 142488 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 70 ms 170176 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 71 ms 177544 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 70 ms 177556 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 21 ms 4720 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 22 ms 6748 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 46 ms 6748 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 40 ms 6764 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 31 ms 6748 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 25 ms 4568 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 38 ms 4700 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 36 ms 4732 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 37 ms 4716 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 38 ms 4696 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 36 ms 4716 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 37 ms 4700 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 35 ms 4568 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 37 ms 4696 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 37 ms 4696 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 37 ms 4700 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 39 ms 4712 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 28 ms 21972 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 29 ms 21852 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 87 ms 21920 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 82 ms 21884 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 42 ms 21952 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 75 ms 21864 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 83 ms 21740 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 84 ms 21596 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 86 ms 21596 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 86 ms 21728 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 85 ms 21596 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 85 ms 21592 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 190 ms 177492 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 48 ms 4696 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 175 ms 177456 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 86 ms 177672 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 33 ms 4696 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 174 ms 177448 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 174 ms 177492 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 180 ms 177232 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 175 ms 177292 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 174 ms 177236 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 177 ms 177284 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 175 ms 177284 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 170 ms 177160 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 175 ms 177316 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'