Submission #1237362

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237362		Double_Slash	Boarding Passes (BOI22_passes)	C++20	100 / 100	487 ms	64440 KiB

passes

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()

int main() {
    string s;
    cin >> s;
    int n = s.size(), g = *max_element(all(s)) - 'A' + 1;
    ll ev[g][1 << g]{};
    auto c = [&] (int x) { return (ll) x * (x - 1) / 2; };
    for (int j = g; j--;) {
        vector<int> v;
        for (int i = 0; i < n; ++i) {
            if (s[i] - 'A' == j) v.emplace_back(i);
        }
        if (v.empty()) continue;
        struct : vector<int> {
            vector<ll> ps{0}, iw{0};

            void init() {
                for (int i = 0; i < size(); ++i) {
                    ps.emplace_back(ps.back() + (*this)[i]);
                    iw.emplace_back(iw.back() + (i + 1) * (*this)[i]);
                }
            }

            ll operator()(int l, int r) {
                return iw[r + 1] - iw[l] - l * (ps[r + 1] - ps[l]);
            }
        } l[g], r[g];
        for (int k = g; k--;) {
            l[k].resize(v.size() + 1);
            r[k].resize(v.size() + 1);
        }
        for (int i = n, idx = -1; i--;) {
            if (~idx) l[s[i] - 'A'][idx] += 1 + (s[i] - 'A' != j);
            if (s[i] - 'A' == j) ++idx;
        }
        for (int i = 0, idx = -1; i < n; ++i) {
            if (~idx) r[s[i] - 'A'][idx] += 1 + (s[i] - 'A' != j);
            if (s[i] - 'A' == j) ++idx;
        }
        for (int k = g; k--;) {
            l[k].init();
            r[k].init();
        }
        auto gl = [&] (int i, int m) {
            ll cur = 0;
            m |= 1 << j;
            for (int k = g; k--;) cur += ((m >> k) & 1) * l[k](v.size() - i, v.size() - 1);
            return cur;
        };
        auto gr = [&] (int i, int m) {
            ll cur = 0;
            m |= 1 << j;
            for (int k = g; k--;) cur += ((m >> k) & 1) * r[k](i, v.size() - 1);
            return cur;
        };
        for (int m = 1 << g; m--;) {
            if ((m >> j) & 1) continue;
            ev[j][m] = min(gr(0, m), gl(v.size(), m));
            if (v.size() == 1) continue;
            int i = 1;
            for (int k = 17; k--;) {
                if (i + (1 << k) + 1 >= v.size()) continue;
                i += 1 << k;
                if (gl(i + 1, m) + gr(i + 1, m) >= gl(i, m) + gr(i, m)) i -= 1 << k;
            }
            ev[j][m] = min(ev[j][m], gl(i, m) + gr(i, m));
            if (i + 1 < v.size()) ev[j][m] = min(ev[j][m], gl(i + 1, m) + gr(i + 1, m));
        }
    }
    ll dp[1 << g];
    memset(dp, 0x3f, sizeof dp);
    dp[0] = 0;
    for (int m = 0; m < (1 << g); ++m) {
        for (int i = g; i--;) {
            if ((m >> i) & 1) continue;
            dp[m | (1 << i)] = min(dp[m | (1 << i)], dp[m] + ev[i][m]);
        }
    }
    cout << dp[(1 << g) - 1] / 2;
    if (dp[(1 << g) - 1] & 1) cout << ".5";
}

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