#include <bits/stdc++.h> #define fi first #define sc second #define pb push_back #define rep(i,p,k) for(int i=(p);i<(k);++i) #define forn(i,p,k) for(int i=(p);i<=(k);++i) #define forr(i,k,p) for(int i=(k)-1;i>=(p);--i) #define each(a,b) for(auto&a:b) #define all(v) begin(v), end(v) #define RET(smth) return void(cout<<(smth)<<'\n'); #define sz(v) (int)v.size() using namespace std; using pii = pair<int,int>; using ll = long long; using lll = __int128_t; using Vi = vector<int>; using ld = double; #ifdef DEBUG #include "debug.h" #else #define debug(...) ; #endif const ld eps = 1e-9; int main() { #ifndef DEBUG cin.tie(0) -> sync_with_stdio(0); #endif int n,t; cin >> n >> t; vector<ld> pr(n); for(auto &p : pr) cin >> p; sort(all(pr)); while(!pr.empty() && pr.back() == 1) { pr.pop_back(); t--; } reverse(all(pr)); while(!pr.empty() && pr.back() == 0) pr.pop_back(); n = sz(pr); if(t <= 0) { cout << 1 << '\n'; return 0; } if(t > n) { cout << 0 << '\n'; return 0; } vector<ld> poly(n+1); auto mul = [&](ld p1, ld p2, int deg) { auto a = p1*p2; auto b = p1 + p2 - 2*a; auto c = 1 - p1 - p2 + a; for(int i=deg;i>=0;i--) poly[i+2] = poly[i]*a + poly[i+1]*b + poly[i+2]*c; poly[1] = poly[0]*b + poly[1]*c; poly[0] *= c; }; ld res = 0; if(t == 1) res = pr[0]; if(t % 2) { poly[0] = 1 - pr[0]; poly[1] = pr[0]; } else { poly[0] = 1; } for(int i=t%2;i+1<n;i+=2) { mul(pr[i], pr[i+1], i); if(i + 2 >= t) { ld pp = 0; forn(j,(t+i+2)/2,i+2) pp += poly[j]; if(pp + 1e-7 < res) break; res = max(res,pp); // res = pp; } } cout << setprecision(9) << fixed << res << '\n'; 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 | #include <bits/stdc++.h> #define fi first #define sc second #define pb push_back #define rep(i,p,k) for(int i=(p);i<(k);++i) #define forn(i,p,k) for(int i=(p);i<=(k);++i) #define forr(i,k,p) for(int i=(k)-1;i>=(p);--i) #define each(a,b) for(auto&a:b) #define all(v) begin(v), end(v) #define RET(smth) return void(cout<<(smth)<<'\n'); #define sz(v) (int)v.size() using namespace std; using pii = pair<int,int>; using ll = long long; using lll = __int128_t; using Vi = vector<int>; using ld = double; #ifdef DEBUG #include "debug.h" #else #define debug(...) ; #endif const ld eps = 1e-9; int main() { #ifndef DEBUG cin.tie(0) -> sync_with_stdio(0); #endif int n,t; cin >> n >> t; vector<ld> pr(n); for(auto &p : pr) cin >> p; sort(all(pr)); while(!pr.empty() && pr.back() == 1) { pr.pop_back(); t--; } reverse(all(pr)); while(!pr.empty() && pr.back() == 0) pr.pop_back(); n = sz(pr); if(t <= 0) { cout << 1 << '\n'; return 0; } if(t > n) { cout << 0 << '\n'; return 0; } vector<ld> poly(n+1); auto mul = [&](ld p1, ld p2, int deg) { auto a = p1*p2; auto b = p1 + p2 - 2*a; auto c = 1 - p1 - p2 + a; for(int i=deg;i>=0;i--) poly[i+2] = poly[i]*a + poly[i+1]*b + poly[i+2]*c; poly[1] = poly[0]*b + poly[1]*c; poly[0] *= c; }; ld res = 0; if(t == 1) res = pr[0]; if(t % 2) { poly[0] = 1 - pr[0]; poly[1] = pr[0]; } else { poly[0] = 1; } for(int i=t%2;i+1<n;i+=2) { mul(pr[i], pr[i+1], i); if(i + 2 >= t) { ld pp = 0; forn(j,(t+i+2)/2,i+2) pp += poly[j]; if(pp + 1e-7 < res) break; res = max(res,pp); // res = pp; } } cout << setprecision(9) << fixed << res << '\n'; return 0; } |