oj.uz

Submission #723161

# Submission time Handle Problem Language Result Execution time Memory
723161 2023-04-13T09:46:55 Z drdilyor Boarding Passes (BOI22_passes) C++17
55 / 100
 1298 ms 4124 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;
        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)
                    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 77 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 9 ms 352 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 10 ms 340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 9 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 10 ms 352 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 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 3 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 3 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 3 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 4 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 4 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 324 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 9 ms 352 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 10 ms 340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 9 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 10 ms 352 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 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 3 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 3 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 3 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 4 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 4 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 324 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 12 ms 344 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 12 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 3 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 8 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 3 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 3 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 3 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 3 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 3 ms 324 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 3 ms 320 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 1178 ms 3932 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 1161 ms 4124 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 1284 ms 4044 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 1114 ms 3964 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 1140 ms 4012 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 1182 ms 4000 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 1233 ms 3812 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 1217 ms 3916 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 1298 ms 3824 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 1202 ms 3880 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 1213 ms 3812 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 1241 ms 3812 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 77 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 -