Submission #582107

#	Time	Username	Problem	Language	Result	Execution time	Memory
582107		KoD	Boarding Passes (BOI22_passes)	C++17	100 / 100	205 ms	18880 KiB

passes

#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

using ll = long long;

template <class F> struct fixed : private F {
    explicit fixed(F&& f) : F(std::forward<F>(f)) {}
    template <class... Args> decltype(auto) operator()(Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};

template <class T>
constexpr T infty = std::numeric_limits<T>::max() / 2;

template <class T>
void setmin(T& x, const T& y) {
    if (x > y) {
        x = y;
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::string S;
    std::cin >> S;
    const int N = (int)S.size();
    const int G = 15;
    array<vector<int>, G> pos = {};
    for (int i = 0; i < N; ++i) {
        pos[S[i] - 'A'].push_back(i);
    }
    array<vector<int>, G> accum = {};
    accum.fill(vector(N + 1, 0));
    for (int i = 0; i < N; ++i) {
        for (int k = 0; k < G; ++k) {
            accum[k][i + 1] = accum[k][i];
        }
        accum[S[i] - 'A'][i + 1] += 1;
    }
    array<array<vector<ll>, G>, G> precalc = {};
    for (int i = 0; i < G; ++i) {
        for (int j = 0; j < G; ++j) {
            const int n = (int)pos[i].size();
            precalc[i][j].resize(n + 1);
            for (const int x : pos[i]) {
                precalc[i][j][0] += accum[j][N] - accum[j][x];
            }
            for (int k = 0; k < n; ++k) {
                const int x = pos[i][k];
                ll next = precalc[i][j][k];
                next -= accum[j][N] - accum[j][x];
                next += accum[j][x];
                precalc[i][j][k + 1] = next;
            }
        }
    }
    vector<ll> dp(1 << G, infty<ll>);
    dp[0] = 0;
    for (int set = 0; set < (1 << G); ++set) {
        for (int add = 0; add < G; ++add) {
            if (set >> add & 1) {
                continue;
            }
            const int n = pos[add].size();
            const auto calc = [&](const int k) {
                ll ret = 0;
                for (int i = 0; i < G; ++i) {
                    if (set >> i & 1) {
                        ret += precalc[add][i][k];
                    }
                }
                return ret * 2 + (ll)k * (k - 1) / 2 + (ll)(n - k) * (n - k - 1) / 2;
            };
            int l = -1, r = n + 1;
            while (r - l > 2) {
                const int m = (l + r) / 2;
                if (calc(m) > calc(m + 1)) {
                    l = m;
                } else {
                    r = m + 1;
                }
            }
            setmin(dp[set | (1 << add)], dp[set] + calc(l + 1));
        }
    }
    const ll ans = dp[(1 << G) - 1];
    std::cout << ans / 2;
    if (ans % 2 == 1) {
        std::cout << ".5";
    }
    std::cout << '\n';
    return 0;
}

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