Submission #1081800

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081800		wangziyanmo	Boarding Passes (BOI22_passes)	C++14	100 / 100	684 ms	645716 KiB

passes

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ld long double

int pre[100010][20],pr[100010][20][20],su[100010][20][20];
ld cost[100010];
ld dp[100010];
vector<int> place[20];

ld getcost(int pos,int num,int k){
	//cerr<<pos<<' '<<num<<' '<<k<<"\n";
	int n=place[k].size()-1;
	ld ret=cost[pos+1]+cost[n-pos];
	for (int i=0;i<15;i++){
		if ((num&(1<<i))==0) continue;
		if (pos<n) ret+=su[place[k][pos+1]][k][i];
		if (pos>-1) ret+=pr[place[k][pos]][k][i];
	}
	return ret;
}

ld cacu(int num,int k){
	int l=-1,r=place[k].size()-1;
	//cerr<<l<<' '<<r<<"\n";
	while (l+5<r){
		int ml=l+(r-l)/3,mr=r-(r-l)/3;
		//cerr<<l<<' '<<r<<' '<<ml<<' '<<mr<<"\n"; 
		if (getcost(ml,num,k)<=getcost(mr,num,k)) r=mr;
		else l=ml;
	}
	//cout<<l<<' '<<r<<"\n";
	ld ret=1e18;
	for (int i=l;i<=r;i++){
		//cout<<i<<' '<<getcost(i,num,k)<<"\n";
		ret=min(getcost(i,num,k),ret);
	}
	return ret;
}

signed main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	string s;cin>>s;s=' '+s;
	int n=s.size()-1;
	for (int i=1;i<=n;i++){
		for (int j=0;j<15;j++) pre[i][j]=pre[i-1][j];
		pre[i][s[i]-'A']++;
		place[s[i]-'A'].push_back(i);
	}
	for (int i=0;i<15;i++){
		//for (auto x:place[i]) cout<<x<<' ';
		//cout<<"\n";
	}
	for (int i=2;i<=n;i++){
		cost[i]=(cost[i-1]+(ld)(i-1)/2);
		//cout<<cost[i]<<' ';
	}
	//cout<<"\n";
	for (int i=1;i<=n;i++){
		for (int j=0;j<15;j++){
			for (int k=0;k<15;k++){
				pr[i][j][k]=pr[i-1][j][k];
			}
		}
		for (int k=0;k<15;k++) pr[i][s[i]-'A'][k]+=pre[i][k];
	}
	for (int i=n;i>0;i--){
		for (int j=0;j<15;j++){
			for (int k=0;k<15;k++){
				su[i][j][k]=su[i+1][j][k];
			}
		}
		for (int k=0;k<15;k++) su[i][s[i]-'A'][k]+=pre[n][k]-pre[i-1][k];		
	}
	dp[0]=0;
	for (int i=1;i<(1<<15);i++) dp[i]=1e18;
	for (int i=1;i<(1<<15);i++){
		for (int j=0;j<15;j++){
			if ((i&(1<<j))==0) continue;
			//cerr<<i<<' '<<j<<"\n";
			dp[i]=min(dp[i^(1<<j)]+cacu(i^(1<<j),j),dp[i]);
			//cout<<cacu(i^(1<<j),j)<<' '<<dp[i^(1<<j)]+cacu(i^(1<<j),j)<<"\n";
		}
		//cout<<dp[i]<<"\n\n";
	}
	printf("%.6Lf\n",dp[(1<<15)-1]);
}

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