oj.uz

Submission #860731

# Submission time Handle Problem Language Result Execution time Memory
860731 2023-10-14T04:35:47 Z E869120 Boarding Passes (BOI22_passes) C++14
60 / 100
 273 ms 13144 KB 
#include <bits/stdc++.h>
using namespace std;

// Input
long long G;
long long N, A[1 << 19];
string S;

// DP
long long Cost[1 << 10][10];
long long Left[1 << 19];
long long Rigt[1 << 19];
long long dp[1 << 19];

int main() {
    // Step 1. Input
    cin >> S;
    N = S.size();
    for (int i = 0; i < (int)S.size(); i++) {
        A[i] = (S[i] - 'A');
        G = max(G, A[i] + 1);
    }

    // Step 2. Precount
    for (int i = 0; i < (1 << G); i++) {
        for (int j = 0; j < G; j++) {
            if ((i >> j) & 1) continue;

            // Left Side
            int cur1 = 0;
            for (int k = 0; k < N; k++) {
                Left[k] = cur1;
                if (A[k] == j) cur1 += 1;
                if ((i >> A[k]) & 1) cur1 += 2;
            }

            // Rigt Side
            int cur2 = 0;
            for (int k = N - 1; k >= 0; k--) {
                Rigt[k] = cur2;
                if (A[k] == j) cur2 += 1;
                if ((i >> A[k]) & 1) cur2 += 2;
            }

            // Optimal 1
            long long Current = 0;
            for (int k = 0; k < N; k++) {
                if (A[k] == j) Current += Rigt[k];
            }
            Cost[i][j] = Current;
            for (int k = 0; k < N; k++) {
                if (A[k] == j) Current += (Left[k] - Rigt[k]);
                Cost[i][j] = min(Cost[i][j], Current);
            }
        }
    }

    // Step 3. DP
    for (int i = 0; i < (1 << G); i++) dp[i] = (1LL << 60);
    dp[0] = 0;
    for (int i = 0; i < (1 << G); i++) {
        for (int j = 0; j < G; j++) {
            if ((i >> j) & 1) continue;
            dp[i + (1 << j)] = min(dp[i + (1 << j)], dp[i] + Cost[i][j]);
        }
    }

    // Step 4. Output
    printf("%.12lf\n", 0.5 * dp[(1 << G) - 1]);
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 6492 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 6492 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 6492 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 6488 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 3 ms 12892 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 3 ms 12892 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 3 ms 13144 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 4 ms 12892 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 6492 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 6492 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 2 ms 6492 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 6492 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 6492 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 6492 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 6488 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 6492 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 6492 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 6492 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 6532 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 6492 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 6492 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 6492 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 6492 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 6492 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 6492 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 6492 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 6492 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 2 ms 6492 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 6492 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 6492 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 6492 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 6488 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 6492 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 6492 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 6492 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 6532 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 6492 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 6492 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 6492 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 6492 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 6492 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 6492 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 ms 6492 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 1 ms 6492 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 1 ms 6492 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 1 ms 6492 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 1 ms 6492 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 1 ms 6488 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 1 ms 6488 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 1 ms 6492 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 1 ms 6492 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 1 ms 6492 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 6492 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 1 ms 6492 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 1 ms 6492 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 1 ms 6492 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 1 ms 6492 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 1 ms 6492 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 1 ms 6492 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 46 ms 6492 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 39 ms 6612 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 273 ms 6608 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 203 ms 6492 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 191 ms 6612 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 195 ms 6492 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 194 ms 6612 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 196 ms 6612 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 198 ms 6748 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 197 ms 6612 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 194 ms 6616 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 198 ms 6492 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 6492 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 6492 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 6492 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 6488 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 3 ms 12892 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 3 ms 12892 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 3 ms 13144 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 4 ms 12892 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 1 ms 6492 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 1 ms 6492 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 2 ms 6492 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 1 ms 6492 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 1 ms 6492 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 1 ms 6492 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 1 ms 6488 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 1 ms 6492 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 1 ms 6492 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 1 ms 6492 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 1 ms 6532 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 1 ms 6492 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 1 ms 6492 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 1 ms 6492 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 1 ms 6492 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 1 ms 6492 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 1 ms 6492 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 1 ms 6492 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 1 ms 6492 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 1 ms 6492 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 1 ms 6492 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 1 ms 6492 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 1 ms 6488 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 1 ms 6488 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 1 ms 6492 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 1 ms 6492 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 1 ms 6492 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 1 ms 6492 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 1 ms 6492 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 1 ms 6492 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 1 ms 6492 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 1 ms 6492 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 1 ms 6492 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 1 ms 6492 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 46 ms 6492 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 39 ms 6612 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 273 ms 6608 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 203 ms 6492 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 191 ms 6612 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 195 ms 6492 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 194 ms 6612 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 196 ms 6612 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 198 ms 6748 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 197 ms 6612 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 194 ms 6616 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 198 ms 6492 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Incorrect 16 ms 11100 KB 1st numbers differ - expected: '7.5000000000', found: '2.0000000000', error = '0.7333333333'
57 Halted 0 ms 0 KB -