제출 #1179664

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1179664		tamyte	Boarding Passes (BOI22_passes)	C++20	60 / 100	2095 ms	270084 KiB

passes

#include <bits/stdc++.h>
using namespace std;
using ll = long long;


double add(vector<int>& arr, vector<int>& points) {
	double exp = 0;
	int j = 0;
	for (auto& i : points) {
		int left = upper_bound(begin(arr), end(arr), i) - begin(arr);
		int right = arr.size() - left;
		double l = left + (1.0 * j / 2.0);
		double r = right + (points.size() - j - 1) / 2.0;
		exp += min(l, r);
		j++;
	}
	return exp;
}

int main(){
    // random_device rd;
    // mt19937 rng(rd());
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 	string s;
 	cin >> s;
 	int n = s.size();
 	vector<vector<int>> points(15);
 	vector<int> pool;
 	for (int i = 0; i < n; ++i) {
 		int j = s[i] - 'A';
 		pool.push_back(j);
 	}
 	sort(begin(pool), end(pool));
 	pool.erase(unique(begin(pool), end(pool)), end(pool));
 	map<char, int> mp;
 	for (int i = 0; i < pool.size(); ++i) {
 		mp[(pool[i] + 'A')] = i;
 	}
 	for (int i = 0; i < n; ++i) {
 		points[mp[s[i]]].push_back(i);
 	}
 	int k = pool.size();
 	vector<vector<int>> arr((1 << k));
 	for (int i = 0; i < (1 << k); ++i) {
 		vector<int> now;
 		for (int j = 0; j < k; ++j) {
 			if (i >> j & 1) {
 				for (auto& u : points[j]) {
 					now.push_back(u);
 				}
 			}
 		}
 		sort(begin(now), end(now));
 		arr[i] = now;
 	}
 	vector<double> dp((1 << k), 1e15);
 	dp[0] = 0;
 	for (int mask = 0; mask < (1 << k); ++mask) {
 		if (dp[mask] == 1e15) continue;
 		for (int j = 0; j < k; ++j) {
 			if (mask >> j & 1) continue;
 			double ndp = dp[mask] + add(arr[mask], points[j]);
 			dp[mask | (1 << j)] = min(dp[mask | (1 << j)], ndp);
 		}
 	}
 	cout << fixed << setprecision(10) << dp[(1 << k) - 1] << endl;
}

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