Submission #859035

#	Time	Username	Problem	Language	Result	Execution time	Memory
859035		vgtcross	Boarding Passes (BOI22_passes)	C++17	100 / 100	301 ms	365928 KiB

passes

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 100100;
const int K = 15;

ll p[N][K];
ll q[N][K][K];
ll s[N][K][K];
ll dp[1 << K];
vector<int> pos[K];

void solve() {
    string str;
    cin >> str;
    
    int n = str.size();
    
    vector<int> v(n);
    for (int i = 0; i < n; ++i) {
        v[i] = str[i] - 'A';
        pos[v[i]].push_back(i);
    }
    for (int k = 0; k < K; ++k) pos[k].push_back(n);
    
    for (int i = 0; i < n; ++i) {
        for (int k = 0; k < K; ++k) p[i+1][k] = p[i][k] + (v[i] == k);
        for (int k = 0; k < K; ++k) {
            for (int l = 0; l < K; ++l) q[i+1][k][l] = q[i][k][l] + (v[i] == k) * p[i+1][l];
        }
    }
    for (int i = n-1; i >= 0; --i) {
        for (int k = 0; k < K; ++k) {
            for (int l = 0; l < K; ++l) s[i][k][l] = s[i+1][k][l] + (v[i] == k) * (p[n][l] - p[i][l]);
        }
    }
    
    memset(dp, 0x3f, sizeof dp);
    dp[0] = 0;
    for (int j = 1; j < (1 << K); ++j) {
        for (int i = 0; i < K; ++i) if (j >> i & 1) {
            int a = -1, d = pos[i].size();
            ll ans = 1e18;
            while (d-a > 2) {
                int b = a + (d-a)/3;
                int c = a + 2*(d-a)/3;
                int x = pos[i][b];
                int y = pos[i][c];
                ll ansb = p[x][i]*(p[x][i]-1)/2 + (p[n][i]-p[x][i])*(p[n][i]-p[x][i]-1)/2;
                ll ansc = p[y][i]*(p[y][i]-1)/2 + (p[n][i]-p[y][i])*(p[n][i]-p[y][i]-1)/2;
                for (int k = 0; k < K; ++k) if (i != k && (j >> k & 1)) {
                    ansb += 2*q[x][i][k] + 2*s[x][i][k];
                    ansc += 2*q[y][i][k] + 2*s[y][i][k];
                }
                if (ansb < ansc) {
                    ans = min(ans, ansb);
                    d = c;
                } else {
                    ans = min(ans, ansc);
                    a = b;
                }
            }
            dp[j] = min(dp[j], dp[j ^ (1 << i)] + (p[n][i] > 0) * ans);
        }
    }
    
    cout << (long double) dp[(1 << K) - 1] / 2.0 << '\n';
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    
    cout << fixed << setprecision(6);
    
    solve();
}

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