Submission #853274

#	Time	Username	Problem	Language	Result	Execution time	Memory
853274		MinaRagy06	Boarding Passes (BOI22_passes)	C++17	100 / 100	168 ms	19816 KiB

passes

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

vector<ll> val[16][16];
vector<int> idx[16];
int prfx[16][100'005];
double dp[1 << 16];
int sum(int g, int l, int r) {
    return prfx[g][r + 1] - prfx[g][l];
}
int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cout << fixed << setprecision(3);
    string in;
    cin >> in;
    int n = in.size();
    set<int> chars;
    for (auto i : in) {
        chars.insert(i);
    }
    int mp[255]{}, ctr = 0;
    for (auto i : chars) {
        mp[i] = ctr++;
    }
    int m = chars.size();
    int a[n];
    for (int i = 0; i < n; i++) {
        a[i] = mp[(int)in[i]];
    }
    for (int i = 0; i < n; i++) {
        idx[a[i]].push_back(i);
        for (int j = 0; j < m; j++) {
            prfx[j][i + 1] = prfx[j][i];
        }
        prfx[a[i]][i + 1]++;
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < m; j++) {
            vector<int> cur = idx[j];
            val[i][j].resize(cur.size() + 1);
            reverse(cur.begin(), cur.end());
            val[i][j][0] = 0;
            for (auto l : cur) {
                val[i][j][0] += sum(i, l, n - 1);
            }
            for (int k = 1; k <= (int) idx[j].size(); k++) {
                val[i][j][k] = val[i][j][k - 1];
                val[i][j][k] -= sum(i, cur.back(), n - 1);
                val[i][j][k] += sum(i, 0, cur.back());
                cur.pop_back();
            }
        }
    }
    dp[(1 << m) - 1] = 0;
    for (int msk = (1 << m) - 2; msk >= 0; msk--) {
        vector<int> bits[2];
        for (int i = 0; i < m; i++) {
            bits[(msk >> i) & 1].push_back(i);
        }
        dp[msk] = 1e10;
        for (auto i : bits[0]) {
            auto calc = [&] (int s) {
                double cur = 0;
                for (auto j : bits[1]) {
                    cur += val[j][i][s];
                }
                ll ttl = idx[i].size();
                cur += 1ll * s * (s - 1) / 4.0 + 1ll * (ttl - s) * (ttl - s - 1) / 4.0;
                return cur;
            };
            double mn = 1e10;
            int l = 0, r = idx[i].size();
            while (r - l > 3) {
                int md1 = l + (r - l) / 3, md2 = r - (r - l) / 3;
                if (calc(md1) <= calc(md2)) {
                    r = md2;
                } else {
                    l = md1;
                }
            }
            for (int s = l; s <= r; s++) {
                mn = min(mn, calc(s));
            }
            dp[msk] = min(dp[msk], mn + dp[msk | (1 << i)]);
        }
    }
    cout << dp[0] << '\n';
    return 0;
}

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