Submission #953721

#	Time	Username	Problem	Language	Result	Execution time	Memory
953721		PM1	Boarding Passes (BOI22_passes)	C++17	100 / 100	494 ms	628492 KiB

passes

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#define ll long long
const int mxn=1e5+5,mxg=15;
int g,n,a[mxn],cnt=0,all[mxg+5];
string s;
ll dp[(1<<mxg)],res[(1<<mxg)][mxg+5],z=1,zz=2;
ll pre[mxn][mxg+5][mxg+5],suf[mxn][mxg+5][mxg+5],num[mxn];
vector<int>v[mxg+5];
ll cal(ll mask,int c,ll y){
	ll sum=0,x=v[c][y];
	for(int i=1;i<=cnt;i++){
		if(mask&(1<<(i-1))){
			sum+=pre[x+1][c][i]+suf[x+1][c][i];
		}
	}
	sum*=2;
	sum+=y*(y-1)/2;
	y=all[c]-y;
	sum+=y*(y-1)/2;
	return sum;
}
ll calu(ll mask,int c){
	ll sum=0;
	for(int i=1;i<=cnt;i++){
		if(mask&(1<<(i-1))){
			sum+=suf[0][c][i];
		}
	}
	sum*=2;
	ll y=all[c];
	sum+=y*(y-1)/2;
	return sum;
}
ll f(ll mask,ll c){
	ll res=calu(mask,c);
	int L=0,R=v[c].size()-1;
	while(L<R){
		int mid=(L+R)/2;
		ll x=cal(mask,c,mid);
		ll y=cal(mask,c,mid+1);
		if(x<=y)
			R=mid;
		else
			L=mid+1;
	}
	res=min(res,cal(mask,c,L));
	//cout<<mask<<" "<<c<<" "<<res<<'\n';
	return res;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>s;
	n=s.size();
	for(int i=1;i<=mxg;i++)
		v[i].push_back(-1);
	for(int i=0;i<n;i++){
		int x=s[i];
		a[x]=(a[x]==0)?++cnt:a[x];
		x=a[x];
		all[x]+=z;
		v[x].push_back(i);
	}
	for(int i=0;i<n;i++){
		int x=s[i];
		x=a[x];
		for(int j=1;j<=cnt;j++){
			for(int k=1;k<=cnt;k++){
				if(j==k)continue;
				pre[i+1][j][k]=pre[i][j][k];
				if(x==j)
					pre[i+1][j][k]+=num[k];
			}
		}
		num[x]++;
	}
	memset(num,0,sizeof num);
	for(int i=n-1;i>=0;i--){
		int x=s[i];
		x=a[x];
		for(int j=1;j<=cnt;j++){
			for(int k=1;k<=cnt;k++){
				if(j==k)continue;
				suf[i][j][k]=suf[i+1][j][k];
				if(x==j)
					suf[i][j][k]+=num[k];
			}
		}
		num[x]++;
	}
	for(int i=1;i<(1<<cnt);i++){
		dp[i]=1e18;
		for(int j=0;j<cnt;j++){
			if(i&(1<<j)){
				int y=i-(1<<j);
				dp[i]=min(dp[i],dp[y]+f(y,j+1));
			}
		}
	}
	cout<<dp[(1<<cnt)-1]/2;
	if(dp[(1<<cnt)-1]%2)
		cout<<".5";
	return 0;
}

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