oj.uz

Submission #723264

# Submission time Handle Problem Language Result Execution time Memory
723264 2023-04-13T13:01:12 Z drdilyor Boarding Passes (BOI22_passes) C++17
55 / 100
 2000 ms 137200 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
 
ll exp_inv(ll x) {
    return x * (x-1);
}
 
int main() {
    char a = 'A';
    string s; cin >> s;
    const int G = 10;
    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));
    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;
        }
    }

    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;
            vector<ll> left(n), right(n);
            for (int j = 0; j < n; j++) {
                ll sum = 0;
                for (int c2 = 0; c2 < G; c2++)
                    if (used&1<<c2)
                        sum += suml[i][c2][j];
                left[j] = sum * 4 + exp_inv(cl[i][j]);
            }
 
            for (int j = n-1; j >= 0; j--) {
                ll sum = 0;
                for (int c2 = 0; c2 < G; c2++)
                    if (used&1<<c2)
                        sum += sumr[i][c2][j];
                right[j] = sum * 4 + exp_inv(cr[i][j]);
            }
 
            ll cur = left[n-1];
            for (int mid = 1; mid < n; mid++) {
                cur = min(cur, left[mid-1] + right[mid]);
            }
            res = min(res, cur + memo[used |1<<i]);
        }
    };
    ll ans;
    if (n > 10000) ans = exp_inv(n / 2) + exp_inv(n - n / 2);
    else ans = memo[0];
 
    cout << ans / 4;
    if (ans%4 == 1) cout << ".25";
    if (ans%4 == 2) cout << ".5";
    if (ans%4== 3) cout << ".75";
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 1748 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 2 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 107 ms 2028 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Execution timed out 2088 ms 137200 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 15 ms 468 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 12 ms 496 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 11 ms 480 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 12 ms 492 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 2 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 10 ms 460 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 4 ms 340 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 4 ms 340 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 5 ms 340 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 4 ms 364 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 4 ms 340 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 5 ms 340 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 4 ms 340 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 4 ms 340 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 4 ms 340 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 4 ms 368 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 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 15 ms 468 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 12 ms 496 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 11 ms 480 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 12 ms 492 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 2 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 10 ms 460 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 4 ms 340 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 4 ms 340 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 5 ms 340 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 4 ms 364 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 4 ms 340 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 5 ms 340 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 4 ms 340 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 4 ms 340 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 4 ms 340 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 4 ms 368 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 2 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 12 ms 468 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 11 ms 484 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 11 ms 468 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 13 ms 468 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 2 ms 340 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 10 ms 340 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 4 ms 340 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 4 ms 340 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 4 ms 340 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 4 ms 340 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 4 ms 340 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 6 ms 340 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 4 ms 340 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 4 ms 372 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 4 ms 340 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 5 ms 360 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 1093 ms 17992 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 1134 ms 17988 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 1137 ms 17884 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 1108 ms 18028 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 1132 ms 18020 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 1090 ms 18024 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 1081 ms 17412 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 1116 ms 17812 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 1096 ms 17452 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 1093 ms 17604 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 1121 ms 17584 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 1060 ms 17616 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 1748 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 2 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 107 ms 2028 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Execution timed out 2088 ms 137200 KB Time limit exceeded
7 Halted 0 ms 0 KB -