Submission #917359

#	Time	Username	Problem	Language	Result	Execution time	Memory
917359		NK_	Boarding Passes (BOI22_passes)	C++17	100 / 100	234 ms	31052 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;
using ll = long long;
template<class T> using V = vector<T>;
using vi = V<int>;
using vl = V<ll>;

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];
	};


	V<V<vl>> F(G, V<vl>(G)), B(G, V<vl>(G));
	for(int x = 0; x < G; x++) for(int y = 0; y < G; y++) {
		F[x][y].assign(sz(oc[y]), 0);
		B[x][y].assign(sz(oc[y]), 0);

		for(int i = 0; i < sz(oc[y]); i++) {
			if (i - 1 >= 0) F[x][y][i] = F[x][y][i - 1];
			F[x][y][i] += qry(x, 0, oc[y][i] - 1);
		}

		for(int i = sz(oc[y]) - 1; i >= 0; i--) {
			if (i + 1 < sz(oc[y])) B[x][y][i] = B[x][y][i + 1];
			B[x][y][i] += qry(x, oc[y][i] + 1, N - 1);
		}

		// cout << x << " " << y << endl;
		// for(int i = 0; i < sz(oc[y]); i++) cout << i << " => " << F[x][y][i] << " " << B[x][y][i] << endl;
	}

	vl 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) {	

			ll cost = 1e10;
			auto comp = [&](int b) {
				b = min(sz(oc[g]), b);
				int f = b - 1; ll ans = 0;

				if (f > -1) ans += F[g][g][f];
				if (b < sz(oc[g])) ans += B[g][g][b];

				for(int i = 0; i < G; i++) if ((msk >> i) & 1) {
					if (f > -1) ans += 2 * F[i][g][f];
					if (b < sz(oc[g])) ans += 2 * B[i][g][b];
				}
				
				cost = min(ans, cost);

				return ans;
			};

			// cout << "G: " << g << " " << sz(oc[g]) << endl;
			int lo = 0, hi = sz(oc[g]); 
			while(lo < hi) {
				int mid = (lo + hi) / 2;
				if (comp(mid) < comp(mid + 1)) hi = mid - 1; 
				else lo = mid + 1;
			}

			comp(lo);

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

			int nmsk = msk | (1 << g);
			dp[nmsk] = min(cost + dp[msk], dp[nmsk]);
		}
	}

	cout << fixed << setprecision(10);
	cout << db(dp[(1 << G) - 1]) / db(2) << nl;

	exit(0-0);
}	

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