#include <bits/stdc++.h> using namespace std; int main(){ cin.tie(0)->sync_with_stdio(0); int n, t; cin>>n>>t; vector<float> values(n); for(int i = 0; i<n; i++){ cin>>values[i]; } sort(values.rbegin(), values.rend()); vector<float> dp(2*n+10, 0), dp2(2*n+10, 0); int mid = n+4; dp[n+4] = 1; vector<float>* d1 = &dp; vector<float>* d2 = &dp2; int lower_bnd = n+4 - (n+10)/2; int upper_bnd = n+4 + (n+10)/2; float out = 0; for(int i = 0; i<n; i++){ float tmp = 0; int sp =n+4 - i*2 - ((i+1)%2); int ep = n+4 + i*2 + ((i+1)%2); for(int j = sp; j<=ep; j+=2){ (*d2)[j] = (*d1)[j-1] * values[i] + (*d1)[j+1] * (1.-values[i]); if(j >= t+mid) tmp += (*d2)[j]; } out = max(out, tmp); (*d1).clear(); swap(d1, d2); } cout<<fixed<<setprecision(15)<<out<<endl; 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 | #include <bits/stdc++.h> using namespace std; int main(){ cin.tie(0)->sync_with_stdio(0); int n, t; cin>>n>>t; vector<float> values(n); for(int i = 0; i<n; i++){ cin>>values[i]; } sort(values.rbegin(), values.rend()); vector<float> dp(2*n+10, 0), dp2(2*n+10, 0); int mid = n+4; dp[n+4] = 1; vector<float>* d1 = &dp; vector<float>* d2 = &dp2; int lower_bnd = n+4 - (n+10)/2; int upper_bnd = n+4 + (n+10)/2; float out = 0; for(int i = 0; i<n; i++){ float tmp = 0; int sp =n+4 - i*2 - ((i+1)%2); int ep = n+4 + i*2 + ((i+1)%2); for(int j = sp; j<=ep; j+=2){ (*d2)[j] = (*d1)[j-1] * values[i] + (*d1)[j+1] * (1.-values[i]); if(j >= t+mid) tmp += (*d2)[j]; } out = max(out, tmp); (*d1).clear(); swap(d1, d2); } cout<<fixed<<setprecision(15)<<out<<endl; return 0; } |