oj.uz

Submission #860730

# Submission time Handle Problem Language Result Execution time Memory
860730 2023-10-14T04:35:11 Z E869120 Boarding Passes (BOI22_passes) C++14
0 / 100
 35 ms 12892 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 << N); i++) {
        for (int j = 0; j < N; 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 << N); i++) dp[i] = (1LL << 60);
    dp[0] = 0;
    for (int i = 0; i < (1 << N); i++) {
        for (int j = 0; j < N; 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 << N) - 1]);
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 35 ms 12884 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Runtime error 7 ms 12892 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Runtime error 7 ms 12892 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 35 ms 12884 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -