Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- #include <bits/stdc++.h>
- using namespace __gnu_pbds;
- using namespace std;
- // using long doubles saves you from corner cases but is very time consuming
- #define double long double
- #define int long long
- #define pb push_back
- #define pii pair<int,int>
- #define vi vector<int>
- #define vii vector<pii>
- #define mi map<int,int>
- #define mii map<pii,int>
- #define all(a) (a).begin(),(a).end()
- #define sz(x) (int)x.size()
- // just comment the line below in case of interactive problems
- #define endl "\n"
- #define repp(i,a,b) for(int i=a;i<b;i++)
- #define rep(i,a,b) for(int i=a;i<=b;i++)
- #define brep(i,a,b) for(int i=a;i>=b;i--)
- #define deb1(x) cout << #x << "=" << x << endl
- #define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
- #define deb3(x, y, z) cout << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << endl
- #define trace(v) cout << #v << "=";for(auto it=v.begin();it!=v.end();it++)cout<<*it<<" ";cout<<endl;
- #define tracearr(a,l,r) for(int iii=l;iii<=r;iii++)cout << a[iii] << " ";cout << endl;
- #define PI 3.1415926535897932384626
- #define F first
- #define S second
- #define clr(x,y) memset(x, y, sizeof(x))
- #define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
- //vector<vector<int> > v( n , vector<int> (m, 0));
- typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
- // *s.find_by_order(1) - gives the 2nd samllest element in set
- // s.order_of_key(x) - gives the number of elements in the set which are strictly smaller than x
- const int N=5000 + 5;
- const int MOD=1e9 + 7;
- int dp[N][N];
- int n,m,x,y,a,b,c,d;
- /*
- Fails here -
- 484 401 678 439 991 638 823 706
- Expected o/p - 413977
- My o/p - 447789
- */
- int solve(int cura,int curb){
- if(cura>=a && curb>=b){
- return 0;
- }
- int& ans = dp[cura][curb];
- if(ans!=-1)
- return ans;
- ans = 1e18;
- if(cura<2002){
- ans = min(ans,x + solve(cura+1,curb));
- }
- if(curb<2002){
- ans = min(ans,y + solve(cura,curb+1));
- }
- if(cura>=c && curb<b){
- ans = min(ans,solve(cura-c,curb+d));
- }
- if(curb>=d && cura<a){
- ans = min(ans,solve(cura+c,curb-d));
- }
- //deb3(cura,curb,ans);
- return ans;
- }
- void test_case()
- {
- cin >> n >> m >> x >> y >> a >> b >> c >> d;
- clr(dp,-1);
- cout << solve(n,m) << endl;
- }
- int32_t main()
- {
- /*#ifndef ONLINE_JUDGE
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif*/
- IOS;
- int T=1;
- //cin >> T;
- // int numOfSetBits = __builtin_popcountll(n);
- std::cout << std::fixed << std::setprecision(12);
- while(T--)
- {
- test_case();
- }
- }
- /*
- * while writing bool comp function for sorting put 1 statement in the end which has no if comdition
- * in case of multiple test cases and N=1e5 don't intialize arrays as global except for graph vector-array
- * always check whether or not you are doing mod of a negative number
- * always use 1LL instead of 1
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement