oj.uz

Submission #723347

# Submission time Handle Problem Language Result Execution time Memory
723347 2023-04-13T15:55:17 Z drdilyor Boarding Passes (BOI22_passes) C++17
60 / 100
 2000 ms 471840 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
 
inline ll exp_inv(ll x) {
    return x * (x-1);
}
 
int main() {
    char a = 'A';
    string s; cin >> s;
    const int G = 15;
    int n = s.size();
    if (n == 1) {
        cout << "0\n";
        return 0;
    }

    vector suml(G, vector(n, vector(G, 0ll)));
    vector sumr(G, vector(n, vector(G, 0ll)));
    vector cl(G, vector(n, 0ll));
    vector cr(G, vector(n, 0ll));
    vector ix(G, vector<int>());
    for (int c1 = 0; c1 < G; c1++) {
        for (int c2 = 0; c2 < G; c2++) {
            ll res = 0, cur = 0;
            for (int i = 0; i < n; i++) {
                if (s[i] == c1+a)
                    res += cur;
                else if (s[i] == c2+a)
                    cur++;
                suml[c1][i][c2] = res;
            }
        }
    }
    for (int c1 = 0; c1 < G; c1++) {
        for (int c2 = 0; c2 < G; c2++) {
            ll res = 0, cur = 0;
            for (int i = n-1; i >= 0; i --) {
                if (s[i] == c1+a)
                    res += cur;
                else if (s[i] == c2+a)
                    cur++;
                sumr[c1][i][c2] = res;
            }
        }
    }
    for (int j = 0; j < G; j++) {
        int c = 0;
        for (int i = 0; i < n;i ++) {
            if (s[i] == j+a)
                c++;
            cl[j][i] = c;
        }
    }
    for (int j = 0; j < G; j++) {
        int c = 0;
        for (int i = n-1; i >= 0; i--) {
            if (s[i] == j+a)
                c++;
            cr[j][i] = c;
        }
    }
    for (int i = 0; i < n ;i++) 
        ix[s[i] - a].push_back(i);

    vector memo(1<<G, (ll)1e18);
    memo[(1<<G)-1] = 0;
    for (int used = (1<<G)-1-1; used >= 0; used--) {
        ll& res = memo[used];
        for (int i = 0 ;i < G; i++) {
            if (used&1<<i) continue;

            auto f = [&](int j) {
                ll sum = 0;
                for (int c2 = 0; c2 < G; c2++) {
                    if (used&1<<c2) {
                        if (j) sum += suml[i][j-1][c2];
                        if (j <n)sum += sumr[i][j][c2];
                    }
                }
                return sum * 4 + (j < n ? exp_inv(cr[i][j]) : 0) + (j ? exp_inv(cl[i][j-1]) : 0);
            };

            int l = -1, r = (int)ix[i].size()-2;
            while (l < r-1) {
                int m = (l+r) / 2;
                ll a = f(ix[i][m]), b = f(ix[i][m+1]);
                if (a == b) break;
                else if (a < b) r = m;
                else l = m;
            }
 
            for (int j = max(l-1, 0); j < min((int)ix[i].size(), 2 + max(0, r)); j++) {
                res = min(res, f(ix[i][j]) + memo[used |1<<i]);
            }
            res = min(res, f(0) + memo[used | 1<<i]);
            res = min(res, f(n) + memo[used | 1<<i]);
        }
    };
    ll ans;
    ans = memo[0];
 
    cout << ans / 4;
    if (ans%4 == 1) cout << ".25";
    if (ans%4 == 2) cout << ".5";
    if (ans%4== 3) cout << ".75";
    cout << endl;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 4820 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 44 ms 572 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 48 ms 576 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 78 ms 5260 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 672 ms 371652 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 826 ms 442792 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 868 ms 471764 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 825 ms 471840 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 64 ms 1036 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 170 ms 1032 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 145 ms 1016 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 74 ms 980 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 57 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 174 ms 980 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 100 ms 700 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 105 ms 696 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 109 ms 692 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 94 ms 688 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 108 ms 596 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 109 ms 700 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 110 ms 688 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 95 ms 596 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 107 ms 596 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 98 ms 596 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 64 ms 1036 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 170 ms 1032 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 145 ms 1016 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 74 ms 980 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 57 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 174 ms 980 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 100 ms 700 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 105 ms 696 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 109 ms 692 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 94 ms 688 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 108 ms 596 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 109 ms 700 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 110 ms 688 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 95 ms 596 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 107 ms 596 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 98 ms 596 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 54 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 62 ms 1036 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 166 ms 1028 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 145 ms 980 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 74 ms 1060 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 58 ms 604 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 168 ms 852 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 104 ms 688 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 102 ms 696 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 109 ms 692 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 95 ms 696 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 106 ms 708 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 113 ms 596 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 114 ms 716 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 94 ms 696 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 106 ms 596 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 101 ms 684 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 139 ms 47712 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 132 ms 47716 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 514 ms 47720 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 413 ms 47724 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 307 ms 47840 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 431 ms 47540 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 445 ms 46748 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 719 ms 46624 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 905 ms 46748 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 533 ms 46744 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 546 ms 46748 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 700 ms 46744 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 4820 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 44 ms 572 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 48 ms 576 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 78 ms 5260 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 672 ms 371652 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 826 ms 442792 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 868 ms 471764 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 825 ms 471840 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 51 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 64 ms 1036 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 170 ms 1032 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 145 ms 1016 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 74 ms 980 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 57 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 174 ms 980 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 100 ms 700 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 105 ms 696 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 109 ms 692 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 94 ms 688 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 108 ms 596 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 109 ms 700 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 110 ms 688 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 95 ms 596 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 107 ms 596 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 98 ms 596 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 54 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 62 ms 1036 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 166 ms 1028 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 145 ms 980 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 74 ms 1060 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 58 ms 604 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 168 ms 852 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 104 ms 688 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 102 ms 696 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 109 ms 692 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 95 ms 696 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 106 ms 708 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 113 ms 596 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 114 ms 716 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 94 ms 696 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 106 ms 596 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 101 ms 684 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 139 ms 47712 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 132 ms 47716 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 514 ms 47720 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 413 ms 47724 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 307 ms 47840 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 431 ms 47540 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 445 ms 46748 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 719 ms 46624 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 905 ms 46748 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 533 ms 46744 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 546 ms 46748 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 700 ms 46744 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 70 ms 596 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 86 ms 696 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 80 ms 4808 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 41 ms 468 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 49 ms 572 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 77 ms 5264 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 629 ms 371696 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 748 ms 442740 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 798 ms 471788 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 805 ms 471720 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 54 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 63 ms 980 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 165 ms 1028 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 148 ms 1100 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 78 ms 980 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 58 ms 716 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 163 ms 960 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 96 ms 700 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 102 ms 684 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 107 ms 596 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 97 ms 596 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 105 ms 692 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 118 ms 596 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 119 ms 696 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 91 ms 696 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 101 ms 596 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 97 ms 692 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 128 ms 47716 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 132 ms 47716 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 507 ms 47844 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 414 ms 47724 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 311 ms 47712 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 433 ms 47552 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 443 ms 46820 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 798 ms 46752 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 901 ms 46748 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 539 ms 46748 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 540 ms 46752 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 680 ms 46744 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 1584 ms 471788 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 143 ms 776 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 1361 ms 471696 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 884 ms 471840 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 74 ms 596 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 1432 ms 471704 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Execution timed out 2111 ms 471700 KB Time limit exceeded
103 Halted 0 ms 0 KB -