Submission #1217396

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217396		MuhammadSaram	Boarding Passes (BOI22_passes)	C++20	60 / 100	92 ms	86856 KiB

passes

#include <bits/stdc++.h>

using namespace std;

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

const int M = 100001, N = 10, M1 = 10000;

dd e[M],pre[1<<N][M],dp[1<<N];
vector<int> a[N];

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(NULL), cout.tie(NULL);
	cout<<fixed<<setprecision(10);
	
	for (long long 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 j:a[i])
			pre[(1<<i)][j]++;
		for (int j=1;j<M1;j++)
			pre[(1<<i)][j]+=pre[(1<<i)][j-1];
	}
	for (int m=1;m<(1<<N);m++)
	{
		if (__builtin_popcount(m)<2) continue;
		int p=m&-m;
		for (int i=0;i<M1;i++)
			pre[m][i]=pre[p][i]+pre[m^p][i];
	}
	int fin=0;
	for (int m=1;m<(1<<N);m++)
	{
		if (__builtin_popcount(m)==1)
		{
			
			int p=31-__builtin_clz(m),sz=a[p].size();
			if (sz) fin+=m;
			dp[m]=e[sz/2]+e[sz-sz/2];
			continue;
		}
		dp[m]=n*(n-1)/2;
		for (int p=0;p<N;p++)
		{
			if ((m>>p)%2==0) continue;
			int m1=m^(1<<p),sz=a[p].size();
			if (!sz) continue;
			dd val[sz],val1[sz];
			for (int i=0;i<sz;i++)
				val[i]=pre[m1][a[p][i]],val1[i]=pre[m1][M1-1]-pre[m1][a[p][i]];
			for (int i=1;i<sz;i++) val[i]+=val[i-1];
			for (int i=sz-2;i>=0;i--) val1[i]+=val1[i+1];
			dp[m]=min(dp[m],min(val[sz-1],val1[0])+e[sz]+dp[m1]);
			for (int i=1;i<sz;i++)
				dp[m]=min(dp[m],dp[m1]+val[i-1]+val1[i]+e[i]+e[sz-i]);
		}
	}
	cout<<dp[fin]<<endl;
	
	return 0;
}

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