Advertisement
Ahmed_Negm

Untitled

Mar 26th, 2023
893
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.08 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. using namespace std;
  5. using namespace __gnu_pbds;
  6. #define ll long long
  7. #define OO 2'000'000'000
  8. #define ull unsigned long long
  9. #define nl '\n'
  10. #define sz(x) (ll)(x.size())
  11. #define all(x) x.begin(),x.end()
  12. #define rall(s)  s.rbegin(), s.rend()
  13. #define getline(s) getline(cin>>ws,s)
  14. #define ceill(n, m) (((n) / (m)) + ((n) % (m) ? 1 : 0))
  15. #define pi  3.141592653589793
  16. #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
  17. #define multi_ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
  18.  
  19.  
  20. void Fast_IO(){
  21. ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  22. // freopen("filename.in", "r", stdin);
  23. // freopen("filename.txt", "w", stdout);
  24. #ifndef ONLINE_JUDGE
  25. freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
  26. #endif
  27. }
  28.  
  29.  
  30.  
  31.  
  32. int dx[] = { 2, 1, -1, -2, -2, -1, 1, 2 };
  33. int dy[] = { 1, 2, 2, 1, -1, -2, -2, -1 };
  34.  
  35. struct Off{
  36.     ll cy,me,cost;
  37.     Off(int _cy=0,int _me=0,int _cost=0){
  38.         cy = _cy;
  39.         me = _me;
  40.         cost = _cost;
  41.     }
  42. };
  43.  
  44. ll n,a,b;
  45. vector<Off>v;
  46.  
  47. bool check(ll cy,ll me,ll x,ll y){
  48.     if(cy==0 && me==0) return false;
  49.     return cy*y==me*x;
  50. }
  51.  
  52. ll dp[41][11][11];
  53.  
  54. ll min_cost(ll idx,ll cy,ll me){
  55.     if(idx == n){
  56.         if(check(cy,me,a,b)){
  57.             return 0;
  58.         }
  59.         return OO;
  60.     }
  61.     ll &ret = dp[idx][cy][me];
  62.     if(ret != -1) return ret;
  63.     ret = OO;
  64.     ret = min(ret,min_cost(idx+1,cy+v[idx].cy,me+v[idx].me)+v[idx].cost);
  65.     ret = min(ret,min_cost(idx+1,cy,me));
  66.     return ret;
  67. }
  68.  
  69.  
  70. void solve(){
  71.   cin>>n>>a>>b;
  72.   v = vector<Off>(n);
  73.     for(int i=0;i<n;i++){
  74.         cin>>v[i].cy>>v[i].me>>v[i].cost;
  75.     }
  76.     memset(dp,-1,sizeof (dp));
  77.     ll res = min_cost(0,0,0);
  78.     if(res >= OO){
  79.         cout<<-1<<nl;
  80.     }else{
  81.         cout<<res<<nl;
  82.     }
  83.  
  84.  
  85.  
  86. }
  87.  
  88. int main(){
  89.     Fast_IO();
  90. int t =1;
  91. //cin>>t;
  92. while(t--){
  93. solve();
  94. }
  95. return 0;
  96. }  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement