#include <bits/stdc++.h> using std::cin, std::cout; using i32 = int; using u32 = unsigned int; using i64 = long long; using u64 = unsigned long long; const char endl = '\n'; const int MAX_N = 50005; const int SPLIT = 24; // const int MAX_N = 1000; // const int SPLIT = 2; double chances[MAX_N]; double memo[MAX_N / SPLIT + 3][MAX_N]; double prob(int k, int n) { if (k == 0) return 1; else if (n == 0) return 0; else if (k > n) return 0; else return chances[n - 1] * prob(k - 1, n - 1) + (1 - chances[n - 1]) * prob(k, n - 1); } double tempprob[SPLIT][MAX_N]; void gen_probs(int max_n, int max_k, int start_k = 1, int start_n = 1) { for (int n = start_n; n <= max_n; n++) { double *currprob = tempprob[n % SPLIT]; double *prevprob = tempprob[(n - 1 + SPLIT) % SPLIT]; currprob[0] = 1; for (int k = std::max(1, start_k); k <= max_k; k++) { currprob[k] = chances[n - 1] * prevprob[k - 1] + (1 - chances[n - 1]) * prevprob[k]; } if (n % SPLIT == 0) { std::ranges::copy(currprob, currprob + MAX_N, memo[n / SPLIT]); } } } double fill_in_prob(int k, int n) { int start_n = n - n % SPLIT; int start_k = k - n % SPLIT; std::ranges::copy(memo[start_n / SPLIT] + std::max(0, start_k), memo[start_n / SPLIT] + k + 1, tempprob[0] + std::max(0, start_k)); gen_probs(n, k, start_k + 1, start_n + 1); // add one to pull from 0 return tempprob[n % SPLIT][k]; } int main() { std::ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); int n, cnt; cin >> n >> cnt; for (int i = 0; i < n; i++) { cin >> chances[i]; } std::ranges::sort(chances | std::views::take(n), std::greater{}); memo[0][0] = 1; tempprob[0][0] = 1; gen_probs(n, n); double max = 0; for (int questions = 0; questions <= n; questions++) { int wins_needed = (cnt + questions + 1) / 2; if (wins_needed > questions) continue; double res = fill_in_prob(wins_needed, questions); // cout << questions << ':' << res << ' '; if (res > max) max = res; } cout << std::fixed << std::setprecision(19) << max; return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 | #include <bits/stdc++.h> using std::cin, std::cout; using i32 = int; using u32 = unsigned int; using i64 = long long; using u64 = unsigned long long; const char endl = '\n'; const int MAX_N = 50005; const int SPLIT = 24; // const int MAX_N = 1000; // const int SPLIT = 2; double chances[MAX_N]; double memo[MAX_N / SPLIT + 3][MAX_N]; double prob(int k, int n) { if (k == 0) return 1; else if (n == 0) return 0; else if (k > n) return 0; else return chances[n - 1] * prob(k - 1, n - 1) + (1 - chances[n - 1]) * prob(k, n - 1); } double tempprob[SPLIT][MAX_N]; void gen_probs(int max_n, int max_k, int start_k = 1, int start_n = 1) { for (int n = start_n; n <= max_n; n++) { double *currprob = tempprob[n % SPLIT]; double *prevprob = tempprob[(n - 1 + SPLIT) % SPLIT]; currprob[0] = 1; for (int k = std::max(1, start_k); k <= max_k; k++) { currprob[k] = chances[n - 1] * prevprob[k - 1] + (1 - chances[n - 1]) * prevprob[k]; } if (n % SPLIT == 0) { std::ranges::copy(currprob, currprob + MAX_N, memo[n / SPLIT]); } } } double fill_in_prob(int k, int n) { int start_n = n - n % SPLIT; int start_k = k - n % SPLIT; std::ranges::copy(memo[start_n / SPLIT] + std::max(0, start_k), memo[start_n / SPLIT] + k + 1, tempprob[0] + std::max(0, start_k)); gen_probs(n, k, start_k + 1, start_n + 1); // add one to pull from 0 return tempprob[n % SPLIT][k]; } int main() { std::ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); int n, cnt; cin >> n >> cnt; for (int i = 0; i < n; i++) { cin >> chances[i]; } std::ranges::sort(chances | std::views::take(n), std::greater{}); memo[0][0] = 1; tempprob[0][0] = 1; gen_probs(n, n); double max = 0; for (int questions = 0; questions <= n; questions++) { int wins_needed = (cnt + questions + 1) / 2; if (wins_needed > questions) continue; double res = fill_in_prob(wins_needed, questions); // cout << questions << ':' << res << ' '; if (res > max) max = res; } cout << std::fixed << std::setprecision(19) << max; return 0; } |