oj.uz

Submission #723160

# Submission time Handle Problem Language Result Execution time Memory
723160 2023-04-13T09:44:20 Z drdilyor Boarding Passes (BOI22_passes) C++17
55 / 100
 1434 ms 4160 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();
    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 * 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];
                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 = 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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 596 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Incorrect 1 ms 212 KB 1st numbers differ - expected: '0.0000000000', found: '250000000000000000.0000000000', error = '250000000000000000.0000000000'
3 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 10 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 12 ms 344 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 10 ms 344 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 10 ms 340 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 10 ms 340 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 4 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 3 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 4 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 4 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 4 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 4 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 3 ms 340 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 3 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 3 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 3 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 10 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 12 ms 344 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 10 ms 344 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 10 ms 340 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 10 ms 340 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 4 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 3 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 4 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 4 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 4 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 4 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 3 ms 340 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 3 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 3 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 3 ms 212 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 10 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 11 ms 340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 10 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 10 ms 340 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 2 ms 320 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 9 ms 344 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 3 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 4 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 3 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 4 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 5 ms 328 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 4 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 4 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 3 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 3 ms 324 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 3 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 1181 ms 3924 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 1189 ms 3960 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 1434 ms 3924 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 1233 ms 3936 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 1186 ms 4008 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 1182 ms 3832 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 1273 ms 3864 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 1234 ms 4160 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 1262 ms 3880 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 1271 ms 3836 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 1247 ms 3812 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 1211 ms 3820 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 596 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Incorrect 1 ms 212 KB 1st numbers differ - expected: '0.0000000000', found: '250000000000000000.0000000000', error = '250000000000000000.0000000000'
3 Halted 0 ms 0 KB -