Submission #1270829

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270829		trideser	Boarding Passes (BOI22_passes)	C++20	25 / 100	2093 ms	10312 KiB

passes

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 15;

string s;

int opt_cost(int color, vector<vector<int>>& prefix, int boarded, int seats) {
	int n = prefix[color].back();
	int cost_fb = 0;
	for(int i = 0; i < N; i++) {
		if((1 << i) & boarded)
			cost_fb += prefix[i].back();
	}
	int cost_sum_pref = 0;
	for(int i = 0; i < seats; i++) {
		if(s[i] - 65 == color) {
			for(int j = 0; j < N; j++) {
				if((1 << j) & boarded) cost_sum_pref += prefix[j][i];
			}
		}
	}

	int cost_pref = 0;
	int visited = 0;
	int cost = n * (n - 1) / 2 + 2 * (cost_fb * n - cost_sum_pref);
	for(int i = 0; i < seats; i++) {
		if(s[i] - 65 == color) {
			visited++;
			for(int j = 0; j < N; j++) {
				if((1 << j) & boarded) cost_pref += prefix[j][i];
			}
			int newcost = visited * (visited - 1) / 2;
			newcost += (n - visited) * (n - visited - 1) / 2;
			newcost += cost_pref + cost_fb * (n - visited) - (cost_sum_pref - cost_pref);
			newcost += cost_pref + cost_fb * (n - visited) - (cost_sum_pref - cost_pref);
			//cout << "\t\t" << "\n";
			cost = min(cost, newcost);
		}
	}
	//cout << "\t" << cost << "\n";
	return cost;
}

int32_t main() {
	cin >> s;
	vector<vector<int>> prefix(N, vector<int>(s.size(), 0));
	for(int i = 0; i < s.size(); i++) {
		prefix[s[i] - 65][i] = 1;
	}
	for(int i = 0; i < N; i++) {
		for(int j = 1; j < s.size(); j++) {
			prefix[i][j] += prefix[i][j-1];
		}
	}
	vector<int> state(1 << N, 0x7fffffffffffffff);
	vector<int> currentstates;
	state[0] = 0;
	currentstates.push_back(0);
	while(!currentstates.empty()) {
		//cout << "->\n";
		vector<int> newcurrentstates;
		for(int st : currentstates) {
			//cout << st << ":\n";
			for(int b = 0; b < N; b++) {
				if((1 << b) & st) continue;
				if((1 << b) > st) newcurrentstates.push_back(st | (1 << b));
				int cost = opt_cost(b, prefix, st, s.size());
				int newstate = (1 << b) | st;
				//cout << state[st] + cost << "\n";
				state[newstate] = min(state[newstate], state[st] + cost);
			}
		}
		currentstates = newcurrentstates;
	}
	cout << state.back() / 2;
	if(state.back() & 1) cout << ".5";
	return 0;
}

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