oj.uz

Submission #1080814

# Submission time Handle Problem Language Result Execution time Memory
1080814 2024-08-29T14:31:57 Z wangziyanmo Boarding Passes (BOI22_passes) C++14
0 / 100
 70 ms 7772 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];		
	}
	//return 0;
	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";
	}
	cout<<dp[(1<<15)-1]<<"\n";
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 43 ms 7772 KB 1st numbers differ - expected: '100800.5000000000', found: '100800.0000000000', error = '0.0000049603'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1016 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 36 ms 1628 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Incorrect 70 ms 1624 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 26 ms 1016 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 36 ms 1628 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Incorrect 70 ms 1624 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 Incorrect 43 ms 7772 KB 1st numbers differ - expected: '100800.5000000000', found: '100800.0000000000', error = '0.0000049603'
2 Halted 0 ms 0 KB -