oj.uz

Submission #829446

# Submission time Handle Problem Language Result Execution time Memory
829446 2023-08-18T10:46:28 Z QwertyPi Boarding Passes (BOI22_passes) C++14
25 / 100
 2000 ms 298260 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 dp[1 << G];
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++){
				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--){
				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++){
			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--){
			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 = 1LL << 60;
				for(int x = 0; x <= n; 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];
						}
					}
					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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1723 ms 6580 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 28 ms 3156 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 35 ms 3156 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 40 ms 3212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1810 ms 6960 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Execution timed out 2091 ms 298260 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 3220 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 222 ms 3588 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 212 ms 3540 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 235 ms 3580 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 234 ms 3540 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 69 ms 3236 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 196 ms 3540 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 104 ms 3308 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 97 ms 3308 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 94 ms 3252 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 94 ms 3284 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 97 ms 3284 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 93 ms 3284 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 97 ms 3312 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 89 ms 3284 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 92 ms 3284 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 99 ms 3308 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 3220 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 222 ms 3588 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 212 ms 3540 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 235 ms 3580 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 234 ms 3540 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 69 ms 3236 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 196 ms 3540 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 104 ms 3308 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 97 ms 3308 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 94 ms 3252 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 94 ms 3284 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 97 ms 3284 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 93 ms 3284 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 97 ms 3312 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 89 ms 3284 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 92 ms 3284 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 99 ms 3308 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 57 ms 3220 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 219 ms 3588 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 212 ms 3588 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 215 ms 3580 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 224 ms 3592 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 65 ms 3240 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 199 ms 3540 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 98 ms 3284 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 97 ms 3304 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 86 ms 3308 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 95 ms 3304 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 100 ms 3284 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 105 ms 3308 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 96 ms 3312 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 93 ms 3308 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 94 ms 3308 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 103 ms 3284 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Execution timed out 2078 ms 40644 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1723 ms 6580 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 28 ms 3156 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 35 ms 3156 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 40 ms 3212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1810 ms 6960 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Execution timed out 2091 ms 298260 KB Time limit exceeded
7 Halted 0 ms 0 KB -