Submission #582960

#	Time	Username	Problem	Language	Result	Execution time	Memory
582960		Cyanmond	Boarding Passes (BOI22_passes)	C++17	55 / 100	638 ms	2380 KiB

passes

#include <algorithm>
#include <cassert>
#include <iostream>
#include <limits>
#include <string>
#include <vector>

using namespace std;

using i64 = long long int;
constexpr i64 inf64 = numeric_limits<i64>::max() / 3;

#define ALL(x) (x).begin(), (x).end()
#define REP_3(i, l, r) for (int i = (l); i < (r); ++i)
#define RVP_3(i, l, r) for (int i = (r - 1); i >= (l); --i)
#define REP(i, N) REP_3(i, 0, N)
#define RVP(i, N) RVP_3(i, 0, N)

void answer(const i64 x) {
    cout << x / 2;
    if (x % 2 == 1) cout << ".5" << endl;
}

template <typename T> void chmin(T &a, const T b) {
    if (a > b) a = b;
}

int main() {
    string s;
    cin >> s;
    vector<int> S;
    for (const int e : s) S.push_back(e - 'A');
    const int N = (int)S.size();
    const int G = *max_element(ALL(S)) + 1;
    vector<i64> dp(1 << G, inf64);
    dp[0] = 0;

    auto calc_score = [](vector<int> v) {
        assert(all_of(ALL(v), [](int e) { return 0 <= e and e <= 2; }));
        const int n = (int)v.size();
        vector<int> l_sum(n + 1), r_sum(n + 1);
        REP(i, n) l_sum[i + 1] = l_sum[i] + v[i];
        RVP(i, n) r_sum[i] = r_sum[i + 1] + v[i];
        i64 ret = 0;
        REP(i, n) if (v[i] == 1) ret += min(l_sum[i], r_sum[i + 1]);
        return ret;
    };

    REP(bit, 1 << G) {
        REP(x, G) {
            if (bit & (1 << x)) continue;
            vector<int> v(N);
            REP(i, N) {
                if (bit & (1 << S[i])) {
                    v[i] = 2;
                } else if (S[i] == x) {
                    v[i] = 1;
                }
            }
            const int cost = calc_score(v);
            chmin(dp[bit | (1 << x)], dp[bit] + cost);
        }
    }
    answer(dp[(1 << G) - 1]);
}

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