oj.uz

Submission #1080839

# Submission time Handle Problem Language Result Execution time Memory
1080839 2024-08-29T14:48:54 Z wangziyanmo Boarding Passes (BOI22_passes) C++14
5 / 100
 340 ms 645484 KB 
#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=l+(r-l)/3*2;
		//cerr<<l<<' '<<r<<' '<<ml<<' '<<mr<<"\n"; 
		if (getcost(ml,num,k)<=getcost(mr,num,k)) r=mr;
		else l=ml;
	}
	ld ret=1e18;
	for (int i=l;i<=r;i++) 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=2;i<=n;i++){
		cost[i]=(cost[i-1]+(ld)(i-1)/2);
	}
	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<<dp[i]<<"\n";
	}
	printf("%.6Lf\n",dp[(1<<15)-1]);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 6748 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 19 ms 856 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 20 ms 1012 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 22 ms 860 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 42 ms 7368 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 273 ms 507840 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 296 ms 605756 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 307 ms 645484 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 340 ms 645460 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 860 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 33 ms 1628 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Incorrect 70 ms 1628 KB 1st numbers differ - expected: '1023.0000000000', found: '466.5000000000', error = '0.5439882698'
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 860 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 33 ms 1628 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Incorrect 70 ms 1628 KB 1st numbers differ - expected: '1023.0000000000', found: '466.5000000000', error = '0.5439882698'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 6748 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 19 ms 856 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 20 ms 1012 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 22 ms 860 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 42 ms 7368 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 273 ms 507840 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 296 ms 605756 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 307 ms 645484 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 340 ms 645460 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 24 ms 860 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 33 ms 1628 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Incorrect 70 ms 1628 KB 1st numbers differ - expected: '1023.0000000000', found: '466.5000000000', error = '0.5439882698'
13 Halted 0 ms 0 KB -