oj.uz

Submission #953514

# Submission time Handle Problem Language Result Execution time Memory
953514 2024-03-26T05:04:35 Z PM1 Boarding Passes (BOI22_passes) C++17
55 / 100
 2000 ms 2904 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 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]*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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2652 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 2652 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 2652 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 2652 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 28 ms 2652 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Execution timed out 2021 ms 2904 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 3 ms 2652 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 4 ms 2648 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 4 ms 2648 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 4 ms 2648 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 2 ms 2652 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 4 ms 2652 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 3 ms 2652 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 2 ms 2652 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 2 ms 2652 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 3 ms 2652 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 2 ms 2652 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 2 ms 2652 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 2 ms 2648 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 2 ms 2652 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 2 ms 2652 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 2 ms 2652 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 2652 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 3 ms 2652 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 4 ms 2648 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 4 ms 2648 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 4 ms 2648 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 2 ms 2652 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 4 ms 2652 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 3 ms 2652 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 2 ms 2652 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 2 ms 2652 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 3 ms 2652 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 2 ms 2652 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 2 ms 2652 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 2 ms 2648 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 2 ms 2652 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 2 ms 2652 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 2 ms 2652 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 ms 2652 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 4 ms 2652 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 4 ms 2648 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 4 ms 2652 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 4 ms 2652 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 1 ms 2652 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 4 ms 2460 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 2 ms 2652 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 2 ms 2652 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 2 ms 2660 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 2 ms 2648 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 2 ms 604 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 3 ms 600 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 2 ms 604 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 2 ms 604 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 2 ms 604 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 297 ms 736 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 317 ms 736 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 366 ms 2704 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 342 ms 2708 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 385 ms 2648 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 346 ms 2700 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 380 ms 2700 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 440 ms 736 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 371 ms 2704 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 372 ms 2704 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 366 ms 2700 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 377 ms 852 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2652 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 2652 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 2652 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 2652 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 28 ms 2652 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Execution timed out 2021 ms 2904 KB Time limit exceeded
7 Halted 0 ms 0 KB -