oj.uz

Submission #723255

# Submission time Handle Problem Language Result Execution time Memory
723255 2023-04-13T12:45:56 Z drdilyor Boarding Passes (BOI22_passes) C++17
25 / 100
 2000 ms 3188 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;
    }

    auto suml = [&](int c1, int c2, int r) {
        ll res = 0, cur = 0;
        for (int i = 0; i <= r; i++) {
            if (s[i] == c1+a)
                res += cur;
            else if (s[i] == c2+a)
                cur++;
        }
        return res;
    };
    auto sumr = [&](int c1, int c2, int l) {
        ll res = 0, cur = 0;
        for (int i = n-1; i >= l;i --) {
            if (s[i] == c1+a)
                res += cur;
            else if (s[i] == c2+a)
                cur++;
        }
        return res;
    };

    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)
                    c++;
                else t += has[j];
                sum = 0;
                for (int c2 = 0; c2 < G; c2++)
                    if (used&1<<c2)
                        sum += suml(i, c2, 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];
                sum = 0;
                for (int c2 = 0; c2 < G; c2++)
                    if (used&1<<c2)
                        sum += sumr(i, c2, 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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2078 ms 660 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 293 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 369 ms 340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 286 ms 332 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 313 ms 340 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 11 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 262 ms 340 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 46 ms 300 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 41 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 41 ms 304 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 41 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 41 ms 304 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 41 ms 300 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 45 ms 296 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 44 ms 304 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 42 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 41 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 5 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 293 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 369 ms 340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 286 ms 332 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 313 ms 340 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 11 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 262 ms 340 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 46 ms 300 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 41 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 41 ms 304 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 41 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 41 ms 304 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 41 ms 300 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 45 ms 296 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 44 ms 304 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 42 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 41 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 5 ms 320 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 287 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 319 ms 340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 279 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 343 ms 332 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 10 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 232 ms 328 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 55 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 56 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 41 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 45 ms 308 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 41 ms 308 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 41 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 43 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 40 ms 416 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 54 ms 304 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 46 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Execution timed out 2061 ms 3188 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2078 ms 660 KB Time limit exceeded
2 Halted 0 ms 0 KB -