Submission #868028

#	Time	Username	Problem	Language	Result	Execution time	Memory
868028		TAhmed33	Boarding Passes (BOI22_passes)	C++98	60 / 100	2035 ms	21844 KiB

passes

#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
string s; int n;
vector <int> pos[26];
int val[100001][26];
int val2[100001][26];
ld dp[(1 << 15)];
vector <int> dd;
int cnt;
ld ans (int mask) {
	ld &ret = dp[mask];
	if (ret == ret) return ret;
	ret = 1e18;
	if (mask == (1 << cnt) - 1) return ret = 0;
	for (int i = 0; i < cnt; i++) {
		if (mask & (1 << i)) continue;
		int m = pos[dd[i]].size();
		ld sum = 0;
		for (int j = 0; j < m; j++) {
			int ret1 = 0, ret2 = 0;
			for (int k = 0; k < cnt; k++) {
				if (mask & (1 << k)) {
					ret1 += val[pos[dd[i]][j]][dd[k]];
					ret2 += val2[pos[dd[i]][j]][dd[k]];
				}
			}
			sum += min(ret1 + j * 0.5, ret2 + (m - j - 1) * 0.5);
		}
		ret = min(ret, sum + ans(mask ^ (1 << i)));
	}
	return ret;
}
int main () {
	memset(dp, -1, sizeof(dp));
	cin >> s; n = s.length();
	for (int i = 0; i < n; i++) {
		pos[s[i] - 'A'].push_back(i);
	}
	int x = 0;
	for (int i = 1; i < 26; i++) if (!pos[i].empty()) x = i;
	for (int i = 0; i <= x; i++) if (!pos[i].empty()) dd.push_back(i);
	cnt = dd.size();
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 26; j++) {
			if (pos[j].empty()) continue;
			if (s[i] - 'A' == j) continue;
			int l = 0, r = (int)pos[j].size() - 1, ans = 0;
			while (l <= r) {
				int m = (l + r) >> 1;
				if (pos[j][m] < i) {
					l = m + 1; ans = m + 1; 
				} else {
					r = m - 1;
				}
			}
			val[i][j] = ans; val2[i][j] = (int)pos[j].size() - ans;
		}
	}
	cout << fixed << setprecision(6) << ans(0) << '\n';
}

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