#include<bits/stdc++.h> using namespace std; typedef long long ll; #define fi first #define se second const int N=5e5+5; const int mg=1000; const ll mod=998244353; int n,t; typedef long double ld; ld dp[100005]; ld p[50005]; int main(){ ios::sync_with_stdio(false); cin >> n >> t; for(int i=0; i<=n ;i++) dp[i]=0; dp[0]=1; for(int i=1; i<=n ;i++){ cin >> p[i]; } sort(p+1,p+n+1);reverse(p+1,p+n+1); int l=0,r=0; ld win=0; ld best=0; ld e=0; for(int i=1; i<=n ;i++){ e+=p[i]; for(int j=r+1; j>=l ;j--){ dp[j]=dp[j]*(1-p[i])+dp[j-1]*p[i]; } ++r; while(l<e-mg){ if(l*2-i>=t) win+=dp[l]; dp[l++]=0; } while(r>e+mg){ if(r*2-i>=t) win+=dp[r]; dp[r--]=0; } ld cur=win; for(int j=l; j<=r ;j++){ if(j*2-i>=t) cur+=dp[j]; } best=max(best,cur); } cout << fixed << setprecision(20) << best << '\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 | #include<bits/stdc++.h> using namespace std; typedef long long ll; #define fi first #define se second const int N=5e5+5; const int mg=1000; const ll mod=998244353; int n,t; typedef long double ld; ld dp[100005]; ld p[50005]; int main(){ ios::sync_with_stdio(false); cin >> n >> t; for(int i=0; i<=n ;i++) dp[i]=0; dp[0]=1; for(int i=1; i<=n ;i++){ cin >> p[i]; } sort(p+1,p+n+1);reverse(p+1,p+n+1); int l=0,r=0; ld win=0; ld best=0; ld e=0; for(int i=1; i<=n ;i++){ e+=p[i]; for(int j=r+1; j>=l ;j--){ dp[j]=dp[j]*(1-p[i])+dp[j-1]*p[i]; } ++r; while(l<e-mg){ if(l*2-i>=t) win+=dp[l]; dp[l++]=0; } while(r>e+mg){ if(r*2-i>=t) win+=dp[r]; dp[r--]=0; } ld cur=win; for(int j=l; j<=r ;j++){ if(j*2-i>=t) cur+=dp[j]; } best=max(best,cur); } cout << fixed << setprecision(20) << best << '\n'; } |