oj.uz

Submission #953505

# Submission time Handle Problem Language Result Execution time Memory
953505 2024-03-26T04:53:18 Z PM1 Boarding Passes (BOI22_passes) C++17
25 / 100
 169 ms 744 KB 
#include <bits/stdc++.h>
using namespace std;
const int mxn=1e5+5,mxg=15;
int g,n,a[mxn],cnt=0,all[mxg+5];
string s;
double dp[(1<<mxg)],res[(1<<mxg)][mxg+5],z=1,sum[(1<<mxg)],num[mxg+5],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)1e18;
		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.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 2 ms 604 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 3 ms 604 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 3 ms 604 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 4 ms 604 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 604 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 3 ms 604 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 604 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 604 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 604 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 604 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 604 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 604 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 604 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 604 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 604 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 604 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 2 ms 604 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 3 ms 604 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 3 ms 604 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 4 ms 604 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 604 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 3 ms 604 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 604 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 604 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 604 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 604 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 604 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 604 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 604 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 604 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 604 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 604 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 ms 608 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 2 ms 604 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 3 ms 728 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 3 ms 604 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 3 ms 604 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 1 ms 604 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 2 ms 724 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 1 ms 604 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 1 ms 744 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 2 ms 604 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 720 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 1 ms 600 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 2 ms 604 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 1 ms 604 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 1 ms 604 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 1 ms 604 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 1 ms 604 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 167 ms 724 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Incorrect 169 ms 604 KB 1st numbers differ - expected: '12495000.5000000000', found: '12495000.0000000000', error = '0.0000000400'
37 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

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