oj.uz

Submission #953660

# Submission time Handle Problem Language Result Execution time Memory
953660 2024-03-26T12:04:41 Z ifateen Boarding Passes (BOI22_passes) C++17
100 / 100
 265 ms 100292 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e5 + 5, MAXG = 15;
map<char, int> m;
vector<vector<int>> pos;
int G;
long double dp[1 << MAXG];
int PREF[MAXG][MAXG][MAXN], SUF[MAXG][MAXG][MAXN];
long double compute(int i, int cnt, int mask) {
    long double ret = 0;
    int rcnt = pos[i].size() - cnt;
    ret += cnt * (cnt - 1) * 0.25;
    ret += rcnt * (rcnt - 1) * 0.25;
    for (int j = 0; j < G; ++j) {
        if (mask & (1 << j)) ret += (cnt ? PREF[i][j][cnt - 1] : 0) + (rcnt ? SUF[i][j][rcnt - 1] : 0);
    }
    return ret;
}
signed main() {
    string s;
    cin >> s;
    vector<int> v(s.length());
    int cnt = 0;
    for (int i = 0; i < s.length(); ++i) {
        if (m.find(s[i]) != m.end()) v[i] = m[s[i]];
        else v[i] = m[s[i]] = cnt++;
    }
    G = *max_element(begin(v), end(v)) + 1;
    pos.resize(G);
    int n = s.length();
    for (int i = 0; i < n; ++i) pos[v[i]].push_back(i);
    dp[0] = 0;
    for (int i = 0; i < G; ++i) {
        for (int j = 0; j < G; ++j) {
            if (i == j) continue;
            int ptr = 0, cant = 0;
            for (int k = 0; k < pos[i].size(); ++k) {
                while (ptr < pos[i][k]) cant += v[ptr++] == j;
                PREF[i][j][k] = cant;
                if (k) PREF[i][j][k] += PREF[i][j][k - 1];
            }
            ptr = n - 1, cant = 0;
            for (int k = 0; k < pos[i].size(); ++k) {
                int idx = pos[i].size() - k - 1;
                while (ptr > pos[i][idx]) cant += v[ptr--] == j;
                SUF[i][j][k] = cant;
                if (k) SUF[i][j][k] += SUF[i][j][k - 1];
            }
        }
    }
    for (int mask = 1; mask < (1 << G); mask++) {
        dp[mask] = 1e18;
        for (int i = 0; i < G; i++) {
            if (!(mask & (1 << i))) continue;
            long double EV = compute(i, pos[i].size(), mask);
            int l = 0, r = pos[i].size() - 1;
            while (l <= r) {
                int mid = (l + r) >> 1;
                if (compute(i, mid, mask) <= compute(i, mid + 1, mask)) EV = min(EV, compute(i, mid, mask)), r = mid - 1;
                else l = mid + 1;
            }
            dp[mask] = min(dp[mask], EV + dp[mask ^ (1 << i)]);
        }
    }
    cout << fixed << setprecision(8) << dp[(1 << G) - 1];
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 348 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 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 348 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 3 ms 2260 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 3 ms 2516 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 3 ms 2516 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 3 ms 2412 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 ms 444 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 24 ms 74284 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 10 ms 72408 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 8 ms 72536 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 8 ms 72172 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 7 ms 72256 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 7 ms 65992 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 8 ms 72208 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 8 ms 72216 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 8 ms 74332 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 8 ms 72260 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 8 ms 72284 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 8 ms 72284 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 8 ms 72284 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 8 ms 72272 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 8 ms 72436 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 ms 444 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 24 ms 74284 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 10 ms 72408 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 8 ms 72536 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 8 ms 72172 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 7 ms 72256 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 7 ms 65992 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 8 ms 72208 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 8 ms 72216 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 8 ms 74332 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 8 ms 72260 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 8 ms 72284 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 8 ms 72284 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 8 ms 72284 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 8 ms 72272 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 8 ms 72436 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 ms 8536 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 8 ms 72284 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 8 ms 72192 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 8 ms 72284 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 8 ms 74332 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 8 ms 74332 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 7 ms 65884 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 8 ms 72280 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 9 ms 74328 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 8 ms 72376 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 8 ms 72284 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 8 ms 72284 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 8 ms 74312 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 8 ms 72536 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 8 ms 72284 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 8 ms 72536 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 14 ms 75824 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 12 ms 73816 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 11 ms 76376 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 13 ms 75868 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 13 ms 73820 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 13 ms 73820 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 13 ms 75864 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 13 ms 73820 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 13 ms 73820 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 13 ms 75716 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 348 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 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 348 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 3 ms 2260 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 3 ms 2516 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 3 ms 2516 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 3 ms 2412 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 2 ms 8540 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 0 ms 444 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 24 ms 74284 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 10 ms 72408 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 8 ms 72536 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 8 ms 72172 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 7 ms 72256 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 7 ms 65992 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 8 ms 72208 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 8 ms 72216 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 8 ms 74332 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 8 ms 72260 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 8 ms 72284 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 8 ms 72284 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 8 ms 72284 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 8 ms 72272 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 8 ms 72436 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 1 ms 8536 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 1 ms 344 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 8 ms 72284 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 8 ms 72192 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 8 ms 72284 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 8 ms 74332 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 8 ms 74332 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 7 ms 65884 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 8 ms 72280 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 9 ms 74328 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 8 ms 72376 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 8 ms 72284 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 8 ms 72284 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 8 ms 74312 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 8 ms 72536 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 8 ms 72284 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 8 ms 72536 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 604 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 14 ms 75824 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 12 ms 73816 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 11 ms 76376 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 13 ms 75868 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 13 ms 73820 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 13 ms 73820 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 13 ms 75864 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 13 ms 73820 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 13 ms 73820 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 13 ms 75716 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 6 ms 47552 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 58 ms 74580 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 0 ms 348 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 0 ms 440 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 3 ms 2256 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 3 ms 2516 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 3 ms 2628 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 3 ms 2516 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 1 ms 8540 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 0 ms 344 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 8 ms 72284 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 8 ms 74332 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 8 ms 72148 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 9 ms 72244 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 8 ms 72184 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 8 ms 65884 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 8 ms 74328 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 8 ms 74332 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 9 ms 72284 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 7 ms 72284 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 8 ms 72284 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 8 ms 74328 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 8 ms 72284 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 9 ms 74332 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 8 ms 72260 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 14 ms 73820 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 13 ms 75920 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 11 ms 74332 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 13 ms 75868 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 13 ms 75988 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 13 ms 74016 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 13 ms 73820 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 13 ms 75868 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 13 ms 73820 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 13 ms 75868 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 265 ms 93920 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 38 ms 76092 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 238 ms 94080 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 94 ms 100292 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 47 ms 74516 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 221 ms 95828 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 243 ms 95748 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 238 ms 93780 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 246 ms 94692 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 241 ms 93520 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 236 ms 94036 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 234 ms 93248 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 133 ms 93504 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 248 ms 93984 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'