#include <bits/stdc++.h> using namespace std; #define rep(i,a,n) for (int i=(a);i<(n);i++) #define per(i,a,n) for (int i=(n)-1;i>=(a);i--) #define pb push_back #define eb emplace_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((int)(x).size()) typedef vector<int> VI; typedef basic_string<int> BI; typedef long long ll; typedef pair<int,int> PII; typedef long double db; mt19937 mrand(1111); const ll mod=1000000007; int rnd(int x) { return mrand() % x;} ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;} // head const int N=201000; vector<db> mul(vector<db> a,vector<db> b) { vector<db> c(SZ(a)+SZ(b)-1,0); VI ib; rep(j,0,SZ(b)) if (fabs(b[j])>1e-18) ib.pb(j); rep(i,0,SZ(a)) if (fabs(a[i])>1e-18) { for (auto j:ib) c[i+j]+=a[i]*b[j]; } return c; } db ret[N],p[N]; int n,k; vector<db> solve(int l,int r,vector<db> prob,int vl) { int cl=0,cr=SZ(prob)-1; int len=r-l+1; while (cl<=cr&&2*(vl+cl+len)-r<k) cl++; db pwin=0; while (cl<=cr&&2*(vl+cr)-r>=k) pwin+=prob[cr],--cr; rep(i,l,r+1) ret[i]+=pwin; vl=vl+cl; //assert(cl<=cr); auto nprob=vector<db>(prob.begin()+cl,prob.begin()+cr+1); prob=nprob; if (l==r) { auto pr=vector<db>{1-p[l],p[l]}; auto nprob=mul(prob,pr); //for (auto x:nprob) cout<<x<<" "; cout<<vl<<"!!!\n"; rep(i,0,SZ(nprob)) if (2*(vl+i)-r>=k) ret[l]+=nprob[i]; return pr; } int md=(l+r)>>1; auto pl=solve(l,md,prob,vl); prob=mul(prob,pl); auto pr=solve(md+1,r,prob,vl); return mul(pl,pr); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin>>n>>k; rep(i,1,n+1) cin>>p[i]; sort(p+1,p+n+1); reverse(p+1,p+n+1); solve(1,n,vector<db>{1},0); db ans=*max_element(ret+1,ret+n+1); cout<<setiosflags(ios::fixed)<<setprecision(12)<<ans<<"\n"; }
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 | #include <bits/stdc++.h> using namespace std; #define rep(i,a,n) for (int i=(a);i<(n);i++) #define per(i,a,n) for (int i=(n)-1;i>=(a);i--) #define pb push_back #define eb emplace_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((int)(x).size()) typedef vector<int> VI; typedef basic_string<int> BI; typedef long long ll; typedef pair<int,int> PII; typedef long double db; mt19937 mrand(1111); const ll mod=1000000007; int rnd(int x) { return mrand() % x;} ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;} // head const int N=201000; vector<db> mul(vector<db> a,vector<db> b) { vector<db> c(SZ(a)+SZ(b)-1,0); VI ib; rep(j,0,SZ(b)) if (fabs(b[j])>1e-18) ib.pb(j); rep(i,0,SZ(a)) if (fabs(a[i])>1e-18) { for (auto j:ib) c[i+j]+=a[i]*b[j]; } return c; } db ret[N],p[N]; int n,k; vector<db> solve(int l,int r,vector<db> prob,int vl) { int cl=0,cr=SZ(prob)-1; int len=r-l+1; while (cl<=cr&&2*(vl+cl+len)-r<k) cl++; db pwin=0; while (cl<=cr&&2*(vl+cr)-r>=k) pwin+=prob[cr],--cr; rep(i,l,r+1) ret[i]+=pwin; vl=vl+cl; //assert(cl<=cr); auto nprob=vector<db>(prob.begin()+cl,prob.begin()+cr+1); prob=nprob; if (l==r) { auto pr=vector<db>{1-p[l],p[l]}; auto nprob=mul(prob,pr); //for (auto x:nprob) cout<<x<<" "; cout<<vl<<"!!!\n"; rep(i,0,SZ(nprob)) if (2*(vl+i)-r>=k) ret[l]+=nprob[i]; return pr; } int md=(l+r)>>1; auto pl=solve(l,md,prob,vl); prob=mul(prob,pl); auto pr=solve(md+1,r,prob,vl); return mul(pl,pr); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin>>n>>k; rep(i,1,n+1) cin>>p[i]; sort(p+1,p+n+1); reverse(p+1,p+n+1); solve(1,n,vector<db>{1},0); db ans=*max_element(ret+1,ret+n+1); cout<<setiosflags(ios::fixed)<<setprecision(12)<<ans<<"\n"; } |