oj.uz

Submission #723263

# Submission time Handle Problem Language Result Execution time Memory
723263 2023-04-13T12:54:44 Z drdilyor Boarding Passes (BOI22_passes) C++17
55 / 100
 2000 ms 130424 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)));
    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;
            }
        }
    }

    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);
            ll sum = 0, c = 0;
            for (int j = 0; j < n; j++) {
                if (s[j] == i + a)
                    c++;
                sum = 0;
                for (int c2 = 0; c2 < G; c2++)
                    if (used&1<<c2)
                        sum += suml[i][c2][j];
                left[j] = sum * 4 + exp_inv(c);
            }
 
            sum = c = 0;
            for (int j = n-1; j >= 0; j--) {
                if (s[j] == i + a)
                    c++;
                sum = 0;
                for (int c2 = 0; c2 < G; c2++)
                    if (used&1<<c2)
                        sum += sumr[i][c2][j];
                right[j] = sum * 4 + exp_inv(c);
            }
 
            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 116 ms 1764 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 134 ms 1876 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Execution timed out 2078 ms 130424 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 14 ms 480 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 14 ms 472 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 14 ms 476 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 15 ms 468 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 13 ms 448 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 5 ms 356 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 5 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 5 ms 340 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 5 ms 364 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 6 ms 340 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 6 ms 340 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 5 ms 340 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 5 ms 360 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 6 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 14 ms 480 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 14 ms 472 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 14 ms 476 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 15 ms 468 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 13 ms 448 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 5 ms 356 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 5 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 5 ms 340 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 5 ms 364 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 6 ms 340 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 6 ms 340 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 5 ms 340 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 5 ms 360 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 6 ms 340 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 3 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 14 ms 476 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 14 ms 468 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 14 ms 476 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 15 ms 480 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 3 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 14 ms 452 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 5 ms 340 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 5 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 5 ms 340 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 5 ms 364 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 5 ms 360 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 5 ms 340 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 5 ms 340 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 5 ms 340 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 5 ms 364 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 1216 ms 16840 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 1311 ms 16820 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 1375 ms 16820 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 1284 ms 16820 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 1289 ms 16828 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 1314 ms 16756 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 1288 ms 16476 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 1280 ms 16472 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 1269 ms 16468 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 1296 ms 16476 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 1280 ms 16588 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 1276 ms 16476 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 1764 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 134 ms 1876 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Execution timed out 2078 ms 130424 KB Time limit exceeded
7 Halted 0 ms 0 KB -