SHARE
    TWEET
    aqibm

    Untitled

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

    AltStyle によって変換されたページ (->オリジナル) /