# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
829446 | 2023-08-18T10:46:28 Z | QwertyPi | Boarding Passes (BOI22_passes) | C++14 | 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; }
# | 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 | - |
# | 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' |
# | 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 | - |
# | 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 | - |