Submission #1079046

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079046		hcng	Boarding Passes (BOI22_passes)	C++14	100 / 100	567 ms	365908 KiB

passes

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

#define int long long
#define INF 0x3f3f3f3f3f3f3f3f

const int G = 15;
int n;
string s;
int psum[100010][G];
int pisum[100010][G][G], sisum[100010][G][G];
int dp[1 << G];
vector<int> pos[G];

int calc(int M, int p, int c) {
    int x = psum[M][c], y = psum[n][c];
    int r = x * (x - 1) / 2 + (y - x) * (y - x - 1) / 2;
    for (int i = 0; i < G; i++) {
        if (i == c) continue;
        if ((p >> i) & 1) {
            r += 2 * pisum[M][i][c];
            r += 2 * sisum[M + 1][c][i];
        }
    }
    return r;
}

bool calc2(int M, int p, int c) {
    int x = psum[M][c], y = psum[n][c];
    int r1 = x * (x - 1) / 2;
    int r2 = (y - x) * (y - x - 1) / 2;
    for (int i = 0; i < G; i++) {
        if (i == c) continue;
        if ((p >> i) & 1) {
            r1 += 2 * pisum[M][i][c];
            r2 += 2 * sisum[M + 1][c][i];
        }
    }
    return r1 < r2;
}


int tsearch(int p, int c) {
    int L = 0, R = pos[c].size() - 1;
    int mn = INF;
    while (L + 5 < R) {
        int M1 = L + (R - L) / 3, M2 = R - (R - L) / 3;
        int C1 = calc(pos[c][M1] - 1, p, c);
        int C2 = calc(pos[c][M2] - 1, p, c);
        if (C1 > C2) L = M1;
        else R = M2;
    }
    for (int i = L; i <= R; i++) {
        mn = min(mn, calc(pos[c][i] - 1, p, c));
    }
    return mn;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    cin >> s;
    n = s.size();
    s = ' ' + s;
    
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < G; j++) {
            psum[i][j] = psum[i - 1][j];
        }
        psum[i][s[i] - 'A']++;
        pos[s[i] - 'A'].push_back(i);
    }
    for (int i = 0; i < G; i++) {
        pos[i].push_back(n + 1);
    }
    
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < G; j++) {
            for (int k = 0; k < G; k++) {
                pisum[i][j][k] = pisum[i - 1][j][k];
            }
        }
        for (int j = 0; j < G; j++) {
            if (s[i] - 'A' == j) continue;
            pisum[i][j][s[i] - 'A'] += psum[i - 1][j];
        }
    }
    
    for (int i = n; i >= 1; i--) {
        for (int j = 0; j < G; j++) {
            for (int k = 0; k < G; k++) {
                sisum[i][j][k] = sisum[i + 1][j][k];
            }
        }
        for (int j = 0; j < G; j++) {
            if (s[i] - 'A' == j) continue;
            sisum[i][s[i] - 'A'][j] += psum[n][j] - psum[i][j];
        }
    }
    
    memset(dp, 0x3f, sizeof(dp));
    dp[0] = 0;
    for (int i = 1; i < (1 << G); i++) {
        for (int j = 0; j < G; j++) {
            if (!((i >> j) & 1)) continue;
            int p = i ^ (1 << j);
            dp[i] = min(dp[i], dp[p] + tsearch(p, j));
        }
    }
    
    printf("%.1lf\n", dp[(1 << G) - 1] / (double)2);
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 25 / 25
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40