제출 #860731

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
860731		E869120	Boarding Passes (BOI22_passes)	C++14	60 / 100	273 ms	13144 KiB

passes

#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 / 5
• Subtask 2: 25 / 25
• Subtask 3: 30 / 30
• Subtask 4: 0 / 40