Submission #582122

#	Time	Username	Problem	Language	Result	Execution time	Memory
582122		amunduzbaev	Boarding Passes (BOI22_passes)	C++17	0 / 100	1 ms	596 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;
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);
	}
	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++){
		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 = n, d = check(0);
			while(l + 1 < r - 1){
				int m = (l + r) >> 1;
				if(check(m) <= check(m + 1)) d = min(d, check(m)), r = m;
				else d = min(d, check(m + 1)), l = m + 1;
			}
			
			int res = min({check(l), check(r), check(l + 1), d});
			if((mask >> b) == 0){
				//~ for(int k=0;k<=n;k++){
					//~ cout<<check(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: 0 / 5
• Subtask 2: 0 / 25
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40