Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define pb push_back
- int main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- cout.tie(NULL);
- ll int a[105][105], p[105], cost[105];
- double dp[105];
- int n, m;
- cin>>n>>m;
- fill(dp, dp+105, -1);
- for(int i=0; i<n; i++)
- {
- cin>>cost[i]>>p[i];
- for(int j=0; j<p[i]; j++)
- cin>>a[i][j];
- }
- function<double(int)> solve = [&](int val)
- {
- if(val<=0) return 0.0;
- if(dp[val]!=-1) return dp[val];
- double ans=1e18;
- for(int i=0; i<n; i++)
- {
- double res = 0;
- int zeros = 0;
- for(int j=0; j<p[i]; j++)
- {
- if(a[i][j]==0)
- zeros++;
- else
- res += solve(val-a[i][j]);
- }
- double prob=1.0/p[i];
- res = res*prob+cost[i];
- if(zeros)
- {
- prob=1.0*p[i]/(p[i]-zeros);
- res *= prob;
- }
- ans=min(ans,res);
- }
- return dp[val] = ans;
- };
- cout<<fixed<<setprecision(9)<<solve(m);
- }
Advertisement
Add Comment
Please, Sign In to add comment