Submission #953499

#	Time	Username	Problem	Language	Result	Execution time	Memory
953499		PM1	Boarding Passes (BOI22_passes)	C++17	25 / 100	7 ms	1112 KiB

passes

#include <bits/stdc++.h>
using namespace std;
const int mxn=1e4+5,mxg=10;
int g,n,a[mxn],cnt=0,all[mxg];
string s;
double dp[(1<<mxg)],res[(1<<mxg)][mxn],z=1,sum[(1<<mxg)],num[mxg],rsum[(1<<mxg)],zz=2;
double c(double x){
	return x/zz;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>s;
	n=s.size();
	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;
		for(int j=0;j<(1<<mxg);j++){
			if(j&(1<<(x-1))){
				rsum[j]+=z;
			}
		}
	}
	for(int i=0;i<n;i++){
		int x=s[i];
		x=a[x];
		for(int j=0;j<(1<<cnt);j++){
			if(j&(1<<(x-1)))continue;
			res[j][x]+=min(sum[j]+c(num[x]),rsum[j]+c(all[x]-num[x]-z));
		}
		for(int j=0;j<(1<<cnt);j++){
			if(j&(1<<(x-1))){
				rsum[j]-=z;
				sum[j]+=z;
			}
		}
		num[x]+=z;
	}
	for(int i=1;i<(1<<cnt);i++){
		dp[i]=(double)1e9;
		for(int j=0;j<cnt;j++){
			if(i&(1<<j)){
				int y=i-(1<<j);
				dp[i]=min(dp[i],dp[y]+res[y][j+1]);
			}
		}
	}
	cout<<dp[(1<<cnt)-1];
	return 0;
}

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