제출 #796795

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
796795		ToniB	Boarding Passes (BOI22_passes)	C++17	60 / 100	2083 ms	16748 KiB

passes

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int MAXN = 1e5 + 2;
const int G = 15;

int n, g, cmp[27], pre[MAXN][G], suf[MAXN][G];
bool bio[27];
string s;
ll dp[1 << 15];
vector<int> group[MAXN];

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

int cnt_lower(int i, int mask){
	int ret = 0;
	for(int j = 0; j < g; ++j){
		if(mask & 1 << j) ret += pre[i][j];
	}
	return 4 * ret;
}
int cnt_higher(int i, int mask){
	int ret = 0;
	for(int j = 0; j < g; ++j){
		if(mask & 1 << j) ret += suf[i][j];
	}
	return 4 * ret;
}

int main(){
	cin >> s;
	n = s.length();
	for(char c : s) bio[c - 'A'] = 1;
	for(int i = 0; i < 26; ++i){
		if(bio[i]) cmp[i] = g++;
	}
	for(int i = 0; i < n; ++i) group[cmp[s[i] - 'A']].push_back(i);

	pre[0][cmp[s[0] - 'A']] = 1;
	suf[n - 1][cmp[s[n - 1] - 'A']] = 1;
	for(int i = 1; i < n; ++i){
		for(int j = 0; j < g; ++j) pre[i][j] = pre[i - 1][j];
		++pre[i][cmp[s[i] - 'A']];
	}
	for(int i = n - 2; i >= 0; --i){
		for(int j = 0; j < g; ++j) suf[i][j] = suf[i + 1][j];
		++suf[i][cmp[s[i] - 'A']];
	}
	
	dp[0] = 0;
	for(int i = 1; i < (1 << g); ++i){
		dp[i] = 1e18;
		for(int j = 0; j < g; ++j){
			if(i & 1 << j){
				ll cur = 1e18;
				int sz = group[j].size();
				assert(sz);

				vector<ll> lower (sz), higher (sz);
				lower[0] = cnt_lower(group[j][0], i ^ 1 << j);
				higher[sz - 1] = cnt_higher(group[j][sz - 1], i ^ 1 << j);
				for(int idx = 1; idx < sz; ++idx){
					lower[idx] = lower[idx - 1] + cnt_lower(group[j][idx], i ^ 1 << j);
				}
				for(int idx = sz - 2; idx >= 0; --idx){
					higher[idx] = higher[idx + 1] + cnt_higher(group[j][idx], i ^ 1 << j);
				}

				cur = min(higher[0], lower[sz - 1]) + f(sz);
				for(int idx = 0; idx < sz - 1; ++idx){
					cur = min(cur, lower[idx] + higher[idx + 1] + f(idx + 1) + f(sz - idx - 1));
				}
				cur += dp[i ^ 1 << j];
				dp[i] = min(dp[i], cur);
			}
		}
	}
	cout << fixed << setprecision(7) << (long double)dp[(1 << g) - 1] / 4LL;
	return 0;
}

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