Submission #725430

#	Time	Username	Problem	Language	Result	Execution time	Memory
725430		dxz05	Boarding Passes (BOI22_passes)	C++17	100 / 100	266 ms	23312 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];

        }
    }

    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;

            function<long long(int)> cost = [&](int wall){
                int sz = (int) pos[c].size();
                if (wall > sz) return (ll)1e9;

                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;
            };

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

            int l = 0, r = sz;
            while (l <= r){
                int m = (l + r) >> 1;
                if (cost(m) > cost(m + 1)){
                    l = m + 1;
                } else {
                    r = m - 1;
                }
            }

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

    }

    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