Ankit_132

E

Nov 4th, 2023
361
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.85 KB | None | 0 0
  1.  
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. int main()
  7. {
  8.     int n;
  9.     cin>>n;
  10.  
  11.     vector<int> p(n);
  12.     for(auto &e: p)   cin>>e;
  13.  
  14.     long double p9 = 1;
  15.     vector<long double> pSum(n + 1);
  16.  
  17.     for (int i = 1; i <= n; i++)
  18.     {
  19.         pSum[i] = (pSum[i - 1] + p9);
  20.         p9 *= 0.9;
  21.     }
  22.  
  23.     vector<long double> dp(n + 1, -1e18);
  24.     dp[0] = 0;
  25.     for (int i = 0; i < n; i++)
  26.     {
  27.         auto ndp = dp;
  28.         for (int j=0; j<=i; j++)
  29.         {
  30.             if(j+1 <= n)
  31.                 ndp[j + 1] = max(ndp[j + 1], dp[j] * 0.9 + p[i]);
  32.         }
  33.         swap(ndp, dp);
  34.     }
  35.  
  36.     long double ans = -1e18;
  37.     for (int i = 1; i <= n; i++)
  38.     {
  39.         long double x = 1200.0 / sqrt(1.0 * i);
  40.         ans = max(ans, (dp[i] / pSum[i]) - x);
  41.     }
  42.    
  43.     cout<<fixed<<setprecision(15);
  44.     cout<<ans<<"\n";
  45. }
  46.  
Advertisement
Add Comment
Please, Sign In to add comment