Submission #829466

#	Time	Username	Problem	Language	Result	Execution time	Memory
829466		QwertyPi	Boarding Passes (BOI22_passes)	C++14	100 / 100	597 ms	564600 KiB

passes

#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

int f(int x){
	return x * (x - 1) / 2;
}

const int G = 15;
const int N = 1e5 + 11;
int L[G][G][N], R[G][G][N];
int cL[G][N], cR[G][N];

int s0[G][G][N], s1[G][N];
int dp[1 << G];

int f(int mask, int j, int x){
	int c = cL[j][x] + cR[j][x];
	for(int k = 0; k < G; k++){
		if(j != k && (mask & (1 << k))){
			c += L[k][j][x] + R[k][j][x];
		}
	}
	return c;
}

int g(int mask, int j, int x){
	int c = s1[j][x];
	for(int k = 0; k < G; k++){
		if(j != k && (mask & (1 << k))){
			c += s0[k][j][x];
		}
	}
	return c;
}

int32_t main(){
	string s; cin >> s;
	int n = s.size();
	for(int i = 0; i < G; i++){
		for(int j = 0; j < G; j++){
			// add char i then char j
			L[i][j][0] = 0; int m = 0;
			for(int k = 0; k < n; k++){
				s0[i][j][k] += m;
				if(s[k] == 'A' + i){
					m += 2;
					L[i][j][k + 1] = L[i][j][k];
				}else if(s[k] == 'A' + j){
					L[i][j][k + 1] = L[i][j][k] + m;
				}else{
					L[i][j][k + 1] = L[i][j][k];
				}
			}
			R[i][j][n] = 0; m = 0;
			for(int k = n - 1; k >= 0; k--){
				s0[i][j][k] -= m;
				if(s[k] == 'A' + i){
					m += 2;
					R[i][j][k] = R[i][j][k + 1];
				}else if(s[k] == 'A' + j){
					R[i][j][k] = R[i][j][k + 1] + m;
				}else{
					R[i][j][k] = R[i][j][k + 1];
				}
			}
		}
	}

	for(int i = 0; i < G; i++){
		cL[i][0] = 0; int m = 0;
		for(int j = 0; j < n; j++){
			s1[i][j] += m;
			if(s[j] == 'A' + i){
				cL[i][j + 1] = cL[i][j] + m; m++;
			}else{
				cL[i][j + 1] = cL[i][j];
			}
		}
		cR[i][n] = 0; m = 0;
		for(int j = n - 1; j >= 0; j--){
			s1[i][j] -= m;
			if(s[j] == 'A' + i){
				cR[i][j] = cR[i][j + 1] + m; m++;
			}else{
				cR[i][j] = cR[i][j + 1];
			}
		}
	}

	dp[0] = 0; fill(dp + 1, dp + (1 << G), 1LL << 60);
	for(int mask = 1; mask < (1 << G); mask++){
		for(int j = 0; j < G; j++){
			if(mask & (1 << j)){
				int cost = min(f(mask, j, 0), f(mask, j, n));
				int lo = 0, hi = n;
				while(lo + 1 < hi){
					int mid = (lo + hi) / 2;
					int c = g(mask, j, mid);
					if(c < 0) lo = mid;
					else hi = mid;
				}
				for(int x = lo; x <= hi; x++){
					int c = f(mask, j, x);
					cost = min(cost, c);
				}
				dp[mask] = min(dp[mask], dp[mask - (1 << j)] + cost);
			}
		}
	}
	cout << setprecision(10) << fixed << ((long double) dp[(1 << G) - 1] / 2) << endl;
}

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