oj.uz

Submission #858990

# Submission time Handle Problem Language Result Execution time Memory
858990 2023-10-09T14:09:57 Z vgtcross Boarding Passes (BOI22_passes) C++17
25 / 100
 2000 ms 3164 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 100100;
const int K = 15;

ll p[N][K];
ll dp[1 << K];

void solve() {
    string s;
    cin >> s;
    
    int n = s.size();
    
    vector<int> v(n);
    for (int i = 0; i < n; ++i) v[i] = s[i] - 'A';
    
    memset(dp, 0x3f, sizeof dp);
    dp[0] = 0;
    for (int j = 1; j < (1 << K); ++j) {
        for (int i = 0; i < K; ++i) if (j >> i & 1) {
            ll l[2]{}, r[2]{}, t = 0;
            for (int k : v) {
                r[0] += k == i;
                if (i != k && (j >> k & 1)) {
                    ++r[1];
                    t += r[0];
                }
            }
            
            dp[j] = min(dp[j], dp[j ^ (1 << i)] + r[0]*(r[0]-1)/2 + 2*t);
            for (int k : v) {
                l[0] += k == i;
                r[0] -= k == i;
                l[1] += i != k && (j >> k & 1);
                r[1] -= i != k && (j >> k & 1);
                if (k == i) {
                    t -= r[1];
                    t += l[1];
                }
                
                dp[j] = min(dp[j], dp[j ^ (1 << i)] + l[0]*(l[0]-1)/2 + r[0]*(r[0]-1)/2 + 2*t);
            }
            //cout << bitset<3>(j) << ' ' << bitset<3>(1 << i) << ": " << dp[j] << '\n';
        }
    }
    
    cout << (long double) dp[(1 << K) - 1] / 2.0 << '\n';
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    
    cout << fixed << setprecision(6);
    
    solve();
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 834 ms 2672 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 3 ms 2648 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 6 ms 2652 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 9 ms 2696 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 964 ms 2676 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Execution timed out 2015 ms 3164 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2692 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 99 ms 2672 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 188 ms 2672 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 107 ms 2668 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 108 ms 2672 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 22 ms 2652 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 126 ms 2676 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 40 ms 2652 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 69 ms 2652 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 50 ms 2652 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 47 ms 2652 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 50 ms 2652 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 55 ms 2896 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 59 ms 2652 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 63 ms 2652 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 46 ms 2648 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 49 ms 2648 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2692 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 99 ms 2672 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 188 ms 2672 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 107 ms 2668 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 108 ms 2672 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 22 ms 2652 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 126 ms 2676 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 40 ms 2652 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 69 ms 2652 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 50 ms 2652 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 47 ms 2652 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 50 ms 2652 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 55 ms 2896 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 59 ms 2652 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 63 ms 2652 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 46 ms 2648 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 49 ms 2648 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 8 ms 2908 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 97 ms 2652 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 185 ms 2652 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 116 ms 2648 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 105 ms 2672 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 22 ms 2648 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 115 ms 2904 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 39 ms 2652 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 60 ms 2672 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 50 ms 2672 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 47 ms 2652 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 49 ms 2648 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 51 ms 2896 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 55 ms 2648 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 47 ms 2652 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 46 ms 2648 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 49 ms 2648 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Execution timed out 2017 ms 2648 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 834 ms 2672 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 3 ms 2648 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 6 ms 2652 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 9 ms 2696 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 964 ms 2676 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Execution timed out 2015 ms 3164 KB Time limit exceeded
7 Halted 0 ms 0 KB -