oj.uz

Submission #954658

# Submission time Handle Problem Language Result Execution time Memory
954658 2024-03-28T09:48:16 Z ifateen Boarding Passes (BOI22_passes) C++17
100 / 100
 244 ms 155148 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e5 + 5, MAXG = 15;
map<char, int> m;
vector<int> pos[MAXG];
int n, cnt = 0, G, v[MAXN], PREF[MAXG][MAXG][MAXN], SUF[MAXG][MAXG][MAXN], pref[MAXN][MAXG];
long double dp[1 << MAXG];
long double compute(int i, int count, int mask) {
    long double ret = 0;
    int rcnt = pos[i].size() - count;
    ret += count * (count - 1) * 0.25 + rcnt * (rcnt - 1) * 0.25;
    for (int j = 0; j < G; ++j)
        if (mask & (1 << j)) ret += (count ? PREF[i][j][count - 1] : 0) + (rcnt ? SUF[i][j][rcnt - 1] : 0);
    return ret;
}
signed main() {
    iostream::sync_with_stdio(false), cin.tie(nullptr);
    string s; cin >> s;
    n = s.length();
    for (int i = 0; i < n; ++i) {
        if (m.find(s[i]) != m.end()) v[i] = m[s[i]];
        else v[i] = m[s[i]] = cnt++;
        G = max(G, v[i] + 1);
        pos[v[i]].push_back(i);
        pref[i][v[i]] = 1;
    }
    dp[0] = 0;
    for (int i = 1; i < n; ++i) for (int j = 0; j < G; ++j) pref[i][j] += pref[i - 1][j];
    for (int i = 0; i < G; ++i)
        for (int j = 0; j < G; ++j) {
            if (i == j) continue;
            for (int k = 0; k < pos[i].size(); ++k) {
                PREF[i][j][k] = pref[pos[i][k]][j] + (k ? PREF[i][j][k - 1] : 0);
            }
            for (int k = 0; k < pos[i].size(); ++k) {
                int idx = pos[i].size() - k - 1;
                SUF[i][j][k] = pref[n - 1][j] - (pos[i][idx] ? pref[pos[i][idx] - 1][j] : 0) + (k ? SUF[i][j][k - 1] : 0);
            }
        }
    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), c;
            int l = 0, r = pos[i].size() - 1;
            while (l <= r) {
                int mid = (l + r) >> 1;
                if ((c = compute(i, mid, mask)) <= compute(i, mid + 1, mask)) EV = min(EV, c), r = mid - 1;
                else l = mid + 1;
            }
            dp[mask] = min(dp[mask], EV + dp[mask ^ (1 << i)]);
        }
    }
    cout << fixed << setprecision(1) << dp[(1 << G) - 1];
}

Compilation message

passes.cpp: In function 'int main()':
passes.cpp:33: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]
   33 |             for (int k = 0; k < pos[i].size(); ++k) {
      |                             ~~^~~~~~~~~~~~~~~
passes.cpp:36: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]
   36 |             for (int k = 0; k < pos[i].size(); ++k) {
      |                             ~~^~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 2392 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 2396 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 2392 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 2396 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 3 ms 12308 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 4 ms 14608 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 4 ms 14612 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 4 ms 14612 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 2396 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 10 ms 90600 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 10 ms 90716 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 10 ms 90588 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 11 ms 90712 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 10 ms 90716 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 7 ms 68164 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 11 ms 90716 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 10 ms 90624 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 10 ms 90716 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 10 ms 90588 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 10 ms 90716 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 10 ms 90712 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 10 ms 90716 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 10 ms 90716 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 9 ms 90704 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 10588 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 2396 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 10 ms 90600 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 10 ms 90716 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 10 ms 90588 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 11 ms 90712 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 10 ms 90716 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 7 ms 68164 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 11 ms 90716 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 10 ms 90624 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 10 ms 90716 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 10 ms 90588 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 10 ms 90716 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 10 ms 90712 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 10 ms 90716 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 10 ms 90716 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 9 ms 90704 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 2 ms 10588 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 1 ms 2392 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 10 ms 90712 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 11 ms 90716 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 10 ms 90916 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 10 ms 90716 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 10 ms 90712 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 8 ms 68188 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 10 ms 90716 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 9 ms 90716 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 10 ms 90716 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 10 ms 90716 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 11 ms 90716 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 10 ms 90716 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 10 ms 90716 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 10 ms 90716 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 10 ms 90668 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 1 ms 2652 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 1 ms 2652 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 32 ms 124496 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 17 ms 122528 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 15 ms 124152 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 17 ms 124568 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 18 ms 122460 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 17 ms 124504 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 18 ms 122460 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 18 ms 122460 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 17 ms 122456 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 18 ms 122460 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 2392 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 2396 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 2392 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 2396 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 3 ms 12308 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 4 ms 14608 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 4 ms 14612 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 4 ms 14612 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 1 ms 10588 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 1 ms 2396 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 10 ms 90600 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 10 ms 90716 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 10 ms 90588 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 11 ms 90712 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 10 ms 90716 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 7 ms 68164 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 11 ms 90716 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 10 ms 90624 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 10 ms 90716 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 10 ms 90588 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 10 ms 90716 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 10 ms 90712 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 10 ms 90716 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 10 ms 90716 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 9 ms 90704 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 2 ms 10588 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 1 ms 2392 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 10 ms 90712 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 11 ms 90716 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 10 ms 90916 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 10 ms 90716 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 10 ms 90712 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 8 ms 68188 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 10 ms 90716 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 9 ms 90716 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 10 ms 90716 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 10 ms 90716 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 11 ms 90716 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 10 ms 90716 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 10 ms 90716 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 10 ms 90716 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 10 ms 90668 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 1 ms 2652 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 1 ms 2652 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 32 ms 124496 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 17 ms 122528 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 15 ms 124152 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 17 ms 124568 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 18 ms 122460 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 17 ms 124504 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 18 ms 122460 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 18 ms 122460 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 17 ms 122456 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 18 ms 122460 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 5 ms 47452 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 64 ms 121196 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 1 ms 2396 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 1 ms 2396 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 1 ms 2396 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 0 ms 2396 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 1 ms 2396 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 3 ms 12304 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 4 ms 14608 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 4 ms 14612 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 4 ms 14612 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 1 ms 10588 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 1 ms 2396 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 10 ms 90684 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 10 ms 90716 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 10 ms 90716 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 10 ms 90716 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 10 ms 90716 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 7 ms 68076 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 10 ms 90716 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 11 ms 90636 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 10 ms 90716 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 11 ms 90728 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 10 ms 90716 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 10 ms 90600 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 10 ms 90716 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 10 ms 90716 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 10 ms 90716 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 1 ms 2652 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 1 ms 2652 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 18 ms 126556 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 18 ms 128604 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 16 ms 128092 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 17 ms 126556 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 18 ms 128476 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 17 ms 126560 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 28 ms 134480 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 18 ms 134432 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 19 ms 134492 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 18 ms 132444 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 244 ms 149692 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 48 ms 131156 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 236 ms 147744 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 87 ms 155148 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 55 ms 133212 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 215 ms 149584 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 239 ms 148048 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 233 ms 146068 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 219 ms 142420 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 236 ms 146260 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 235 ms 146104 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 223 ms 145376 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 132 ms 143232 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 233 ms 145120 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'