제출 #917356

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
917356		NK_	Boarding Passes (BOI22_passes)	C++17	25 / 100	2086 ms	6180 KiB

passes

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())

using str = string;
using db = long double;
template<class T> using V = vector<T>;
using vi = V<int>;
using vd = V<db>;

const db EPS = 1e-14;
const int G = 15;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	str S; cin >> S;
	int N = sz(S);
 
	V<vi> P(G, {0}); V<vi> oc(G);
	for(int i = 0; i < N; i++) {
		int c = S[i] - 'A'; oc[c].pb(i);
		for(int g = 0; g < G; g++) P[g].pb(P[g].back() + (g == c));
	}

	auto qry = [&](int g, int l, int r) {
		return P[g][r + 1] - P[g][l];
	};

	auto EXP = [&](int N) { return db(N) / db(2); };

	cout << fixed << setprecision(10);

	V<db> dp(1 << G, 1e10);
	dp[0] = 0;

	for(int msk = 0; msk < (1 << G); msk++) {
		// cout << msk << " => " << dp[msk] << endl;
		for(int g = 0; g < G; g++) if (((msk >> g) & 1) ^ 1) {
			db all = dp[msk];

			for(auto& x : oc[g]) {
				db F = EXP(qry(g, 0, x - 1)), B = EXP(qry(g, x + 1, N - 1));

				for(int c = 0; c < G; c++) if ((msk >> c) & 1) {
					F += qry(c, 0, x), B += qry(c, x, N - 1);
				}
				// cout << x << " ======> " << F << " " << B << endl;

				all += min(F, B);
			}

			// cout << g << " ===> " << all << endl;

			int nmsk = msk | (1 << g);
			if (dp[nmsk] > all + EPS) dp[nmsk] = all;
		}
	}

	cout << dp[(1 << G) - 1] << nl;

	exit(0-0);
}

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