fork download 
  1. #pragma GCC optimize("Ofast")
  2. #pragma GCC optimize("unroll-loops")
  3.  
  4. #include <bits/stdc++.h>
  5.  
  6. using namespace std;
  7. using ll = long long;
  8.  
  9. const ll mod = 1e9 + 7;
  10. const ll mod2 = 998244353;
  11.  
  12. ll gcd(ll a, ll b) {
  13.     return b ? gcd(b, a % b) : a;
  14. }
  15.  
  16. ll pow(ll a, ll b) {
  17.     ll ans = 1;
  18.     while (b) {
  19.         if (b & 1) ans *= a;
  20.         b >>= 1;
  21.         a *= a;
  22.     }
  23.     return ans;
  24. }
  25.  
  26. ll pow(ll a, ll b, ll c) {
  27.     ll ans = 1;
  28.     while (b) {
  29.         if (b & 1) ans = (ans * a) % c;
  30.         b >>= 1;
  31.         a = (a * a) % c;
  32.     }
  33.     return ans;
  34. }
  35.  
  36. void check(bool b) {
  37.     if (b)
  38.         cout << "Yes\n";
  39.     else
  40.         cout << "No\n";
  41. }
  42.  
  43. using ld = long double;
  44.  
  45. int main() {
  46.     ios_base::sync_with_stdio(false);
  47.     cin.tie(nullptr);
  48.     cout.tie(nullptr);
  49.     ll n,k;cin>>n>>k;
  50.     vector<ll>prob(n);
  51.     for (int i = 0; i < n; ++i) {
  52.         cin>>prob[i];
  53.     }
  54.     vector<vector<ld>>x(n,vector<ld>(k+1));
  55.     auto x_=x;
  56.     for (int i = 0; i < n; ++i) {
  57.         ld x1;
  58.         x1=prob[i];x1/=100;
  59.         x[i][0]=1;
  60.         for (int j = 0; j < k; ++j) {
  61.             x[i][j+1]=x[i][j]*x1;
  62.         }
  63.         x1=1-x1;
  64.         x_[i][0]=1;
  65.         for (int j = 0; j < k; ++j) {
  66.             x_[i][j+1]=x_[i][j]*x1;
  67.         }
  68.     }
  69.     vector<vector<ld>>dp(k+1,vector<ld>(k+1,-1));vector<vector<ll>>vis(k+1,vector<ll>(k+1,0));
  70.     for (int i=0;i<=k;++i)dp[k][i]=1,vis[k][i]=1;
  71.     function<ld(ll,ll)>solve = [&](ll i, ll j)->ld{
  72.         if (vis[i][j]==0){
  73. vis[i][j]=1;
  74.             ld t = 0;
  75.             for (int l = 0; l < n; ++l) {
  76.                 t+=x[l][j]*x_[l][i-j];
  77.             }
  78.             vector<ld>new_prob(n);
  79.             for (int l = 0; l < n; ++l) {
  80.                 new_prob[l]=x[l][j]*x_[l][i-j]/t;
  81.             }
  82.             t=0;
  83.             for (int l = 0; l < n; ++l) {
  84.                 t+=new_prob[l]*(x[l][1]*solve(i+1,j+1)+x_[l][1]*solve(i+1,j));
  85.             }
  86.             dp[i][j]=max(dp[i][j],t);
  87.             t=0;
  88.             for (int l = 0; l < n; ++l) {
  89.                 t+=2*new_prob[l]*(x[l][1]*solve(i+1,j+1));
  90.             }
  91.             dp[i][j]=max(dp[i][j],t);
  92.         }
  93.         return dp[i][j];
  94.     };
  95.     cout<<fixed<<setprecision(9)<<1000*solve(0,0)-1000;
  96.     return 0;
  97. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin 
6 6
10 20 60 30 40 50
stdout 
29.408000000
https://ideone.com/D1rEBz
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!