oj.uz

Submission #953516

# Submission time Handle Problem Language Result Execution time Memory
953516 2024-03-26T05:05:58 Z PM1 Boarding Passes (BOI22_passes) C++17
60 / 100
 2000 ms 6276 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mxn=1e5+5,mxg=15;
int g,n,a[mxn],cnt=0,all[mxg+5];
string s;
ll dp[(1<<mxg)],res[(1<<mxg)][mxg+5],z=1,sum[(1<<mxg)],num[mxg+5],rsum[(1<<mxg)],zz=2;
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 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))){
				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]*2+num[x],rsum[j]*2+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]=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]/2;
	if(dp[(1<<cnt)-1]%2)
		cout<<".5";
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 344 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 348 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 1 ms 604 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 2 ms 604 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 1 ms 604 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 2 ms 604 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 0 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 0 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 0 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 0 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 0 ms 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 0 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 0 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 348 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 0 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 0 ms 464 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 0 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 0 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 0 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 1 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 1 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 1 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 0 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 1 ms 344 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 0 ms 344 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 1 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 1 ms 344 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 0 ms 344 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 0 ms 348 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 0 ms 396 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 0 ms 344 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 1 ms 504 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 1 ms 504 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 1 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 1 ms 348 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 1 ms 348 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 33 ms 496 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 29 ms 600 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 33 ms 500 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 44 ms 648 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 33 ms 664 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 33 ms 496 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 44 ms 604 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 33 ms 672 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 33 ms 664 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 37 ms 604 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 344 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 348 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 1 ms 604 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 2 ms 604 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 1 ms 604 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 2 ms 604 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 1 ms 344 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 0 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 1 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 0 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 0 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 0 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 0 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 0 ms 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 0 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 0 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 1 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 1 ms 348 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 1 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 0 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 0 ms 464 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 0 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 0 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 0 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 1 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 1 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 1 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 0 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 1 ms 344 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 0 ms 344 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 1 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 1 ms 344 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 0 ms 344 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 0 ms 348 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 0 ms 396 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 0 ms 344 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 1 ms 504 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 1 ms 504 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 1 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 1 ms 348 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 1 ms 348 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 33 ms 496 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 29 ms 600 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 33 ms 500 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 44 ms 648 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 33 ms 664 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 33 ms 496 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 44 ms 604 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 33 ms 672 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 33 ms 664 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 37 ms 604 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 1 ms 348 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 8 ms 6276 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 1 ms 500 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 1 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 1 ms 344 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 1 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 1 ms 348 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 2 ms 604 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 2 ms 604 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 1 ms 592 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 3 ms 744 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 1 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 0 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 0 ms 344 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 0 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 1 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 1 ms 344 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 1 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 1 ms 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 1 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 1 ms 460 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 1 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 1 ms 344 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 1 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 1 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 0 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 1 ms 464 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 1 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 1 ms 348 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 1 ms 344 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 33 ms 604 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 39 ms 604 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 43 ms 660 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 32 ms 664 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 33 ms 688 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 41 ms 668 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 38 ms 680 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 34 ms 600 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 33 ms 600 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 36 ms 516 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Execution timed out 2024 ms 2904 KB Time limit exceeded
97 Halted 0 ms 0 KB -