oj.uz

Submission #723180

# Submission time Handle Problem Language Result Execution time Memory
723180 2023-04-13T10:04:42 Z drdilyor Boarding Passes (BOI22_passes) C++17
55 / 100
 1342 ms 4128 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;
    if (n > 10000) ans = exp_inv(n);
    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
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 9 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 10 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 11 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 10 ms 356 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 2 ms 296 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 11 ms 340 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 5 ms 300 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 5 ms 296 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 5 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 4 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 3 ms 300 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 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 9 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 10 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 11 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 10 ms 356 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 2 ms 296 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 11 ms 340 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 5 ms 300 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 5 ms 296 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 5 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 4 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 3 ms 300 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 212 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 9 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 10 ms 340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 9 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 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 9 ms 340 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 4 ms 276 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 3 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 4 ms 300 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 4 ms 340 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 332 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 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 3 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 3 ms 296 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 1165 ms 3932 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 1113 ms 3992 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 1342 ms 3924 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 1142 ms 4004 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 1140 ms 3928 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 1163 ms 3952 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 1161 ms 3868 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 1143 ms 4124 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 1139 ms 4128 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 1149 ms 3812 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 1161 ms 3880 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 1219 ms 3924 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 -