oj.uz

Submission #723258

# Submission time Handle Problem Language Result Execution time Memory
723258 2023-04-13T12:48:39 Z drdilyor Boarding Passes (BOI22_passes) C++17
30 / 100
 2000 ms 166008 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, (ld)-1);
    auto dp = [&](auto& dp, int used)->ld{
        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;
        }
 
        ld res = 1e18;
        for (int i = 0 ;i < G; i++) {
            ld cur = 1e18;
            if (used&1<<i) continue;
            vector<ld> 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 180 ms 2044 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 177 ms 2220 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 99 ms 130476 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 95 ms 155800 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 98 ms 165844 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 98 ms 166008 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 26 ms 520 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 23 ms 516 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 24 ms 468 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 19 ms 468 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 3 ms 340 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 17 ms 468 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 9 ms 376 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 8 ms 376 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 6 ms 340 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 7 ms 380 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 9 ms 340 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 7 ms 340 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 7 ms 376 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 7 ms 376 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 7 ms 372 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 7 ms 340 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
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 26 ms 520 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 23 ms 516 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 24 ms 468 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 19 ms 468 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 3 ms 340 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 17 ms 468 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 9 ms 376 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 8 ms 376 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 6 ms 340 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 7 ms 380 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 9 ms 340 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 7 ms 340 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 7 ms 376 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 7 ms 376 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 7 ms 372 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 7 ms 340 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 3 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 22 ms 468 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 30 ms 468 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 20 ms 468 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 24 ms 516 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 3 ms 340 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 17 ms 468 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 7 ms 340 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 8 ms 372 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 7 ms 340 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 7 ms 376 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 7 ms 340 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 8 ms 376 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 7 ms 376 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 7 ms 340 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 6 ms 372 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 7 ms 340 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Execution timed out 2071 ms 19580 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 2044 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 177 ms 2220 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 99 ms 130476 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 95 ms 155800 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 98 ms 165844 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 98 ms 166008 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 26 ms 520 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 23 ms 516 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 24 ms 468 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 19 ms 468 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 3 ms 340 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 17 ms 468 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 9 ms 376 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 8 ms 376 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 6 ms 340 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 7 ms 380 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 9 ms 340 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 7 ms 340 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 7 ms 376 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 7 ms 376 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 7 ms 372 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 7 ms 340 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 3 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 22 ms 468 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 30 ms 468 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 20 ms 468 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 24 ms 516 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 3 ms 340 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 17 ms 468 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 7 ms 340 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 8 ms 372 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 7 ms 340 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 7 ms 376 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 7 ms 340 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 8 ms 376 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 7 ms 376 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 7 ms 340 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 6 ms 372 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 7 ms 340 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Execution timed out 2071 ms 19580 KB Time limit exceeded
45 Halted 0 ms 0 KB -