oj.uz

Submission #723336

# Submission time Handle Problem Language Result Execution time Memory
723336 2023-04-13T15:46:55 Z drdilyor Boarding Passes (BOI22_passes) C++17
60 / 100
 2000 ms 378260 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(G, vector(n, 0ll)));
    vector sumr(G, vector(G, vector(n, 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][c2][i] = 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][c2][i] = 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][c2][j-1];
                        if (j <n)sum += sumr[i][c2][j];
                    }
                }
                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 87 ms 3924 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 304 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 41 ms 468 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 49 ms 604 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 101 ms 4332 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 323 ms 297228 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 306 ms 354872 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 341 ms 378204 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 348 ms 378128 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 70 ms 952 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 182 ms 936 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 159 ms 852 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 73 ms 948 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 61 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 177 ms 852 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 102 ms 688 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 100 ms 680 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 120 ms 672 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 110 ms 724 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 106 ms 596 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 109 ms 684 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 118 ms 596 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 101 ms 596 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 106 ms 676 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 104 ms 680 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 70 ms 952 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 182 ms 936 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 159 ms 852 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 73 ms 948 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 61 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 177 ms 852 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 102 ms 688 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 100 ms 680 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 120 ms 672 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 110 ms 724 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 106 ms 596 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 109 ms 684 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 118 ms 596 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 101 ms 596 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 106 ms 676 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 104 ms 680 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 55 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 69 ms 852 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 172 ms 852 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 159 ms 956 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 74 ms 852 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 58 ms 596 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 118 ms 588 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 104 ms 688 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 120 ms 716 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 98 ms 596 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 110 ms 684 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 112 ms 676 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 123 ms 676 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 94 ms 596 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 114 ms 720 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 104 ms 676 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 105 ms 38296 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 107 ms 38280 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 488 ms 38260 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 440 ms 38248 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 292 ms 38292 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 435 ms 38096 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 433 ms 37580 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 751 ms 37460 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 896 ms 37452 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 538 ms 37456 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 557 ms 37460 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 672 ms 37464 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 3924 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 304 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 41 ms 468 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 49 ms 604 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 101 ms 4332 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 323 ms 297228 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 306 ms 354872 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 341 ms 378204 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 348 ms 378128 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 53 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 70 ms 952 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 182 ms 936 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 159 ms 852 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 73 ms 948 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 61 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 177 ms 852 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 102 ms 688 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 100 ms 680 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 120 ms 672 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 110 ms 724 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 106 ms 596 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 109 ms 684 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 118 ms 596 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 101 ms 596 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 106 ms 676 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 104 ms 680 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 55 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 69 ms 852 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 172 ms 852 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 159 ms 956 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 74 ms 852 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 58 ms 596 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 118 ms 588 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 104 ms 688 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 120 ms 716 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 98 ms 596 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 110 ms 684 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 112 ms 676 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 123 ms 676 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 94 ms 596 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 114 ms 720 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 104 ms 676 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 105 ms 38296 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 107 ms 38280 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 488 ms 38260 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 440 ms 38248 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 292 ms 38292 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 435 ms 38096 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 433 ms 37580 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 751 ms 37460 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 896 ms 37452 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 538 ms 37456 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 557 ms 37460 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 672 ms 37464 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 85 ms 612 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 106 ms 684 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 76 ms 3956 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 40 ms 596 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 59 ms 592 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 79 ms 4264 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 273 ms 297264 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 354 ms 354880 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 320 ms 378208 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 339 ms 378260 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 55 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 65 ms 960 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 168 ms 936 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 160 ms 944 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 78 ms 960 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 59 ms 608 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 173 ms 852 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 111 ms 676 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 108 ms 676 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 112 ms 724 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 99 ms 672 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 117 ms 596 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 110 ms 688 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 113 ms 680 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 96 ms 596 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 102 ms 692 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 100 ms 596 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 105 ms 38236 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 114 ms 38292 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 473 ms 38252 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 423 ms 38240 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 283 ms 38220 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 445 ms 38100 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 429 ms 37472 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 743 ms 37464 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 831 ms 37464 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 517 ms 37460 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 498 ms 37464 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 647 ms 37468 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 1212 ms 377804 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 166 ms 736 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 937 ms 377784 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 356 ms 378196 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 75 ms 660 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 1041 ms 377764 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Execution timed out 2088 ms 378036 KB Time limit exceeded
103 Halted 0 ms 0 KB -