Submission #1121627

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121627		vjudge1	Boarding Passes (BOI22_passes)	C++17	100 / 100	1075 ms	411988 KiB

passes

#include <bits/stdc++.h>
using namespace std;
int n, g;
string s;
long double get(long double x) {
    return x * (x-1)/4;
}

long double pref[100100];
long double suf[100100];
long double dp[1<<16];
vector<int> pos[1111];
long double C[100100][16][16];
int cnt[100100][16];
long double get(int mask, int d, int x) {
    long double ans = 0;
    for(int i = 0; i < g; i++) {
        if(mask & (1<<i)) {
            ans += C[d][x][i];
        }
    }
    long double cc = cnt[d][x];
    long double ALL = cnt[n][x];

    return ans + get(cc) + get(ALL-cc);
}
long double calc(int mask, int x) {
    if(pos[x].size() == 1) return 0;
    int l = 0, r = pos[x].size() - 1;
    while(l + 3 < r) {
        int mid = (l + r)/2;
        if(get(mask, pos[x][mid], x) < get(mask, pos[x][mid+1], x)) {
            r = mid;
        } else {
            l = mid;
        }
    }
    long double ans = 1e18;
    for(int i = l; i <= r; i++) {
        ans = min(ans, get(mask, pos[x][i], x));
    }
    return ans;
}
void precalc(int x, int y) {
    int A = 0;
    int X = 0;
    for(int i = 0; i < n; i++) {
        pref[i+1] = pref[i];
        if(s[i] == 'A' + x) {
            pref[i+1] += A;
            X++;
        } else if(s[i] == 'A'+y) {
            A++;
        }
    }
    X = 0;
    A = 0;
    for(int i = n-1; i >= 0; i--) {
        suf[i] = suf[i+1];
        if(s[i] == 'A' + x) {
            suf[i] += A;
            X++;
        } else if(s[i]  == 'A' + y){
            A++;
        }
    }
    for(int i = 0; i <= n; i++) {
        C[i][x][y] = pref[i] + suf[i];
    }
}
int main() {
    cin >> s;
    n = s.size();
    for(int i = 0; i < 16; i++) {
        pos[i].push_back(0);
    }
    for(int i = 0; i < n; i++) {
        g = max(s[i] - 'A' + 1, g);
        pos[s[i] - 'A'].push_back(i + 1);
    }
    for(int c = 0; c < g; c++) {
        for(int i = 1; i <= n; i++) {
            cnt[i][c] = cnt[i-1][c] + (s[i-1] - 'A' == c);
        }
    }
    for(int i = 0; i < g; i++) {
        for(int j = 0; j < g; j++) {
            if(i == j) continue;
            precalc(i, j);
        }
    }
    for(int i = 0; i < (1<<g); i++) {
        dp[i] = 1e18;
    }
    dp[0] = 0;


    for(int mask = 0; mask < (1<<g); mask++) {
        for(int i = 0; i < g; i++) {
            int  nmask = mask | (1<<i);
            if(nmask != mask) {
                dp[nmask] = min(dp[mask] + calc(mask, i), dp[nmask]);
            }
        }
    }
    cout << fixed << setprecision(12) << dp[(1<<g)-1] << "\n";
}

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