Submission #1267056

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267056		MisterReaper	Boarding Passes (BOI22_passes)	C++20	60 / 100	2096 ms	41664 KiB

passes

// File A.cpp created on 04.09.2025 at 17:30:45
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

constexpr i64 inf = i64(1E18);

template<typename T>
bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::string S;
    std::cin >> S;

    int N = int(S.size());

    auto T = S;
    std::sort(T.begin(), T.end());
    T.erase(std::unique(T.begin(), T.end()), T.end());
    int n = int(T.size());

    std::vector<int> A(N);
    for (int i = 0; i < N; ++i) {
        A[i] = int(std::find(T.begin(), T.end(), S[i]) - T.begin());
    }

    debug(A);

    std::vector<std::vector<int>> ids(n);
    for (int i = 0; i < N; ++i) {
        ids[A[i]].emplace_back(i);
    }

    std::vector<std::vector<int>> pre(n, std::vector<int>(N + 1));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < N; ++j) {
            pre[i][j + 1] = pre[i][j] + (A[j] == i);
        }
    }

    std::vector<std::vector<std::vector<i64>>> costfr(n);
    for (int i = 0; i < n; ++i) {
        costfr[i].resize(n);
        for (int k = 0; k < n; ++k) {
            costfr[i][k].resize(ids[i].size() + 1);
            for (int j = 0; j < int(ids[i].size()); ++j) {
                costfr[i][k][j + 1] = costfr[i][k][j] + pre[k][ids[i][j] + 1];
            }
        }
    }

    std::vector<std::vector<int>> suf(n, std::vector<int>(N + 1));
    for (int i = 0; i < n; ++i) {
        for (int j = N - 1; j >= 0; --j) {
            suf[i][j] = suf[i][j + 1] + (A[j] == i);
        }
    }

    std::vector<std::vector<std::vector<i64>>> costbk(n);
    for (int i = 0; i < n; ++i) {
        costbk[i].resize(n);
        for (int k = 0; k < n; ++k) {
            costbk[i][k].resize(ids[i].size() + 1);
            for (int j = int(ids[i].size()) - 1; j >= 0; --j) {
                costbk[i][k][j] = costbk[i][k][j + 1] + suf[k][ids[i][j]];
            }
        }
    }

    std::vector<std::vector<i64>> save(1 << n, std::vector<i64>(n));
    auto cost = [&](int m, int i) -> i64 {
        i64 sum = inf;
        for (int k = 0; k <= int(ids[i].size()); ++k) {
            i64 now = 0;
            for (int j = 0; j < n; ++j) {
                if (m >> j & 1) {
                    now += costfr[i][j][k] + costbk[i][j][k];
                }
            }
            chmin(sum, 2 * now + 1LL * k * (k - 1) / 2 + 1LL * (int(ids[i].size()) - k) * (int(ids[i].size()) - k - 1) / 2);
        }
        return sum;
    };

    for (int m = 0; m < (1 << n); ++m) {
        for (int j = 0; j < n; ++j) {
            if (m >> j & 1) {
                continue;
            } 
            save[m][j] = cost(m, j);
        }
    }

    std::vector<i64> f(1 << n);
    for (int m = 1; m < (1 << n); ++m) {
        f[m] = inf;
        for (int i = 0; i < n; ++i) {
            if (~m >> i & 1) {
                continue;
            }
            chmin(f[m], f[m ^ (1 << i)] + save[m ^ (1 << i)][i]);
        }
    }

    i64 ans = f[(1 << n) - 1];

    std::cout << ans / 2 << '.' << (ans % 2 ? 5 : 0) << '\n';

    return 0;
}

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