Submission #1273912

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273912		mdobric	Boarding Passes (BOI22_passes)	C++20	55 / 100	508 ms	242188 KiB

passes

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

const int maxn = 10005, maxg = 15, off = 1024;
int n, g;
string s;
double prosli[maxn][maxg];
int red[maxg], red2[maxg], red3[maxg];
double ukp[maxg];
double lijevo[off][maxn], desno[off][maxn], dodaj[off][maxn];
vector <int> mjesta[maxg];
double ans = 1e18;
double dp[maxg][off];

double calc (int i, int x, int mask){
	//cout << i << " " << x << " " << mask << "   " << dp[i][mask] << endl;
	if (abs(dp[i][mask] + 1) > 0.01) return dp[i][mask];
	for (int j = 0; j < g; j++){
		if (mask & (1 << j)){
			int y = calc(j, red3[j], mask - (1 << j));
			break;
		}
	}
	double tr = 0;
	for (int j = 0; j < mjesta[x].size(); j++){
		int y = mjesta[x][j];
		tr += min(lijevo[mask][y] + (prosli[y][x] - 1) / 2, desno[mask][y] + (ukp[x] - prosli[y][x]) / 2);
	}
	for (int j = 0; j < n; j++) dodaj[mask + (1 << i)][j] = dodaj[mask][j];
	for (int j = 0; j < mjesta[x].size(); j++) dodaj[mask + (1 << i)][mjesta[x][j]] = 1;
	for (int j = 0; j < n; j++){
		if (j == 0) lijevo[mask + (1 << i)][j] = dodaj[mask + (1 << i)][j];
		else lijevo[mask + (1 << i)][j] = lijevo[mask + (1 << i)][j - 1] + dodaj[mask + (1 << i)][j];
	}
	for (int j = n - 1; j >= 0; j--){
		if (j == n - 1) desno[mask + (1 << i)][j] = dodaj[mask + (1 << i)][j];
		else desno[mask + (1 << i)][j] = desno[mask + (1 << i)][j + 1] + dodaj[mask + (1 << i)][j];
	}
	//cout << i << " " << mask << "   " << tr << endl;
	//cout << lijevo[mask][0] << lijevo[mask][1] << lijevo[mask][2] << lijevo[mask][3] << lijevo[mask][4] << lijevo[mask][5] << endl;
	//cout << desno[mask][0] << desno[mask][1] << desno[mask][2] <<  desno[mask][3] << desno[mask][4] << desno[mask][5] <<endl;
	return dp[i][mask] = tr;
}

int main (void){
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> s;
	n = s.size();
	memset(prosli, 0, sizeof prosli);
	for (int i = 0; i < n; i++){
		if (i != 0){
			for (int j = 0; j < 15; j++) prosli[i][j] = prosli[i - 1][j];
		}
		int j = s[i] - 'A';
		if (prosli[i][j] == 0) red2[g] = g, red[g] = j, red3[g] = j, g++;
		prosli[i][j]++;
		ukp[j]++;
		mjesta[j].push_back(i);
	}
	sort(red, red + g);
	sort(red3, red3 + g);
	for (int i = 0; i < 10; i++){
		for (int j = 0; j < 1024; j++) dp[i][j] = -1;
	}
	do{
		double tr = 0;
		int mask = 0;
		for (int i = 0; i < g; i++){
			tr += calc(red2[i], red[i], mask);
			mask += (1 << red2[i]);
			//cout << tr << "\n";
		}
		ans = min(ans, tr);
	}while (next_permutation(red, red + g) and next_permutation(red2, red2 + g));
	cout << fixed << setprecision(10);
	cout << ans << "\n";	

	return 0;
}

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