Submission #1274291

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274291		mdobric	Boarding Passes (BOI22_passes)	C++20	0 / 100	10 ms	12808 KiB

passes

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

const int maxn = 100005, maxg = 15;
int n, g;
string s;
double prosli[maxn][maxg], dp[1 << maxg];
int red[maxg], red2[maxg];
double ukp[maxg], calcb[maxg][maxg][maxg], calcf[maxg][maxg][maxg];
vector <int> mjesta[maxg];
double ans = 1e18;

int binary_search (int x, int mask){
	int low = 0, high = ukp[red[x]], mid, mid2;
	while (low < high){
		mid = (low + high) / 2;
		mid2 = mid + 1;
		double suma = 0, suma2 = 0;
		suma += mid * (mid - 1) / 2;
		suma += (ukp[red[x]] - mid) * (ukp[red[x]] - mid - 1) / 2;
		suma2 += mid2 * (mid2 - 1) / 2;
		suma2 += (ukp[red[x]] - mid2) * (ukp[red[x]] - mid2 - 1) / 2;
		for (int j = 0; j < g; j++){
			if (mask & (1 << j) and j != x){
				suma += calcf[x][j][mid];
				suma += calcb[x][j][mjesta[red[x]].size() - mid];
				suma2 += calcf[x][j][mid2];
				suma2 += calcb[x][j][mjesta[red[x]].size() - mid2];
			}
		}
		if (suma < suma2) high = mid;
		else low = mid2;
	}
	return low;
}

double rek (int mask){
	if (abs(dp[mask] + 1) > 0.1) return dp[mask];
	dp[mask] = 1e18;
	for (int i = 0; i < g; i++){
		if (mask & (1 << i)){
			double tr = rek(mask - (1 << i));
			int k = binary_search(i, mask - (1 << i));
			double suma = 0;
			suma += k * (k - 1) / 2;
			suma += (ukp[red[i]] - k) * (ukp[red[i]] - k - 1) / 2;
			suma = suma / 2;
			//cout << tr << " " << suma << endl;
			for (int j = 0; j < g; j++){
				if (mask & (1 << j) and j != i){
					suma += calcf[i][j][k];
					suma += calcb[i][j][mjesta[red[i]].size() - k];
				}
			}
			tr += suma;
			//cout << i << " " << mask << "    " << k << "  " << suma << "  " << tr << endl;
			dp[mask] = min(dp[mask], tr);
		}
	}
	//cout << mask << " " << dp[mask] << endl;
	return dp[mask];
}

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) red[g] = j, red2[j] = g, g++;
		prosli[i][j]++;
		ukp[j]++;
		mjesta[j].push_back(i);
	}
	for (int mask = 0; mask < (1 << g); mask++) dp[mask] = -1;
	dp[0] = 0;
	for (int g1 = 0; g1 < g; g1++){
		for (int g2 = 0; g2 < g; g2++){
			if (g1 != g2){
				for (int i = 0; i < mjesta[red[g1]].size(); i++){
					int pos = mjesta[red[g1]][i];
					calcf[g1][g2][i + 1] = calcf[g1][g2][i] + prosli[pos][red[g2]];
				}
				for (int i = mjesta[red[g1]].size() - 1; i >= 0; i--){
					int pos = mjesta[red[g1]][i];
					calcb[g1][g2][mjesta[red[g1]].size() - i] = calcb[g1][g2][mjesta[red[g1]].size() - i - 1] + ukp[red[g2]] - prosli[pos][red[g2]];
				}
				
			}
		}
	}
	//rek(16);
	ans = rek((1 << g) - 1);	
	cout << fixed << setprecision(10);
	cout << ans << "\n";	

	return 0;
}

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