oj.uz

Submission #723159

# Submission time Handle Problem Language Result Execution time Memory
723159 2023-04-13T09:41:37 Z drdilyor Boarding Passes (BOI22_passes) C++17
25 / 100
 1322 ms 3936 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 = 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 + 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 Incorrect 81 ms 628 KB 1st numbers differ - expected: '100800.5000000000', found: '100800.0000000000', error = '0.0000049603'
2 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 11 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 11 ms 340 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 11 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 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 6 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 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 5 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 6 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
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 11 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 11 ms 340 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 11 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 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 6 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 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 5 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 6 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 2 ms 320 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 12 ms 352 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 12 ms 348 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 11 ms 340 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 2 ms 312 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 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 4 ms 324 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 5 ms 288 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 1322 ms 3924 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Incorrect 1167 ms 3936 KB 1st numbers differ - expected: '12495000.5000000000', found: '12495000.0000000000', error = '0.0000000400'
37 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 81 ms 628 KB 1st numbers differ - expected: '100800.5000000000', found: '100800.0000000000', error = '0.0000049603'
2 Halted 0 ms 0 KB -