제출 #1217371

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1217371		MuhammadSaram	Boarding Passes (BOI22_passes)	C++20	0 / 100	9 ms	2824 KiB

passes

#include <bits/stdc++.h>

using namespace std;

#define dd long double
#define all(v) v.begin(), v.end()

const int M = 100001, N = 7;

dd e[M],val[N][1<<N][101];
vector<int> a[N];

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(NULL), cout.tie(NULL);
	cout<<fixed<<setprecision(10);
	
	for (int i=2;i<M;i++)
		e[i]=i*(i-1)/4.0;
	
	string s;
	cin>>s;
	int n=s.size();
	for (int i=0;i<n;i++)
		a[s[i]-'A'].push_back(i);
	if (a[0].size()==n)
	{
		cout<<e[n/2]+e[n-n/2]<<endl;
		return 0;
	}
	vector<int> v;
	for (int i=0;i<N;i++)
		v.push_back(i);
	for (int i=0;i<N;i++)
		for (int m=0;m<(1<<N);m++)
			for (int k=0;k<=a[i].size();k++)
			{
				if (m>>i&1) continue;
				for (int j=0;j<N;j++)
				{
					if ((m>>j)%2==0) continue;
					for (int l=0;l<k;l++)
						val[i][j][k]+=lower_bound(all(a[j]),a[i][l])-begin(a[j]);
					for (int l=k;l<a[i].size();l++)
						val[i][j][k]+=a[j].size()-(lower_bound(all(a[j]),a[i][l])-begin(a[j]));
				}
			}
	dd ans=n*(n-1)/2;
	do
	{
		int m=0;
		dd vl=0;
		for (int i:v)
		{
			dd mn=n*(n-1)/2;
			int sz=a[i].size();
			for (int k=0;k<=sz;k++)
				mn=min(mn,val[i][m][k]+e[k]+e[sz-k]);
			vl+=mn,m+=(1<<i);
		}
		ans=min(ans,vl);
	}while(next_permutation(all(v)));
	cout<<ans<<endl;
	
	return 0;
}

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