// Author: Bartek Knapik #include <cstdio> #include <vector> using namespace std; const int MAX_N = 50000 + 9; double p[MAX_N], tmp[MAX_N]; vector<double> tot[MAX_N]; int n, t; void sort(int begin, int end) { if (end - begin <= 1) return; int mid = (begin + end) / 2; sort(begin, mid); sort(mid, end); int a = begin; int b = mid; int c = 0; while (a < mid && b < end) { if (p[a] > p[b]) tmp[c++] = p[a++]; else tmp[c++] = p[b++]; } while (a < mid) tmp[c++] = p[a++]; while (b < end) tmp[c++] = p[b++]; c = 0; while (begin < end) p[begin++] = tmp[c++]; } int main() { scanf("%d%d", &n, &t); for (int i = 0; i < n; ++i) scanf("%lf", &p[i]); sort(0, n); for (int i = 0; i <= n; ++i) tot[i].resize(MAX_N); for (int i = 0; i <= n; ++i) tot[i][0] = 1.0; for (int i = 1; i <= n; ++i) for (int f = 0; f <= i; ++f) { tot[i][f] = tot[i-1][f] * p[i-1] ; if (f) tot[i][f] += tot[i-1][f-1] * (1 - p[i-1]); } double ans, tmp_ans; ans = 0.0; for (int i = t; i <= n; ++i) { tmp_ans = 0.0; for (int f = 0; 2 * f <= i - t; ++f) tmp_ans += tot[i][f]; if (tmp_ans > ans) ans = tmp_ans; } printf("%.20lf\n", ans); 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 | // Author: Bartek Knapik #include <cstdio> #include <vector> using namespace std; const int MAX_N = 50000 + 9; double p[MAX_N], tmp[MAX_N]; vector<double> tot[MAX_N]; int n, t; void sort(int begin, int end) { if (end - begin <= 1) return; int mid = (begin + end) / 2; sort(begin, mid); sort(mid, end); int a = begin; int b = mid; int c = 0; while (a < mid && b < end) { if (p[a] > p[b]) tmp[c++] = p[a++]; else tmp[c++] = p[b++]; } while (a < mid) tmp[c++] = p[a++]; while (b < end) tmp[c++] = p[b++]; c = 0; while (begin < end) p[begin++] = tmp[c++]; } int main() { scanf("%d%d", &n, &t); for (int i = 0; i < n; ++i) scanf("%lf", &p[i]); sort(0, n); for (int i = 0; i <= n; ++i) tot[i].resize(MAX_N); for (int i = 0; i <= n; ++i) tot[i][0] = 1.0; for (int i = 1; i <= n; ++i) for (int f = 0; f <= i; ++f) { tot[i][f] = tot[i-1][f] * p[i-1] ; if (f) tot[i][f] += tot[i-1][f-1] * (1 - p[i-1]); } double ans, tmp_ans; ans = 0.0; for (int i = t; i <= n; ++i) { tmp_ans = 0.0; for (int f = 0; 2 * f <= i - t; ++f) tmp_ans += tot[i][f]; if (tmp_ans > ans) ans = tmp_ans; } printf("%.20lf\n", ans); return 0; } |