Ankit_132

E

Aug 13th, 2023
295
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.23 KB | None | 0 0
  1.  
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. #define ll     long long
  7. #define pb     push_back
  8.  
  9. int main()
  10. {
  11.     ios_base::sync_with_stdio(false);
  12.     cin.tie(NULL);
  13.     cout.tie(NULL);
  14.    
  15.     ll int a[105][105], p[105], cost[105];
  16.     double dp[105];
  17.     int n, m;
  18.  
  19.     cin>>n>>m;
  20.     fill(dp, dp+105, -1);
  21.  
  22.     for(int i=0; i<n; i++)
  23.     {
  24.         cin>>cost[i]>>p[i];
  25.         for(int j=0; j<p[i]; j++)
  26.             cin>>a[i][j];
  27.     }
  28.  
  29.     function<double(int)> solve = [&](int val)
  30.     {
  31.         if(val<=0)          return 0.0;
  32.         if(dp[val]!=-1)     return dp[val];
  33.  
  34.         double ans=1e18;
  35.  
  36.         for(int i=0; i<n; i++)
  37.         {
  38.             double res = 0;
  39.             int zeros = 0;
  40.  
  41.             for(int j=0; j<p[i]; j++)
  42.             {
  43.                 if(a[i][j]==0)
  44.                     zeros++;
  45.                 else
  46.                     res += solve(val-a[i][j]);
  47.             }
  48.  
  49.             double prob=1.0/p[i];
  50.             res = res*prob+cost[i];
  51.  
  52.             if(zeros)
  53.             {
  54.                 prob=1.0*p[i]/(p[i]-zeros);
  55.                 res *= prob;
  56.             }
  57.  
  58.             ans=min(ans,res);
  59.         }
  60.  
  61.         return dp[val] = ans;
  62.     };
  63.  
  64.     cout<<fixed<<setprecision(9)<<solve(m);
  65. }
  66.  
Advertisement
Add Comment
Please, Sign In to add comment