SHARE
TWEET

Untitled

a guest Oct 19th, 2019 73 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. typedef pair<int, int> ii;
  6.  
  7. const int ms = 105;
  8.  
  9. long double dp[ms][ms][ms];
  10. bool vis[ms][ms][ms];
  11. int n;
  12. long double a[ms];
  13.  
  14. long double solve(int on, int have, int acc){
  15.     long double &x = dp[on][have][acc];
  16.     if(vis[on][have][acc]) return x;
  17.  
  18.     vis[on][have][acc] = true;
  19.  
  20.     if(on == n){
  21.         if(acc == 0) return x = 0;
  22.         if(acc == have) return x = acc;
  23.         return x = powl(acc, acc/(long double) have);
  24.     }
  25.  
  26.     x = a[on] * solve(on + 1, have + 1, acc + 1) + (1-a[on]) * solve(on + 1, have + 1, acc);
  27.     x = max(x, solve(on + 1, have, acc));
  28.     return x;
  29. }
  30.  
  31. int main () {
  32.     ios::sync_with_stdio(0); cin.tie(0);
  33.     cin >> n;
  34.     cout << fixed << setprecision(10);
  35.     for(int i = 0; i < n; ++i){
  36.         cin >> a[i];
  37.         a[i] /= 100;
  38.     }
  39.     sort(a, a + n, greater<int>());
  40.     cout << solve(0, 0, 0) << '\n';
  41. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top