oj.uz

Submission #722691

# Submission time Handle Problem Language Result Execution time Memory
722691 2023-04-12T16:36:09 Z HamletPetrosyan Boarding Passes (BOI22_passes) C++17
60 / 100
 1212 ms 668 KB 
/// -- -- ---- --- -- --
/// 12.04.2023 Wed 20:35
/// -- -- ---- --- -- --

#include <bits/stdc++.h>
using namespace std;
void abandoned_precalc();

#define pll pair<long long, long long>
#define all(a) (a).begin(), (a).end()
#define len(a) ((long long)(a).size())
#define add push_back
#define mkp make_pair
#define ll long long
#define fr first
#define sc second

const long long INF = 1000000000ll * 1000000003ll;
const long long MOD = 1000000007ll;
const int N = 2e5 + 5, G = 10;

string s;
ll ans4 = INF;

ll dp[(1 << G)];
ll asc[N], pref[N], suf[N];
ll cnt[N], sc;

int o(char x){ return x - 'A'; }

void solve(){
	cin >> s;
//	for(ll i = 0; i <= len(s); i++){
//		ans4 = min(ans4, i * (i - 1) + (len(s) - i) * (len(s) - i - 1));
//	}
//	cout << (double)ans4 / 4. << "\n";

	for(int i = 0; i < len(s); i++) asc[o(s[i])]++;
//	for(int i = 0; i <= G; i++) cout << asc[i] << " ";
//	cout << "\n";

	for(int mask = 1; mask < (1 << G); mask++){
		dp[mask] = INF;
		fill(cnt, cnt + G, 0); sc = 0;
		for(int i = len(s) - 1; ~i; i--){
			if(!(mask & (1 << o(s[i])))) continue;
			sc++; cnt[o(s[i])]++;
			suf[o(s[i])] += sc - cnt[o(s[i])];
			pref[o(s[i])] = 0;
		}
		for(int i = 0; i < G; i++){
			if(!(mask & (1 << i))) continue;
			dp[mask] = min(dp[mask], dp[mask ^ (1 << i)]
										+ suf[i] * 4
										+ cnt[i] * (cnt[i] - 1));
		}
		for(int i = 0, pc = 0; i < len(s); i++){
			if(!(mask & (1 << o(s[i])))) continue;
			suf[o(s[i])] -= sc - cnt[o(s[i])];
			sc--; cnt[o(s[i])]--; pc++;
			pref[o(s[i])] += pc - asc[o(s[i])] + cnt[o(s[i])];
			dp[mask] = min(dp[mask], dp[mask ^ (1 << o(s[i]))]
										+ (pref[o(s[i])] + suf[o(s[i])]) * 4
										+ cnt[o(s[i])] * (cnt[o(s[i])] - 1) + (asc[o(s[i])] - cnt[o(s[i])]) * (asc[o(s[i])] - cnt[o(s[i])] - 1));
		}
	}
	cout << (double)dp[(1 << G) - 1] / 4. << "\n";
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	int _ = 1;
	cout << fixed;
	cout.precision(9);

	abandoned_precalc();
	// cin >> _ ;
	while(_--) solve();
	return 0;
}

/// ---- - --------  ------ -------- -- - - -
/// just a reminder. ubuntu password is i o i
/// ---- - --------  ------ -------- -- - - -














void abandoned_precalc(){
	
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 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 1 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 14 ms 360 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 882 ms 620 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 1146 ms 648 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 1172 ms 668 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 1212 ms 660 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 2 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 2 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 2 ms 340 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 2 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 2 ms 340 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 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 328 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 2 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 2 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 2 ms 340 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 2 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 2 ms 340 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 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 328 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 2 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 2 ms 332 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 328 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 328 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 120 ms 372 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 119 ms 380 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 175 ms 376 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 125 ms 376 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 119 ms 340 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 115 ms 340 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 115 ms 368 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 119 ms 384 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 121 ms 372 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 118 ms 464 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 123 ms 376 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 118 ms 340 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 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 1 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 14 ms 360 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 882 ms 620 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 1146 ms 648 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 1172 ms 668 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 1212 ms 660 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 2 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 2 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 2 ms 340 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 2 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 2 ms 340 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 1 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 328 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 2 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 2 ms 332 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 328 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 328 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 120 ms 372 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 119 ms 380 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 175 ms 376 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 125 ms 376 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 119 ms 340 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 115 ms 340 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 115 ms 368 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 119 ms 384 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 121 ms 372 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 118 ms 464 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 123 ms 376 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 118 ms 340 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Incorrect 1 ms 336 KB 1st numbers differ - expected: '7.5000000000', found: '6.0000000000', error = '0.2000000000'
57 Halted 0 ms 0 KB -