# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
593131 | 2022-07-10T12:32:45 Z | MilosMilutinovic | Boarding Passes (BOI22_passes) | C++14 | 2000 ms | 20368 KB |
/** * author: wxhtzdy * created: 10.07.2022 13:22:51 **/ #include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); string s; cin >> s; int n = (int) s.size(); vector<int> a(n); for (int i = 0; i < n; i++) { a[i] = (int) (s[i] - 'A'); } const int A = 15; vector<vector<int>> ids(A); for (int i = 0; i < n; i++) { ids[a[i]].push_back(i); } vector<vector<vector<long long>>> cntL(A, vector<vector<long long>>(A)); vector<vector<vector<long long>>> cntR(A, vector<vector<long long>>(A)); for (int i = 0; i < A; i++) { int sz = (int) ids[i].size(); for (int j = 0; j < A; j++) { cntL[i][j].resize(sz); int ptr = 0; for (int k = 0; k < sz; k++) { while (ptr < (int) ids[j].size() && ids[j][ptr] < ids[i][k]) { ptr += 1; } cntL[i][j][k] = ptr; if (k > 0) { cntL[i][j][k] += cntL[i][j][k - 1]; } } } } for (int i = 0; i < A; i++) { int sz = (int) ids[i].size(); for (int j = 0; j < A; j++) { cntR[i][j].resize(sz); int ptr = (int) ids[j].size() - 1; for (int k = sz - 1; k >= 0; k--) { while (ptr >= 0 && ids[j][ptr] > ids[i][k]) { ptr -= 1; } cntR[i][j][k] = (int) ids[j].size() - 1 - ptr; if (k < sz - 1) { cntR[i][j][k] += cntR[i][j][k + 1]; } } } } vector<long double> dp(1 << A, 1e14); dp[0] = 0; for (int s = 0; s < (1 << A); s++) { for (int i = 0; i < A; i++) { if (s >> i & 1) { continue; } if (ids[i].empty()) { dp[s | (1 << i)] = min(dp[s | (1 << i)], dp[s]); continue; } auto Calc = [&](int id) { int L = id + 1; int R = (int) ids[i].size() - id - 1; long double res = (double) (L * 1LL * (L - 1) / 2) / 2.0; res += (R * 1LL * (R - 1) / 2) / 2.0; for (int j = 0; j < A; j++) { if (s >> j & 1) { if (id >= 0) { res += cntL[i][j][id]; } if (id + 1 < (int) ids[i].size()) { res += cntR[i][j][id + 1]; } } } return res; }; int low = -1, high = (int) ids[i].size() - 2, at = high + 1; while (low <= high) { int mid = (low + high) >> 1; if (Calc(mid) > Calc(mid + 1)) { low = mid + 1; } else { at = mid; high = mid - 1; } } for (int p = -1; p < (int) ids[i].size(); p++) { dp[s | (1 << i)] = min(dp[s | (1 << i)], dp[s] + Calc(p)); } } } int zzz = dp[(1 << A) - 1]; if (dp[(1 << A) - 1] != (double) zzz) { cout << fixed << setprecision(1) << dp[(1 << A) - 1]; } else { cout << fixed << setprecision(0) << dp[(1 << A) - 1]; } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 391 ms | 980 KB | Output is correct |
2 | Correct | 7 ms | 852 KB | Output is correct |
3 | Correct | 11 ms | 852 KB | Output is correct |
4 | Correct | 13 ms | 852 KB | Output is correct |
5 | Correct | 446 ms | 980 KB | Output is correct |
6 | Execution timed out | 2080 ms | 20368 KB | Time limit exceeded |
7 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 832 KB | Output is correct |
2 | Correct | 61 ms | 852 KB | Output is correct |
3 | Correct | 96 ms | 852 KB | Output is correct |
4 | Correct | 93 ms | 852 KB | Output is correct |
5 | Correct | 83 ms | 852 KB | Output is correct |
6 | Correct | 29 ms | 852 KB | Output is correct |
7 | Correct | 80 ms | 852 KB | Output is correct |
8 | Correct | 53 ms | 852 KB | Output is correct |
9 | Correct | 56 ms | 852 KB | Output is correct |
10 | Correct | 55 ms | 852 KB | Output is correct |
11 | Correct | 54 ms | 852 KB | Output is correct |
12 | Correct | 56 ms | 852 KB | Output is correct |
13 | Correct | 53 ms | 852 KB | Output is correct |
14 | Correct | 55 ms | 852 KB | Output is correct |
15 | Correct | 54 ms | 852 KB | Output is correct |
16 | Correct | 54 ms | 852 KB | Output is correct |
17 | Correct | 57 ms | 852 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 832 KB | Output is correct |
2 | Correct | 61 ms | 852 KB | Output is correct |
3 | Correct | 96 ms | 852 KB | Output is correct |
4 | Correct | 93 ms | 852 KB | Output is correct |
5 | Correct | 83 ms | 852 KB | Output is correct |
6 | Correct | 29 ms | 852 KB | Output is correct |
7 | Correct | 80 ms | 852 KB | Output is correct |
8 | Correct | 53 ms | 852 KB | Output is correct |
9 | Correct | 56 ms | 852 KB | Output is correct |
10 | Correct | 55 ms | 852 KB | Output is correct |
11 | Correct | 54 ms | 852 KB | Output is correct |
12 | Correct | 56 ms | 852 KB | Output is correct |
13 | Correct | 53 ms | 852 KB | Output is correct |
14 | Correct | 55 ms | 852 KB | Output is correct |
15 | Correct | 54 ms | 852 KB | Output is correct |
16 | Correct | 54 ms | 852 KB | Output is correct |
17 | Correct | 57 ms | 852 KB | Output is correct |
18 | Correct | 19 ms | 852 KB | Output is correct |
19 | Correct | 61 ms | 832 KB | Output is correct |
20 | Correct | 94 ms | 832 KB | Output is correct |
21 | Correct | 94 ms | 852 KB | Output is correct |
22 | Correct | 75 ms | 852 KB | Output is correct |
23 | Correct | 29 ms | 852 KB | Output is correct |
24 | Correct | 82 ms | 852 KB | Output is correct |
25 | Correct | 51 ms | 852 KB | Output is correct |
26 | Correct | 53 ms | 832 KB | Output is correct |
27 | Correct | 56 ms | 852 KB | Output is correct |
28 | Correct | 58 ms | 852 KB | Output is correct |
29 | Correct | 58 ms | 852 KB | Output is correct |
30 | Correct | 59 ms | 828 KB | Output is correct |
31 | Correct | 56 ms | 852 KB | Output is correct |
32 | Correct | 57 ms | 852 KB | Output is correct |
33 | Correct | 55 ms | 852 KB | Output is correct |
34 | Correct | 64 ms | 852 KB | Output is correct |
35 | Execution timed out | 2075 ms | 3284 KB | Time limit exceeded |
36 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 391 ms | 980 KB | Output is correct |
2 | Correct | 7 ms | 852 KB | Output is correct |
3 | Correct | 11 ms | 852 KB | Output is correct |
4 | Correct | 13 ms | 852 KB | Output is correct |
5 | Correct | 446 ms | 980 KB | Output is correct |
6 | Execution timed out | 2080 ms | 20368 KB | Time limit exceeded |
7 | Halted | 0 ms | 0 KB | - |