Advertisement
aqibm

Untitled

Jun 15th, 2021
21
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.20 KB | None | 0 0
  1. #include <ext/pb_ds/assoc_container.hpp>
  2. #include <ext/pb_ds/tree_policy.hpp>
  3. #include <bits/stdc++.h>
  4.  
  5. using namespace __gnu_pbds;
  6. using namespace std;
  7.  
  8. // using long doubles saves you from corner cases but is very time consuming
  9. #define double long double
  10. #define int long long
  11. #define pb push_back
  12. #define pii pair<int,int>
  13. #define vi vector<int>
  14. #define vii vector<pii>
  15. #define mi map<int,int>
  16. #define mii map<pii,int>
  17. #define all(a) (a).begin(),(a).end()
  18. #define sz(x) (int)x.size()
  19. // just comment the line below in case of interactive problems
  20. #define endl "\n"
  21. #define repp(i,a,b) for(int i=a;i<b;i++)
  22. #define rep(i,a,b) for(int i=a;i<=b;i++)
  23. #define brep(i,a,b) for(int i=a;i>=b;i--)
  24. #define deb1(x) cout << #x << "=" << x << endl
  25. #define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
  26. #define deb3(x, y, z) cout << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << endl
  27. #define trace(v) cout << #v << "=";for(auto it=v.begin();it!=v.end();it++)cout<<*it<<" ";cout<<endl;
  28. #define tracearr(a,l,r) for(int iii=l;iii<=r;iii++)cout << a[iii] << " ";cout << endl;
  29. #define PI 3.1415926535897932384626
  30. #define F first
  31. #define S second
  32. #define clr(x,y) memset(x, y, sizeof(x))
  33. #define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  34. //vector<vector<int> > v( n , vector<int> (m, 0));
  35.  
  36.  
  37. typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
  38. // *s.find_by_order(1) - gives the 2nd samllest element in set
  39. // s.order_of_key(x) - gives the number of elements in the set which are strictly smaller than x
  40.  
  41.  
  42. const int N=5000 + 5;
  43. const int MOD=1e9 + 7;
  44.  
  45. int dp[N][N];
  46.  
  47. int n,m,x,y,a,b,c,d;
  48.  
  49. /*
  50. Fails here -
  51. 484 401 678 439 991 638 823 706
  52.  
  53. Expected o/p - 413977
  54. My o/p - 447789
  55. */
  56.  
  57. int solve(int cura,int curb){
  58. if(cura>=a && curb>=b){
  59. return 0;
  60. }
  61. int& ans = dp[cura][curb];
  62. if(ans!=-1)
  63. return ans;
  64. ans = 1e18;
  65. if(cura<2002){
  66. ans = min(ans,x + solve(cura+1,curb));
  67. }
  68. if(curb<2002){
  69. ans = min(ans,y + solve(cura,curb+1));
  70. }
  71. if(cura>=c && curb<b){
  72. ans = min(ans,solve(cura-c,curb+d));
  73. }
  74. if(curb>=d && cura<a){
  75. ans = min(ans,solve(cura+c,curb-d));
  76. }
  77. //deb3(cura,curb,ans);
  78. return ans;
  79. }
  80.  
  81. void test_case()
  82. {
  83. cin >> n >> m >> x >> y >> a >> b >> c >> d;
  84. clr(dp,-1);
  85. cout << solve(n,m) << endl;
  86.  
  87. }
  88.  
  89. int32_t main()
  90. {
  91. /*#ifndef ONLINE_JUDGE
  92. freopen("input.txt", "r", stdin);
  93. freopen("output.txt", "w", stdout);
  94. #endif*/
  95. IOS;
  96. int T=1;
  97. //cin >> T;
  98. // int numOfSetBits = __builtin_popcountll(n);
  99. std::cout << std::fixed << std::setprecision(12);
  100. while(T--)
  101. {
  102. test_case();
  103. }
  104. }
  105.  
  106. /*
  107. * while writing bool comp function for sorting put 1 statement in the end which has no if comdition
  108. * in case of multiple test cases and N=1e5 don't intialize arrays as global except for graph vector-array
  109. * always check whether or not you are doing mod of a negative number
  110. * always use 1LL instead of 1
  111. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement