Submission #722691

#	Time	Username	Problem	Language	Result	Execution time	Memory
722691		HamletPetrosyan	Boarding Passes (BOI22_passes)	C++17	60 / 100	1212 ms	668 KiB

passes

/// -- -- ---- --- -- --
/// 12.04.2023 Wed 20:35
/// -- -- ---- --- -- --

#include <bits/stdc++.h>
using namespace std;
void abandoned_precalc();

#define pll pair<long long, long long>
#define all(a) (a).begin(), (a).end()
#define len(a) ((long long)(a).size())
#define add push_back
#define mkp make_pair
#define ll long long
#define fr first
#define sc second

const long long INF = 1000000000ll * 1000000003ll;
const long long MOD = 1000000007ll;
const int N = 2e5 + 5, G = 10;

string s;
ll ans4 = INF;

ll dp[(1 << G)];
ll asc[N], pref[N], suf[N];
ll cnt[N], sc;

int o(char x){ return x - 'A'; }

void solve(){
	cin >> s;
//	for(ll i = 0; i <= len(s); i++){
//		ans4 = min(ans4, i * (i - 1) + (len(s) - i) * (len(s) - i - 1));
//	}
//	cout << (double)ans4 / 4. << "\n";

	for(int i = 0; i < len(s); i++) asc[o(s[i])]++;
//	for(int i = 0; i <= G; i++) cout << asc[i] << " ";
//	cout << "\n";

	for(int mask = 1; mask < (1 << G); mask++){
		dp[mask] = INF;
		fill(cnt, cnt + G, 0); sc = 0;
		for(int i = len(s) - 1; ~i; i--){
			if(!(mask & (1 << o(s[i])))) continue;
			sc++; cnt[o(s[i])]++;
			suf[o(s[i])] += sc - cnt[o(s[i])];
			pref[o(s[i])] = 0;
		}
		for(int i = 0; i < G; i++){
			if(!(mask & (1 << i))) continue;
			dp[mask] = min(dp[mask], dp[mask ^ (1 << i)]
										+ suf[i] * 4
										+ cnt[i] * (cnt[i] - 1));
		}
		for(int i = 0, pc = 0; i < len(s); i++){
			if(!(mask & (1 << o(s[i])))) continue;
			suf[o(s[i])] -= sc - cnt[o(s[i])];
			sc--; cnt[o(s[i])]--; pc++;
			pref[o(s[i])] += pc - asc[o(s[i])] + cnt[o(s[i])];
			dp[mask] = min(dp[mask], dp[mask ^ (1 << o(s[i]))]
										+ (pref[o(s[i])] + suf[o(s[i])]) * 4
										+ cnt[o(s[i])] * (cnt[o(s[i])] - 1) + (asc[o(s[i])] - cnt[o(s[i])]) * (asc[o(s[i])] - cnt[o(s[i])] - 1));
		}
	}
	cout << (double)dp[(1 << G) - 1] / 4. << "\n";
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	int _ = 1;
	cout << fixed;
	cout.precision(9);

	abandoned_precalc();
	// cin >> _ ;
	while(_--) solve();
	return 0;
}

/// ---- - --------  ------ -------- -- - - -
/// just a reminder. ubuntu password is i o i
/// ---- - --------  ------ -------- -- - - -














void abandoned_precalc(){
	
}

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