oj.uz

Submission #858994

# Submission time Handle Problem Language Result Execution time Memory
858994 2023-10-09T14:13:36 Z vgtcross Boarding Passes (BOI22_passes) C++17
60 / 100
 1902 ms 1116 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 100100;
const int K = 10;

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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 348 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 20 ms 348 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 1481 ms 860 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 1778 ms 1116 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 1898 ms 1116 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 1902 ms 1116 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 2 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 5 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 2 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 3 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 3 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 2 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 2 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 344 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 348 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 2 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 2 ms 436 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 2 ms 344 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 2 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 5 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 2 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 3 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 3 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 2 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 2 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 344 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 348 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 2 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 2 ms 436 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 2 ms 344 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 2 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 5 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 3 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 3 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 1 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 3 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 2 ms 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 2 ms 412 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 2 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 2 ms 468 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 2 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 2 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 1 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 1 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 2 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 198 ms 504 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 189 ms 520 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 524 ms 516 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 187 ms 516 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 187 ms 348 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 212 ms 596 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 200 ms 344 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 201 ms 348 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 204 ms 516 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 201 ms 524 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 201 ms 520 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 208 ms 536 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 348 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 20 ms 348 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 1481 ms 860 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 1778 ms 1116 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 1898 ms 1116 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 1902 ms 1116 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 0 ms 344 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 2 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 5 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 2 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 3 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 1 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 3 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 1 ms 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 2 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 2 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 1 ms 344 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 1 ms 348 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 1 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 2 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 1 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 2 ms 436 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 2 ms 344 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 1 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 2 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 5 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 3 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 3 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 1 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 3 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 2 ms 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 2 ms 412 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 2 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 1 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 2 ms 468 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 2 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 2 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 1 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 1 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 2 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 198 ms 504 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 189 ms 520 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 524 ms 516 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 187 ms 516 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 187 ms 348 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 212 ms 596 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 200 ms 344 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 201 ms 348 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 204 ms 516 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 201 ms 524 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 201 ms 520 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 208 ms 536 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Incorrect 1 ms 348 KB 1st numbers differ - expected: '7.5000000000', found: '6.0000000000', error = '0.2000000000'
57 Halted 0 ms 0 KB -