oj.uz

Submission #723158

# Submission time Handle Problem Language Result Execution time Memory
723158 2023-04-13T09:41:09 Z drdilyor Boarding Passes (BOI22_passes) C++17
25 / 100
 2000 ms 6300 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

ld exp_inv(ll x) {
    return x * (x-1) / 4.0l;
}

int main() {
    char a = 'A';
    string s; cin >> s;
    const int G = 15;
    int n = s.size();
    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;
        ld res = 1e18;
        for (int i = 0 ;i < G; i++) {
            ld cur = 1e18;
            if (used&1<<i) continue;
            vector has(n, 0);
            for (int j = 0; j < n; j++) {
                if (used& 1<<(s[j] - a))
                    has[j] = 1;
            }
            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)
                    sum += t, c++;
                else t += has[j];
                left[j] = sum + 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];
                right[j] = sum + 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;
    };
    cout << dp(dp, 0) << '\n';
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2083 ms 1300 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 724 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 489 ms 872 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 468 ms 852 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 474 ms 852 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 458 ms 852 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 65 ms 816 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 410 ms 852 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 131 ms 724 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 149 ms 724 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 137 ms 724 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 135 ms 724 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 137 ms 724 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 141 ms 724 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 140 ms 788 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 143 ms 724 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 145 ms 724 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 140 ms 724 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 724 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 489 ms 872 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 468 ms 852 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 474 ms 852 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 458 ms 852 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 65 ms 816 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 410 ms 852 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 131 ms 724 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 149 ms 724 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 137 ms 724 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 135 ms 724 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 137 ms 724 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 141 ms 724 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 140 ms 788 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 143 ms 724 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 145 ms 724 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 140 ms 724 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 43 ms 724 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 473 ms 880 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 473 ms 852 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 461 ms 852 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 466 ms 852 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 62 ms 820 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 469 ms 852 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 135 ms 724 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 141 ms 724 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 155 ms 724 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 139 ms 724 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 137 ms 724 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 140 ms 724 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 141 ms 724 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 140 ms 724 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 138 ms 724 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 136 ms 724 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Execution timed out 2068 ms 6300 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2083 ms 1300 KB Time limit exceeded
2 Halted 0 ms 0 KB -