oj.uz

Submission #723185

# Submission time Handle Problem Language Result Execution time Memory
723185 2023-04-13T10:07:40 Z drdilyor Boarding Passes (BOI22_passes) C++17
60 / 100
 1701 ms 4060 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 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 / 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 116 ms 600 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 1 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 90 ms 664 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 2 ms 468 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 3 ms 468 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 3 ms 468 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 3 ms 468 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

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 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 10 ms 356 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 10 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 10 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 3 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 10 ms 348 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 4 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 304 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 5 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 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 4 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 4 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 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 10 ms 356 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 10 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 10 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 3 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 10 ms 348 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 4 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 304 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 5 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 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 4 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 4 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 352 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 15 ms 352 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 13 ms 356 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 13 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 10 ms 344 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 5 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 4 ms 324 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 5 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 5 ms 336 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 5 ms 212 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 296 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 4 ms 300 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 4 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 4 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 1439 ms 3924 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 1419 ms 3980 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 1701 ms 4060 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 1413 ms 3960 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 1265 ms 3924 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 1293 ms 3876 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 1340 ms 3872 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 1249 ms 3872 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 1337 ms 3960 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 1492 ms 3872 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 1370 ms 3856 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 1267 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 116 ms 600 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 1 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 90 ms 664 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 2 ms 468 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 3 ms 468 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 3 ms 468 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 3 ms 468 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 10 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 10 ms 356 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 10 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 10 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 3 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 10 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 4 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 4 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 4 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 3 ms 304 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 5 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 4 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 4 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 4 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 4 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 4 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 2 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 9 ms 352 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 15 ms 352 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 13 ms 356 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 13 ms 340 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 2 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 10 ms 344 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 5 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 4 ms 324 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 5 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 5 ms 336 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 5 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 4 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 4 ms 296 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 4 ms 300 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 4 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 4 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 1439 ms 3924 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 1419 ms 3980 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 1701 ms 4060 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 1413 ms 3960 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 1265 ms 3924 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 1293 ms 3876 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 1340 ms 3872 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 1249 ms 3872 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 1337 ms 3960 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 1492 ms 3872 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 1370 ms 3856 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 1267 ms 3812 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Incorrect 2 ms 212 KB 1st numbers differ - expected: '7.5000000000', found: '6.0000000000', error = '0.2000000000'
57 Halted 0 ms 0 KB -