Submission #725413

#	Time	Username	Problem	Language	Result	Execution time	Memory
725413		dxz05	Boarding Passes (BOI22_passes)	C++17	100 / 100	391 ms	23416 KiB

passes

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define all(x) (x).begin(), (x).end()
#define MP make_pair
const int N = 100500;

long long exp_inv(ll n){
    return (long long) n * (n - 1); // should be divided by 4
}

ll dp[1 << 15];
vector<ll> pref[16][16];
vector<ll> suff[16][16];

void solve(){
    string str;
    cin >> str;
    int n = (int)str.size();

    vector<vector<int>> pos;
    map<char, int> id;

    for (int i = 0; i < n; i++){
        if (id.find(str[i]) == id.end()){
            id[str[i]] = (int) id.size();
            pos.emplace_back();
        }
        pos[id[str[i]]].push_back(i);
    }

    int G = (int) pos.size();

    for (int x = 0; x < G; x++){
        int sz_x = (int) pos[x].size();

        for (int y = 0; y < G; y++){
            if (x == y) continue;
            int sz_y = (int) pos[y].size();

            vector<ll> &p = pref[x][y], &s = suff[x][y];

            p.resize(sz_x);
            s.resize(sz_x);

            int j = 0;
            for (int i = 0; i < sz_x; i++){
                while (j < sz_y && pos[y][j] <= pos[x][i]) j++;
                p[i] = j;
            }

            j = sz_y - 1;
            for (int i = sz_x - 1; i >= 0; i--){
                while (j >= 0 && pos[y][j] >= pos[x][i]) j--;
                s[i] = sz_y - j - 1;
            }

            for (int i = 1; i < sz_x; i++) p[i] += p[i - 1];
            for (int i = sz_x - 2; i >= 0; i--) s[i] += s[i + 1];

        }
    }

    function<long long(int, int, int)> cost = [&](int mask, int c, int wall){
        int sz = (int) pos[c].size();

        long long res = 0;
        for (int d = 0; d < G; d++){
            if (!(mask & (1 << d))) continue;

            if (wall > 0) res += pref[c][d][wall - 1];
            if (wall < sz) res += suff[c][d][wall];
        }

        res *= 4;
        res += exp_inv(wall) + exp_inv(sz - wall);

        return res;
    };

    fill(dp, dp + (1 << G), 5e18);

    dp[0] = 0;

    for (int mask = 0; mask < (1 << G); mask++){
        if (dp[mask] >= 1e18) continue;

        for (int c = 0; c < G; c++){
            if (mask & (1 << c)) continue;

            int sz = (int) pos[c].size();

            long long mn = 5e18;

            int l = 0, r = sz;
            while (r - l >= 3){
                int m1 = (2 * l + r) / 3, m2 = (l + 2 * r) / 3;
                ll f1 = cost(mask, c, m1), f2 = cost(mask, c, m2);

                mn = min({mn, f1, f2});
                if (f1 < f2){
                    r = m2;
                } else {
                    l = m1;
                }
            }

            for (int i = l; i <= r; i++) mn = min(mn, cost(mask, c, i));

            int new_mask = mask | (1 << c);
            dp[new_mask] = min(dp[new_mask], dp[mask] + mn);
        }

    }

    cout << dp[(1 << G) - 1] / 4;

    if (dp[(1 << G) - 1] % 4 != 0) cout << ".5";

    cout << endl;

}

int main() {
    ios_base::sync_with_stdio(false);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    solve();

    return 0;
}

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