oj.uz

Submission #1081800

# Submission time Handle Problem Language Result Execution time Memory
1081800 2024-08-30T11:06:02 Z wangziyanmo Boarding Passes (BOI22_passes) C++14
100 / 100
 684 ms 645716 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=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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 6772 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 19 ms 1012 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 22 ms 860 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 22 ms 856 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 42 ms 7420 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 237 ms 507840 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 274 ms 605888 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 282 ms 645312 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 285 ms 645284 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.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 35 ms 1628 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 78 ms 1628 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 72 ms 1624 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 43 ms 1628 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 27 ms 860 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 68 ms 1488 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 41 ms 1116 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 41 ms 1116 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 41 ms 1116 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 43 ms 1116 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 41 ms 1164 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 41 ms 1116 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 46 ms 1120 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 41 ms 1364 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 40 ms 1368 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 42 ms 1112 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.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 35 ms 1628 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 78 ms 1628 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 72 ms 1624 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 43 ms 1628 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 27 ms 860 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 68 ms 1488 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 41 ms 1116 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 41 ms 1116 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 41 ms 1116 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 43 ms 1116 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 41 ms 1164 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 41 ms 1116 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 46 ms 1120 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 41 ms 1364 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 40 ms 1368 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 42 ms 1112 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 25 ms 860 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 34 ms 1624 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 74 ms 1624 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 72 ms 1628 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 39 ms 1628 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 27 ms 860 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 69 ms 1368 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 44 ms 1112 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 41 ms 1116 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 42 ms 1184 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 42 ms 1116 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 45 ms 1116 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 42 ms 1116 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 41 ms 1116 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 41 ms 1116 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 41 ms 1116 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 41 ms 1116 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 72 ms 65468 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 71 ms 65468 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 252 ms 65368 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 241 ms 65368 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 80 ms 65360 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 255 ms 65112 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 254 ms 64088 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 256 ms 64092 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 249 ms 64088 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 246 ms 64092 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 251 ms 64156 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 263 ms 64092 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 6772 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 19 ms 1012 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 22 ms 860 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 22 ms 856 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 42 ms 7420 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 237 ms 507840 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 274 ms 605888 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 282 ms 645312 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 285 ms 645284 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 35 ms 1628 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 78 ms 1628 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 72 ms 1624 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 43 ms 1628 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 27 ms 860 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 68 ms 1488 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 41 ms 1116 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 41 ms 1116 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 41 ms 1116 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 43 ms 1116 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 41 ms 1164 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 41 ms 1116 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 46 ms 1120 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 41 ms 1364 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 40 ms 1368 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 42 ms 1112 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 25 ms 860 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 34 ms 1624 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 74 ms 1624 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 72 ms 1628 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 39 ms 1628 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 27 ms 860 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 69 ms 1368 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 44 ms 1112 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 41 ms 1116 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 42 ms 1184 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 42 ms 1116 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 45 ms 1116 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 42 ms 1116 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 41 ms 1116 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 41 ms 1116 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 41 ms 1116 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 41 ms 1116 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 72 ms 65468 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 71 ms 65468 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 252 ms 65368 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 241 ms 65368 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 80 ms 65360 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 255 ms 65112 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 254 ms 64088 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 256 ms 64092 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 249 ms 64088 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 246 ms 64092 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 251 ms 64156 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 263 ms 64092 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 32 ms 856 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 54 ms 1116 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 43 ms 6744 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 19 ms 856 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 21 ms 860 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 22 ms 856 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 42 ms 7260 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 236 ms 507752 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 267 ms 605840 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 291 ms 645448 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 277 ms 645340 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 24 ms 860 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 38 ms 1628 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 74 ms 1628 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 72 ms 1604 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 39 ms 1624 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 27 ms 860 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 67 ms 1372 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 41 ms 1116 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 45 ms 1368 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 43 ms 1116 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 41 ms 1112 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 41 ms 1116 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 41 ms 1184 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 40 ms 1116 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 41 ms 1116 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 41 ms 1116 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 42 ms 1116 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 70 ms 65560 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 69 ms 65620 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 248 ms 65508 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 242 ms 65200 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 83 ms 65560 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 246 ms 65104 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 253 ms 64348 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 248 ms 64084 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 253 ms 64336 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 251 ms 64080 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 254 ms 64080 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 245 ms 64080 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 684 ms 645716 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 61 ms 1116 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 636 ms 645392 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 288 ms 645460 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 38 ms 1112 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 673 ms 645600 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 671 ms 645668 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 657 ms 643148 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 669 ms 643292 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 668 ms 643144 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 660 ms 643208 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 679 ms 643216 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 637 ms 642380 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 654 ms 643152 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'