Submission #860732

#	Time	Username	Problem	Language	Result	Execution time	Memory
860732		E869120	Boarding Passes (BOI22_passes)	C++14	100 / 100	1910 ms	506676 KiB

passes

#include <bits/stdc++.h>
using namespace std;

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

// DP
long long Cost[1 << 17][17];
long long sum1L[17][1 << 17];
long long sum1R[17][1 << 17];
long long sum2L[17][17][1 << 17];
long long sum2R[17][17][1 << 17];
long long dp[1 << 17];

long long GetLeft(int mask, int grp, int pos) {
    if (pos == 0) return 0;
    long long sum = 0;
    for (int i = 0; i < G; i++) {
        if (((mask >> i) & 1) == 0) continue;
        sum += 2LL * sum1L[i][pos - 1];
    }
    sum += 1LL * sum1L[grp][pos - 1];
    return sum;
}

long long GetRigt(int mask, int grp, int pos) {
    if (pos == 0) return 0;
    long long sum = 0;
    for (int i = 0; i < G; i++) {
        if (((mask >> i) & 1) == 0) continue;
        sum += 2LL * sum1R[i][pos + 1];
    }
    sum += 1LL * sum1R[grp][pos + 1];
    return sum;
}

long long GetLeftSum(int mask, int grp, int pos) {
    long long ret = 0;
    for (int i = 0; i < G; i++) {
        if (((mask >> i) & 1) == 0) continue;
        ret += sum2L[grp][i][pos];
    }
    ret += sum2L[grp][grp][pos];
    return ret;
}

long long GetRigtSum(int mask, int grp, int pos) {
    long long ret = 0;
    for (int i = 0; i < G; i++) {
        if (((mask >> i) & 1) == 0) continue;
        ret += sum2R[grp][i][pos];
    }
    ret += sum2R[grp][grp][pos];
    return ret;
}

long long GetCost(int mask, int grp) {
    // Step A. Binary Search
    int cl = 0, cr = N, cm;
    for (int i = 0; i < 20; i++) {
        cm = (cl + cr) / 2;
        long long v1 = GetLeft(mask, grp, cm);
        long long v2 = GetRigt(mask, grp, cm);
        if (v1 < v2) { cl = cm; }
        else { cr = cm; }
    }

    // Step B. Brute Force
    long long Return = (1LL << 60);
    for (int i = cm - 1; i <= cm + 1; i++) {
        if (i < 0 || i >= N - 1) continue;
        long long val1 = GetLeftSum(mask, grp, i);
        long long val2 = GetRigtSum(mask, grp, i + 1);
        Return = min(Return, val1 + val2);
    }
    return Return;
}

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);
    }
    if (N <= 2) {
        cout << 0 << endl;
        return 0;
    }

    // Step 2. Precount 1
    for (int i = 0; i < N; i++) {
        sum1L[A[i]][i] += 1;
        sum1R[A[i]][i] += 1;
    }
    for (int i = 0; i < G; i++) {
        for (int j = 1; j <= N - 1; j++) sum1L[i][j] += sum1L[i][j - 1];
        for (int j = N - 2; j >= 0; j--) sum1R[i][j] += sum1R[i][j + 1];
    }

    // Step 3. Precount 2
    for (int i = 0; i < G; i++) {
        for (int j = 0; j < G; j++) {
            long long cur1 = 0;
            long long sum1 = 0;
            for (int k = 0; k < N; k++) {
                if (A[k] == i) sum1 += cur1;
                sum2L[i][j][k] = sum1;
                if (A[k] == j && i == j) cur1 += 1;
                if (A[k] == j && i != j) cur1 += 2;
            }
            long long cur2 = 0;
            long long sum2 = 0;
            for (int k = N - 1; k >= 0; k--) {
                if (A[k] == i) sum2 += cur2;
                sum2R[i][j][k] = sum2;
                if (A[k] == j && i == j) cur2 += 1;
                if (A[k] == j && i != j) cur2 += 2;
            }
        }
    }

    // Step 4. Precount 3
    for (int i = 0; i < (1 << G); i++) {
        for (int j = 0; j < G; j++) {
            if ((i >> j) & 1) continue;
            Cost[i][j] = GetCost(i, j);
        }
    }
    /*for (int i = 0; i < (1 << G); i++) {
        for (int j = 0; j < G; j++) printf("% 4lld", Cost[i][j]);
        printf("\n");
    }*/

    // Step 5. 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 6. 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: 40 / 40