# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
593119 | 2022-07-10T12:22:13 Z | MilosMilutinovic | Boarding Passes (BOI22_passes) | C++14 | 2000 ms | 11024 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<int>>> cntL(A, vector<vector<int>>(A)); vector<vector<vector<int>>> cntR(A, vector<vector<int>>(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; } } } 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; } } } 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
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 402 ms | 852 KB | Output is correct |
2 | Correct | 8 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 | 433 ms | 980 KB | Output is correct |
6 | Execution timed out | 2081 ms | 11024 KB | Time limit exceeded |
7 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 18 ms | 852 KB | Output is correct |
2 | Correct | 60 ms | 852 KB | Output is correct |
3 | Incorrect | 94 ms | 852 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 18 ms | 852 KB | Output is correct |
2 | Correct | 60 ms | 852 KB | Output is correct |
3 | Incorrect | 94 ms | 852 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 402 ms | 852 KB | Output is correct |
2 | Correct | 8 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 | 433 ms | 980 KB | Output is correct |
6 | Execution timed out | 2081 ms | 11024 KB | Time limit exceeded |
7 | Halted | 0 ms | 0 KB | - |