# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
647595 | 2022-10-03T09:21:37 Z | Pety | Boarding Passes (BOI22_passes) | C++14 | 5 ms | 4940 KB |
#include <bits/stdc++.h> #define ll long long using namespace std; const double INF = 1e12; const int MOD = 1e9 + 7; int n, g, sum[12][100002]; vector<int>poz[10]; vector<double>calc[10][10]; double dp[(1 << 10)]; string s; double expected(int n) { if (n < 2) return 0.0; return (double)n * (n - 1) / 4; } int main () { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> s; int n = s.size(); s = '#' + s; for (int i = 0; i < 10; i++) poz[i].push_back(0); int g = 0; for (int i = 1; i <= n; i++) { g = max(g, s[i] - 'A' + 1); poz[s[i] - 'A'].push_back(i); for (int j = 0; j < 10; j++) sum[j][i] = sum[j][i - 1] + (s[i] - 'A' == j); } for (int i = 0; i < g; i++) { for (int j = 0; j < g; j++) { if (i == j) continue; calc[i][j].resize(poz[i].size() + 1); ll pas = 0; for (int k = 0; k < poz[i].size(); k++) { calc[i][j][k] += pas; if (k + 1 < poz[i].size()) pas += sum[j][poz[i][k + 1]]; } pas = 0; for (int k = poz[i].size() - 1; k >= 0; k--) { calc[i][j][k] += pas; pas += sum[j][n] - sum[j][poz[i][k] - 1]; } } } for (int mask = 0; mask < (1 << g); mask++) dp[mask] = INF; dp[0] = 0; for (int mask = 0; mask < (1 << g); mask++) { for (int i = 0; i < g; i++) if (!(mask & (1 << i))) { double cur = INF; for (int k = 0; k <= poz[i].size(); k++) { double aux = expected(k) + expected(poz[i].size() - 1 - k); for (int j = 0; j < g; j++) if (mask & (1 << j)) aux += calc[i][j][k]; cur = min(cur, aux); } dp[mask ^ (1 << i)] = min(dp[mask] + cur, dp[mask ^ (1 << i)]); } } cout << fixed << setprecision(7) << dp[(1 << g) - 1]; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | found '100800.5000000000', expected '100800.5000000000', error '0.0000000000' |
2 | Correct | 1 ms | 340 KB | found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
3 | Correct | 1 ms | 340 KB | found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
4 | Correct | 0 ms | 340 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
5 | Correct | 0 ms | 340 KB | found '124002.0000000000', expected '124002.0000000000', error '0.0000000000' |
6 | Correct | 4 ms | 3912 KB | found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000' |
7 | Correct | 4 ms | 4680 KB | found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000' |
8 | Correct | 5 ms | 4940 KB | found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000' |
9 | Correct | 5 ms | 4940 KB | found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000' |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 340 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
2 | Correct | 1 ms | 340 KB | found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
3 | Incorrect | 1 ms | 340 KB | 1st numbers differ - expected: '1023.0000000000', found: '349.5000000000', error = '0.6583577713' |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 340 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
2 | Correct | 1 ms | 340 KB | found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
3 | Incorrect | 1 ms | 340 KB | 1st numbers differ - expected: '1023.0000000000', found: '349.5000000000', error = '0.6583577713' |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | found '100800.5000000000', expected '100800.5000000000', error '0.0000000000' |
2 | Correct | 1 ms | 340 KB | found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
3 | Correct | 1 ms | 340 KB | found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
4 | Correct | 0 ms | 340 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
5 | Correct | 0 ms | 340 KB | found '124002.0000000000', expected '124002.0000000000', error '0.0000000000' |
6 | Correct | 4 ms | 3912 KB | found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000' |
7 | Correct | 4 ms | 4680 KB | found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000' |
8 | Correct | 5 ms | 4940 KB | found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000' |
9 | Correct | 5 ms | 4940 KB | found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000' |
10 | Correct | 0 ms | 340 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
11 | Correct | 1 ms | 340 KB | found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
12 | Incorrect | 1 ms | 340 KB | 1st numbers differ - expected: '1023.0000000000', found: '349.5000000000', error = '0.6583577713' |
13 | Halted | 0 ms | 0 KB | - |