oj.uz

Submission #954664

# Submission time Handle Problem Language Result Execution time Memory
954664 2024-03-28T09:52:17 Z ifateen Boarding Passes (BOI22_passes) C++17
100 / 100
 242 ms 140808 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];
double dp[1 << MAXG];
double compute(int i, int count, int mask) {
    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;
            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 2396 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 2396 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 2396 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 2396 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 2396 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 3 ms 12052 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 4 ms 14612 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 3 ms 14608 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 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 92764 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 10 ms 92764 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 11 ms 92764 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 12 ms 92764 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 10 ms 92764 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 8 ms 68188 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 11 ms 92772 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 10 ms 92760 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 11 ms 92764 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 10 ms 92764 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 10 ms 92764 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 11 ms 92760 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 11 ms 92764 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 10 ms 92792 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 12 ms 92668 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 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 92764 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 10 ms 92764 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 11 ms 92764 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 12 ms 92764 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 10 ms 92764 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 8 ms 68188 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 11 ms 92772 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 10 ms 92760 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 11 ms 92764 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 10 ms 92764 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 10 ms 92764 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 11 ms 92760 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 11 ms 92764 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 10 ms 92792 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 12 ms 92668 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 2 ms 10584 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 1 ms 2396 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 10 ms 92760 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 10 ms 92764 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 10 ms 92764 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 11 ms 92764 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 11 ms 92760 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 7 ms 68184 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 10 ms 92760 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 10 ms 92668 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 10 ms 92764 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 10 ms 92764 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 10 ms 92692 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 10 ms 92764 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 10 ms 92764 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 10 ms 92764 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 10 ms 92764 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 16 ms 114268 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 16 ms 116316 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 14 ms 114012 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 16 ms 112220 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 16 ms 110428 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 16 ms 112476 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 16 ms 110172 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 16 ms 110172 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 16 ms 110172 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 15 ms 114268 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 2396 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 2396 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 2396 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 2396 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 2396 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 3 ms 12052 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 4 ms 14612 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 3 ms 14608 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 2 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 92764 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 10 ms 92764 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 11 ms 92764 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 12 ms 92764 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 10 ms 92764 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 8 ms 68188 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 11 ms 92772 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 10 ms 92760 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 11 ms 92764 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 10 ms 92764 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 10 ms 92764 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 11 ms 92760 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 11 ms 92764 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 10 ms 92792 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 12 ms 92668 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 2 ms 10584 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 1 ms 2396 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 10 ms 92760 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 10 ms 92764 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 10 ms 92764 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 11 ms 92764 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 11 ms 92760 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 7 ms 68184 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 10 ms 92760 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 10 ms 92668 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 10 ms 92764 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 10 ms 92764 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 10 ms 92692 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 10 ms 92764 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 10 ms 92764 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 10 ms 92764 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 10 ms 92764 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 16 ms 114268 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 16 ms 116316 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 14 ms 114012 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 16 ms 112220 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 16 ms 110428 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 16 ms 112476 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 16 ms 110172 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 16 ms 110172 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 16 ms 110172 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 15 ms 114268 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 6 ms 51548 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 57 ms 108940 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 1 ms 2392 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 2648 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 1 ms 2392 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 12308 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 4 ms 14612 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 5 ms 14864 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 2 ms 10584 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 92764 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 11 ms 92764 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 10 ms 92764 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 10 ms 92780 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 11 ms 92768 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 9 ms 68188 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 10 ms 92764 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 10 ms 92764 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 10 ms 92764 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 10 ms 92764 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 10 ms 92760 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 10 ms 92764 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 11 ms 92708 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 10 ms 92764 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 11 ms 92764 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 1 ms 2648 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 16 ms 116316 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 16 ms 116476 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 14 ms 114264 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 15 ms 110172 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 17 ms 112472 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 16 ms 112476 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 17 ms 116316 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 16 ms 114268 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 18 ms 110172 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 15 ms 108380 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 216 ms 130924 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 39 ms 114772 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 202 ms 134872 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 82 ms 140808 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 48 ms 115280 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 178 ms 130640 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 211 ms 128852 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 209 ms 131080 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 242 ms 129100 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 202 ms 130640 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 192 ms 130884 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 201 ms 129872 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 106 ms 128084 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 213 ms 128472 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'