oj.uz

Submission #604027

# Submission time Handle Problem Language Result Execution time Memory
604027 2022-07-24T15:32:45 Z MohamedAhmed04 Boarding Passes (BOI22_passes) C++14
60 / 100
 1248 ms 4212 KB 
#include <bits/stdc++.h>

using namespace std ;

const int MAX = 1e5 + 10 ;

int arr[MAX] , mark[MAX] ;
int n ;

long double pref[MAX] , suff[MAX] ;

string s ;

vector<int>occ[30] ;

long double dp[MAX] ;
int freq[30] , last[30] ;

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>s ;
	n = s.size() ;
	for(int i = 0 ; i < n ; ++i)
		occ[s[i]-'A'].push_back(i) ;
	for(int mask = 1 ; mask < (1 << 10) ; ++mask)
	{
		dp[mask] = 1e18 ;
		for(int c = 0 ; c < 10 ; ++c)
			freq[c] = 0 , last[c] = -1 ;
		long double cnt = 0 ;
		for(int i = 0 ; i < n ; ++i)
		{
			int c = s[i] - 'A' ;
			if((!(mask & (1 << c))))
				continue ;
			pref[i] = (cnt - freq[c]) + 0.5 * freq[c] ;
			if(last[c] != -1)
				pref[i] += pref[last[c]] ;
			++cnt , freq[c]++ , last[c] = i ;
		}
		for(int c = 0 ; c < 10 ; ++c)
			freq[c] = 0 , last[c] = -1 ;
		cnt = 0 ;
		for(int i = n-1 ; i >= 0 ; --i)
		{
			int c = s[i] - 'A' ;
			if((!(mask & (1 << c))))
				continue ;
			suff[i] = (cnt - freq[c]) + 0.5 * freq[c] ;
			if(last[c] != -1)
				suff[i] += suff[last[c]] ;
			++cnt , freq[c]++ , last[c] = i ;
		}
		for(int c = 0 ; c < 10 ; ++c)
		{
			if((!(mask & (1 << c))))
				continue ;
			if(!occ[c].size())
			{
				dp[mask] = min(dp[mask] , dp[mask ^ (1 << c)]) ;
				continue ;
			}
			int sz = occ[c].size() ;
			long double Min = min(pref[occ[c][sz-1]] , suff[occ[c][0]]) ;
			for(int i = 0 ; i < sz-1 ; ++i)
				Min = min(Min , pref[occ[c][i]] + suff[occ[c][i+1]]) ;
			dp[mask] = min(dp[mask] , dp[mask ^ (1 << c)] + Min) ;
		}
	}
	return cout<<fixed<<setprecision(12)<<dp[(1 << 10)-1]<<"\n" , 0 ;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 340 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 340 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 16 ms 412 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 928 ms 3440 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 1237 ms 4028 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 1248 ms 4200 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 1186 ms 4212 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 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 3 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 4 ms 340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 2 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 3 ms 352 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 340 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 2 ms 340 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 340 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 340 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 340 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 340 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 340 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 340 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 2 ms 340 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 340 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 340 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 340 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 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 3 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 4 ms 340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 2 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 3 ms 352 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 340 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 2 ms 340 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 340 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 340 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 340 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 340 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 340 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 340 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 2 ms 340 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 340 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 340 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 340 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 2 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 2 ms 340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 3 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 2 ms 340 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 1 ms 340 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 2 ms 340 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 1 ms 340 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 1 ms 340 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 1 ms 340 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 340 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 1 ms 340 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 1 ms 340 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 1 ms 340 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 1 ms 340 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 1 ms 340 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 1 ms 340 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 113 ms 784 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 136 ms 776 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 185 ms 756 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 108 ms 680 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 110 ms 800 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 136 ms 728 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 109 ms 772 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 107 ms 880 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 120 ms 760 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 110 ms 752 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 141 ms 756 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 118 ms 884 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 340 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 340 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 16 ms 412 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 928 ms 3440 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 1237 ms 4028 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 1248 ms 4200 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 1186 ms 4212 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 1 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 3 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 4 ms 340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 2 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 3 ms 352 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 1 ms 340 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 2 ms 340 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 1 ms 340 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 1 ms 340 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 1 ms 340 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 1 ms 340 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 1 ms 340 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 1 ms 340 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 2 ms 340 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 1 ms 340 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 1 ms 340 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 1 ms 340 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 1 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 2 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 2 ms 340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 3 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 2 ms 340 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 1 ms 340 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 2 ms 340 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 1 ms 340 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 1 ms 340 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 1 ms 340 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 1 ms 340 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 1 ms 340 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 1 ms 340 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 1 ms 340 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 1 ms 340 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 1 ms 340 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 1 ms 340 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 113 ms 784 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 136 ms 776 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 185 ms 756 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 108 ms 680 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 110 ms 800 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 136 ms 728 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 109 ms 772 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 107 ms 880 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 120 ms 760 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 110 ms 752 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 141 ms 756 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 118 ms 884 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Incorrect 1 ms 340 KB 1st numbers differ - expected: '7.5000000000', found: '6.0000000000', error = '0.2000000000'
57 Halted 0 ms 0 KB -