Submission #1272266

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272266		trideser	Boarding Passes (BOI22_passes)	C++20	100 / 100	134 ms	30956 KiB

passes

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

const int N = 15;

string s;
vector<vector<vector<int>>> prefix(N, vector<vector<int>>());
vector<vector<vector<int>>> prefix_sum(N, vector<vector<int>>());

int calculate_prefix(int color, int boarded, int index) {
	int ret = 0;
	for(int i = 0; i < N; i++) {
		if((1 << i) & boarded) ret += prefix[color][index][i];
	}
	return ret;
}


int calculate_prefix_sum(int color, int boarded, int index) {
	int ret = 0;
	for(int i = 0; i < N; i++) {
		if((1 << i) & boarded) ret += prefix_sum[color][index][i];
	}
	return ret;
}


int calculate_sum(int boarded) {
	int ret = 0;
	for(int i = 0; i < N; i++) {
		if((1 << i) & boarded) ret += prefix[i].back()[i];
	}
	return ret;
}

int opt_cost(int color, int boarded, int seats) {
	int n = prefix[color].size() - 1;
	int l = 0;
	int r = n;
	int total_boarded = calculate_sum(boarded);
	while(l != r) {
		int mid = l + r + 1;
		mid /= 2;
		int cost = (mid * (mid - 1) + (n - mid) * (n - mid - 1)) / 2;
		int prev = mid - 1;
		cost -= (prev * (prev - 1) + (n - prev) * (n - prev - 1)) / 2;
		cost += 2 * (2 * calculate_prefix(color, boarded, mid) - total_boarded);
		if(cost > 0)
			r = mid - 1;
		else
			l = mid;
	}
	int retpt1 = (l * (l - 1) + (n - l) * (n - l - 1)) / 2;
	int ret = 2 * (2 * calculate_prefix_sum(color, boarded, l) + total_boarded * (n - l) - calculate_prefix_sum(color, boarded, n));
	ret += retpt1;

	return ret;
}

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

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