oj.uz

Submission #723259

# Submission time Handle Problem Language Result Execution time Memory
723259 2023-04-13T12:49:53 Z drdilyor Boarding Passes (BOI22_passes) C++17
60 / 100
 1905 ms 165944 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
 
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, -1ll);
    auto dp = [&](auto& dp, int used)->ll{
        if (memo[used] >= 0) return memo[used];
        if (__builtin_popcount(used) == G) return 0;
        vector has(n, 0);
        for (int j = 0; j < n; j++) {
            if (used& 1<<(s[j] - a))
                has[j] = 1;
        }
 
        ll res = 1e18;
        for (int i = 0 ;i < G; i++) {
            ll cur = 1e18;
            if (used&1<<i) continue;
            vector<ll> left(n), right(n);
            ll sum = 0;
            ll t = 0, c = 0;
            for (int j = 0; j < n; j++) {
                if (s[j] == i + a)
                    c++;
                else t += has[j];
                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 = 0, t= 0, c = 0;
            for (int j = n-1; j >= 0; j--) {
                if (s[j] == i + a)
                    sum += t, c++;
                else t += has[j];
                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);
            }
 
            for (int mid = 1; mid < n; mid++) {
                cur = min(cur, left[mid-1] + right[mid]);
            }
            res = min(res, cur + dp(dp, used |1<<i));
        }
        return memo[used] = res;
    };
    ll ans;
    if (n > 10000) ans = exp_inv(n / 2) + exp_inv(n - n / 2);
    else ans = dp(dp, 0);
 
    cout << ans / 4;
    if (ans%4 == 1) cout << ".25";
    if (ans%4 == 2) cout << ".5";
    if (ans%4== 3) cout << ".75";
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 131 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 2 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 147 ms 2056 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 86 ms 130536 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 96 ms 155796 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 120 ms 165916 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 100 ms 165944 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

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 488 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 17 ms 484 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 16 ms 488 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 16 ms 468 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 15 ms 468 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 6 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 340 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 364 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 6 ms 340 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 5 ms 340 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 7 ms 464 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 488 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 17 ms 484 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 16 ms 488 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 16 ms 468 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 15 ms 468 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 6 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 340 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 364 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 6 ms 340 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 5 ms 340 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 7 ms 464 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 16 ms 488 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 18 ms 468 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 17 ms 468 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 17 ms 468 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 13 ms 464 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 6 ms 368 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 6 ms 360 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 7 ms 360 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 9 ms 364 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 5 ms 368 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 6 ms 340 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 9 ms 340 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 8 ms 340 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 6 ms 368 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 1569 ms 18000 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 1553 ms 18064 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 1633 ms 17976 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 1508 ms 17980 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 1562 ms 18120 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 1525 ms 18236 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 1553 ms 17708 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 1671 ms 17604 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 1851 ms 17608 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 1721 ms 17692 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 1905 ms 17660 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 1797 ms 17612 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 131 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 2 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 147 ms 2056 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 86 ms 130536 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 96 ms 155796 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 120 ms 165916 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 100 ms 165944 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 2 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 15 ms 488 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 17 ms 484 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 16 ms 488 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 16 ms 468 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 3 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 15 ms 468 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 6 ms 340 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 6 ms 340 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 5 ms 340 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 5 ms 340 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 5 ms 340 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 6 ms 340 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 6 ms 364 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 6 ms 340 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 5 ms 340 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 7 ms 464 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 2 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 16 ms 488 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 18 ms 468 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 17 ms 468 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 17 ms 468 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 3 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 13 ms 464 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 6 ms 368 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 6 ms 360 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 7 ms 360 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 9 ms 364 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 5 ms 368 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 6 ms 340 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 6 ms 340 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 9 ms 340 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 8 ms 340 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 6 ms 368 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 1569 ms 18000 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 1553 ms 18064 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 1633 ms 17976 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 1508 ms 17980 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 1562 ms 18120 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 1525 ms 18236 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 1553 ms 17708 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 1671 ms 17604 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 1851 ms 17608 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 1721 ms 17692 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 1905 ms 17660 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 1797 ms 17612 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Incorrect 6 ms 340 KB 1st numbers differ - expected: '7.5000000000', found: '6.0000000000', error = '0.2000000000'
57 Halted 0 ms 0 KB -