oj.uz

Submission #954641

# Submission time Handle Problem Language Result Execution time Memory
954641 2024-03-28T09:25:32 Z ifateen Boarding Passes (BOI22_passes) C++17
100 / 100
 293 ms 169276 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() {
    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(8) << 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 1 ms 2396 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 5 ms 12240 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 5 ms 14544 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 5 ms 14544 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 6 ms 14544 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 12 ms 90716 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 10 ms 90720 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 11 ms 90716 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 11 ms 90716 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 11 ms 90632 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 7 ms 67932 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 90652 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 90716 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 90716 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 10 ms 90644 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 10 ms 90712 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 10 ms 90716 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 12 ms 90716 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 10 ms 90720 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 11 ms 90716 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 11 ms 90716 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 11 ms 90632 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 7 ms 67932 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 90652 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 90716 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 90716 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 10 ms 90644 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 10 ms 90712 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 10 ms 90716 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 ms 10588 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 1 ms 2404 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 11 ms 90724 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 10 ms 90712 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 10 ms 90912 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 10 ms 90556 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 10 ms 90716 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 9 ms 68028 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 10 ms 90712 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 11 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 90712 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 10 ms 90968 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 11 ms 90748 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 10 ms 90716 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 2 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 33 ms 142808 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 19 ms 142684 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 17 ms 142432 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 19 ms 142680 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 19 ms 142684 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 21 ms 144720 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 19 ms 146780 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 20 ms 142684 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 20 ms 142684 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 20 ms 144752 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 1 ms 2396 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 5 ms 12240 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 5 ms 14544 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 5 ms 14544 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 6 ms 14544 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 12 ms 90716 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 10 ms 90720 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 11 ms 90716 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 11 ms 90716 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 11 ms 90632 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 7 ms 67932 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 90652 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 90716 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 90716 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 10 ms 90644 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 10 ms 90712 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 10 ms 90716 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 1 ms 10588 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 1 ms 2404 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 11 ms 90724 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 10 ms 90712 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 10 ms 90912 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 10 ms 90556 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 10 ms 90716 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 9 ms 68028 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 10 ms 90712 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 11 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 90712 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 10 ms 90968 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 11 ms 90748 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 10 ms 90716 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 2 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 33 ms 142808 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 19 ms 142684 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 17 ms 142432 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 19 ms 142680 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 19 ms 142684 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 21 ms 144720 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 19 ms 146780 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 20 ms 142684 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 20 ms 142684 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 20 ms 144752 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 67 ms 147632 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 2488 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 1 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 4 ms 12240 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 5 ms 14544 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 5 ms 14544 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 5 ms 14544 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 2 ms 10588 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 1 ms 2392 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 11 ms 90556 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 10 ms 90720 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 12 ms 90712 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 90668 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 7 ms 67928 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 10 ms 90712 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 10 ms 90712 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 90720 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 11 ms 90712 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 10 ms 90716 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 11 ms 90732 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 10 ms 90596 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 11 ms 90716 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 2 ms 2652 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 1 ms 2756 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 19 ms 140636 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 19 ms 140576 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 17 ms 142432 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 19 ms 138588 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 22 ms 142828 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 20 ms 140624 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 20 ms 140636 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 19 ms 140632 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 21 ms 138680 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 19 ms 140692 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 293 ms 157660 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 46 ms 145408 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 254 ms 161288 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 92 ms 169276 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 56 ms 147676 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 210 ms 159508 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 245 ms 159728 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 225 ms 161360 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 237 ms 159592 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 234 ms 161304 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 262 ms 161632 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 234 ms 160912 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 134 ms 158248 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 235 ms 162408 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'