oj.uz

Submission #829466

# Submission time Handle Problem Language Result Execution time Memory
829466 2023-08-18T11:03:07 Z QwertyPi Boarding Passes (BOI22_passes) C++14
100 / 100
 597 ms 564600 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

int f(int x){
	return x * (x - 1) / 2;
}

const int G = 15;
const int N = 1e5 + 11;
int L[G][G][N], R[G][G][N];
int cL[G][N], cR[G][N];

int s0[G][G][N], s1[G][N];
int dp[1 << G];

int f(int mask, int j, int x){
	int c = cL[j][x] + cR[j][x];
	for(int k = 0; k < G; k++){
		if(j != k && (mask & (1 << k))){
			c += L[k][j][x] + R[k][j][x];
		}
	}
	return c;
}

int g(int mask, int j, int x){
	int c = s1[j][x];
	for(int k = 0; k < G; k++){
		if(j != k && (mask & (1 << k))){
			c += s0[k][j][x];
		}
	}
	return c;
}

int32_t main(){
	string s; cin >> s;
	int n = s.size();
	for(int i = 0; i < G; i++){
		for(int j = 0; j < G; j++){
			// add char i then char j
			L[i][j][0] = 0; int m = 0;
			for(int k = 0; k < n; k++){
				s0[i][j][k] += m;
				if(s[k] == 'A' + i){
					m += 2;
					L[i][j][k + 1] = L[i][j][k];
				}else if(s[k] == 'A' + j){
					L[i][j][k + 1] = L[i][j][k] + m;
				}else{
					L[i][j][k + 1] = L[i][j][k];
				}
			}
			R[i][j][n] = 0; m = 0;
			for(int k = n - 1; k >= 0; k--){
				s0[i][j][k] -= m;
				if(s[k] == 'A' + i){
					m += 2;
					R[i][j][k] = R[i][j][k + 1];
				}else if(s[k] == 'A' + j){
					R[i][j][k] = R[i][j][k + 1] + m;
				}else{
					R[i][j][k] = R[i][j][k + 1];
				}
			}
		}
	}

	for(int i = 0; i < G; i++){
		cL[i][0] = 0; int m = 0;
		for(int j = 0; j < n; j++){
			s1[i][j] += m;
			if(s[j] == 'A' + i){
				cL[i][j + 1] = cL[i][j] + m; m++;
			}else{
				cL[i][j + 1] = cL[i][j];
			}
		}
		cR[i][n] = 0; m = 0;
		for(int j = n - 1; j >= 0; j--){
			s1[i][j] -= m;
			if(s[j] == 'A' + i){
				cR[i][j] = cR[i][j + 1] + m; m++;
			}else{
				cR[i][j] = cR[i][j + 1];
			}
		}
	}

	dp[0] = 0; fill(dp + 1, dp + (1 << G), 1LL << 60);
	for(int mask = 1; mask < (1 << G); mask++){
		for(int j = 0; j < G; j++){
			if(mask & (1 << j)){
				int cost = min(f(mask, j, 0), f(mask, j, n));
				int lo = 0, hi = n;
				while(lo + 1 < hi){
					int mid = (lo + hi) / 2;
					int c = g(mask, j, mid);
					if(c < 0) lo = mid;
					else hi = mid;
				}
				for(int x = lo; x <= hi; x++){
					int c = f(mask, j, x);
					cost = min(cost, c);
				}
				dp[mask] = min(dp[mask], dp[mask - (1 << j)] + cost);
			}
		}
	}
	cout << setprecision(10) << fixed << ((long double) dp[(1 << G) - 1] / 2) << endl;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 9492 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 51 ms 4436 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 53 ms 4436 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 55 ms 4528 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 108 ms 10188 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 416 ms 446988 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 477 ms 532684 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 497 ms 564512 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 463 ms 564392 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 4540 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 92 ms 4924 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 104 ms 4960 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 93 ms 4948 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 88 ms 4972 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 73 ms 4564 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 90 ms 4820 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 84 ms 4620 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 83 ms 4624 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 85 ms 4564 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 89 ms 4624 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 83 ms 4628 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 77 ms 4620 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 79 ms 4620 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 80 ms 4564 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 80 ms 4564 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 79 ms 4620 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 4540 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 92 ms 4924 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 104 ms 4960 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 93 ms 4948 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 88 ms 4972 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 73 ms 4564 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 90 ms 4820 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 84 ms 4620 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 83 ms 4624 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 85 ms 4564 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 89 ms 4624 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 83 ms 4628 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 77 ms 4620 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 79 ms 4620 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 80 ms 4564 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 80 ms 4564 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 79 ms 4620 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 80 ms 4532 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 84 ms 4968 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 93 ms 4964 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 111 ms 4952 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 106 ms 4968 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 69 ms 4564 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 92 ms 4844 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 95 ms 4624 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 90 ms 4620 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 88 ms 4628 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 81 ms 4628 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 86 ms 4628 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 79 ms 4620 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 82 ms 4624 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 79 ms 4620 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 80 ms 4564 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 81 ms 4564 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 176 ms 60804 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 160 ms 60692 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 193 ms 60620 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 244 ms 60700 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 169 ms 60616 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 158 ms 60348 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 174 ms 59516 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 193 ms 59468 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 167 ms 59472 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 190 ms 59508 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 183 ms 59508 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 193 ms 59504 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 9492 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 51 ms 4436 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 53 ms 4436 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 55 ms 4528 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 108 ms 10188 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 416 ms 446988 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 477 ms 532684 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 497 ms 564512 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 463 ms 564392 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 68 ms 4540 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 92 ms 4924 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 104 ms 4960 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 93 ms 4948 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 88 ms 4972 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 73 ms 4564 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 90 ms 4820 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 84 ms 4620 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 83 ms 4624 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 85 ms 4564 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 89 ms 4624 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 83 ms 4628 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 77 ms 4620 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 79 ms 4620 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 80 ms 4564 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 80 ms 4564 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 79 ms 4620 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 80 ms 4532 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 84 ms 4968 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 93 ms 4964 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 111 ms 4952 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 106 ms 4968 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 69 ms 4564 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 92 ms 4844 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 95 ms 4624 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 90 ms 4620 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 88 ms 4628 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 81 ms 4628 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 86 ms 4628 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 79 ms 4620 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 82 ms 4624 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 79 ms 4620 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 80 ms 4564 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 81 ms 4564 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 176 ms 60804 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 160 ms 60692 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 193 ms 60620 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 244 ms 60700 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 169 ms 60616 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 158 ms 60348 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 174 ms 59516 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 193 ms 59468 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 167 ms 59472 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 190 ms 59508 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 183 ms 59508 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 193 ms 59504 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 78 ms 4572 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 82 ms 4636 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 102 ms 9504 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 41 ms 4436 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 51 ms 4520 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 58 ms 4532 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 102 ms 10068 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 454 ms 447076 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 487 ms 532688 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 482 ms 564544 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 484 ms 564512 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 64 ms 4544 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 81 ms 4976 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 97 ms 4968 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 110 ms 4948 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 91 ms 4924 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 79 ms 4556 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 92 ms 4820 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 84 ms 4624 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 95 ms 4624 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 94 ms 4624 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 88 ms 4628 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 87 ms 4628 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 83 ms 4632 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 81 ms 4628 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 96 ms 4628 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 91 ms 4628 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 93 ms 4692 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 157 ms 60600 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 180 ms 60636 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 201 ms 60704 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 245 ms 60700 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 169 ms 60704 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 162 ms 60460 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 197 ms 59532 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 182 ms 59508 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 181 ms 59508 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 201 ms 59504 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 213 ms 59512 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 190 ms 59432 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 521 ms 564396 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 89 ms 4660 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 597 ms 564600 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 403 ms 564520 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 85 ms 4600 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 401 ms 564404 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 468 ms 564424 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 454 ms 564512 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 445 ms 564432 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 485 ms 564416 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 456 ms 564516 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 482 ms 564516 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 492 ms 564444 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 467 ms 564516 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'