Submission #582258

#	Time	Username	Problem	Language	Result	Execution time	Memory
582258		amunduzbaev	Boarding Passes (BOI22_passes)	C++17	100 / 100	701 ms	365968 KiB

passes

#include "bits/stdc++.h"
using namespace std;
 
#define ar array
typedef int64_t ll;
#define int ll

const int G = 15;
const int N = 1e5 + 5;
vector<int> gop[G];
int dp[1 << G]; 
int pref[G][G][N], cc[G][N];
int suff[G][G][N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	string s; cin>>s;
	int n = s.size(), g = 0;
	for(int i=0;i<n;i++){
		g = max(g, (ll)s[i] - 'A' + 1);
		gop[s[i] - 'A'].push_back(i);
	}
	for(int i=0;i<n;i++){
		if(i){
			for(int j=0;j<g;j++) cc[j][i] = cc[j][i-1];
		}
		
		cc[s[i] - 'A'][i]++;
	}
	
	for(int a=0;a<g;a++){
		gop[a].push_back(n);
		gop[a].push_back(n);
		for(int b=0;b<g;b++){
			for(int i=0;i<n;i++){
				if(i) pref[a][b][i] = pref[a][b][i - 1];
				if(s[i] - 'A' == a){
					pref[a][b][i] += cc[b][i] * 2;
				}
			}
			for(int i=n-1;~i;i--){
				suff[a][b][i] = suff[a][b][i + 1];
				if(s[i] - 'A' == a){
					suff[a][b][i] += (cc[b][n - 1] - cc[b][i]) * 2;
				}
			}
		}
	}
	
	memset(dp, 63, sizeof dp);
	dp[0] = 0;
	for(int mask=0;mask < (1 << g);mask++){
		//~ int b = __builtin_popcount(mask);
		//~ if((mask >> b) == 0){
			//~ for(int k=0;k<g;k++) cout<<(mask >> k & 1);
			//~ cout<<" : "<<dp[mask]<<"\n";
		//~ }
		
		for(int j=0;j<g;j++){
			if(mask >> j & 1) continue;
			auto check = [&](int i){
				int res = 0;
				for(int k=0;k<g;k++){
					if(mask >> k & 1){
						if(i) res += pref[j][k][i - 1];
						res += suff[j][k][i];
					}
				}
				if(i){
					int m = cc[j][i - 1];
					if(m) res = res + m * (m - 1) / 2;
				}
				
				int m = cc[j][n - 1] - (i ? cc[j][i - 1] : 0);
				if(m) res = res + m * (m - 1) / 2;
				return res;
			};
			
			int l = 0, r = gop[j].size() - 1;
			while(l + 1 < r - 1){
				int m = (l + r) >> 1;
				if(check(gop[j][m]) < check(gop[j][m + 1])) r = m + 1;
				else l = m;
			}
			
			int res = min({check(gop[j][l]), check(gop[j][r]), check(gop[j][l + 1])});
			//~ if((mask >> b) == 0){
				//~ for(int k=0;k<(int)gop[j].size();k++){
					//~ cout<<check(gop[j][k])<<" ";
				//~ } cout<<"\n";
				//~ cout<<res<<"\n";
			//~ }
			
			dp[mask | (1 << j)] = min(dp[mask | (1 << j)], dp[mask] + res);
		}
	}
	
	int res = dp[(1 << g) - 1];
	cout<<res/2;
	if(res&1) cout<<".5";
}

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