Submission #829446

#	Time	Username	Problem	Language	Result	Execution time	Memory
829446		QwertyPi	Boarding Passes (BOI22_passes)	C++14	25 / 100	2091 ms	298260 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 dp[1 << G];
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++){
				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--){
				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++){
			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--){
			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 = 1LL << 60;
				for(int x = 0; x <= n; 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];
						}
					}
					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: 0 / 5
• Subtask 2: 25 / 25
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40