oj.uz

Submission #723265

# Submission time Handle Problem Language Result Execution time Memory
723265 2023-04-13T13:06:35 Z drdilyor Boarding Passes (BOI22_passes) C++17
55 / 100
 2000 ms 137624 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));
    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;
            vector<ll> left(n), right(n);

            auto f = [&](int j) {
                ll sum = 0;
                for (int c2 = 0; c2 < G; c2++)
                    if (used&1<<c2)
                        sum += suml[i][c2][j-1];
                for (int c2 = 0; c2 < G; c2++)
                    if (used&1<<c2)
                        sum += sumr[i][c2][j];
                return sum * 4 + exp_inv(cr[i][j]) + exp_inv(cl[i][j-1]);
            };
 
            for (int j = 1; j < n; j++)
                res = min(res, f(j) + 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 102 ms 1876 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 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 101 ms 2036 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Execution timed out 2067 ms 137624 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 12 ms 468 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 12 ms 484 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 12 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 3 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 9 ms 460 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 6 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 4 ms 340 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 4 ms 340 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 4 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 7 ms 364 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 4 ms 340 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 12 ms 468 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 12 ms 484 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 12 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 3 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 9 ms 460 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 6 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 4 ms 340 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 4 ms 340 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 4 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 7 ms 364 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 4 ms 340 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 11 ms 468 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 10 ms 468 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 10 ms 468 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 11 ms 492 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 2 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 10 ms 456 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 5 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 4 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 368 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 4 ms 340 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 1106 ms 17992 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 1130 ms 17996 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 1052 ms 17920 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 1074 ms 17948 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 1065 ms 17900 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 1075 ms 17944 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 1089 ms 17632 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 1099 ms 17532 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 1057 ms 17416 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 1063 ms 17560 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 1056 ms 17660 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 1091 ms 17516 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 1876 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 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 101 ms 2036 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Execution timed out 2067 ms 137624 KB Time limit exceeded
7 Halted 0 ms 0 KB -