• Sign Up
• Login
• API
• FAQ
• Tools
• Archive
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.
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!

Top