fork download
  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <queue>
  5. #include <string>
  6. #include <cstring>
  7. #include <cmath>
  8. #include <map>
  9. #include <iostream>
  10. #include <limits>
  11. #include <set>
  12.  
  13. typedef std::pair<int,int> ii;
  14. typedef std::pair<double,double> dd;
  15. typedef long long int Int;
  16. typedef std::vector<int> vi;
  17. typedef std::vector<double> vd;
  18. typedef std::vector<vi> vvi;
  19. typedef std::vector<std::string> vs;
  20. typedef std::vector<ii> vii;
  21.  
  22. #define sz(X) int((X).size())
  23. #define REP(i,n) for(int i = 0; i < n; ++i)
  24. #define FOR(i,v) for(int i = 0; i < int(v.size()); ++i)
  25. #define ALL(v) v.begin(),v.end()
  26. using namespace std;
  27. char buf[100002];
  28.  
  29. const double inf = numeric_limits<double>::infinity();
  30. const double eps = 1e-5;
  31.  
  32. int main(){
  33. #ifdef LOCAL
  34. freopen("CF.txt","r",stdin);
  35. #endif
  36. int n;
  37. cin>>n;
  38. vd p(n);
  39. for(int j = 0; j<n; ++j) cin>>p[j], p[j] = 1-p[j];
  40. sort(p.begin(),p.end());
  41. priority_queue<pair<dd,int> > Q;
  42. Q.push(make_pair(dd(0.0,1.0),0));
  43. double mx = 0.0;
  44. int ctr = 0;
  45. while(!Q.empty()){
  46. double Tp = Q.top().first.first;
  47. double P = Q.top().first.second;
  48. int i = Q.top().second;
  49. Q.pop();
  50. for(int k = i; k<n; ++k){
  51. double T = Tp*p[k]+(1-p[k])*P;
  52. double P2 = P*p[k];
  53. ++ctr;
  54.  
  55. // Uncomment & output is correct!!
  56. //if (ctr == 100)
  57. //ctr = 0, cout << T << " " << mx << endl;
  58. // I have made this "ctr" thing in order to not output too much on ideone's output file
  59.  
  60. if( T > mx){
  61. mx = T;
  62. Q.push(make_pair(dd(T,P2),k+1));
  63. }
  64. }
  65. }
  66. cout << mx;
  67. return 0;
  68. }
  69.  
  70.  
  71. // printf("%I64d\n", c1-res);
  72. // scanf(" %lf",&nums[i]);
Success #stdin #stdout 0s 3532KB
stdin
100
0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01
stdout
0.038812