417A - Elimination - CodeForces Solution

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
#define __lcm(a,b) ((a*b)/__gcd(a,b))

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> ordered_map;
typedef tree<pair<int, int>, null_type, less_equal<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> ordered_multimap;

#define The_Special_One ios_base::sync_with_stdio(false); cin.tie(NULL);  cout.tie(NULL);

#define int long long 
#define endl '\n'
#define ll long long 
#define ld long double

#define binRep(num, n) bitset<n>(num).to_string()
#define clz(x) __builtin_clz(x)
#define clzll(x) __builtin_clzll(x)
#define ONES(n) __builtin_popcount(n)

#define SP(n) fixed << setprecision(n)
#define YES cout << "YES\n"
#define NO cout << "NO\n"

#define all(x) (x).begin(), (x).end()
#define rall(x) x.rbegin(), (x).rend()

#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define sz(v) ((int)v.size())
#define F first
#define S second
#define rp(i, a, b) for(int i=a; i<b; i++) 
#define iter(it,c) for(auto it=(c).begin(); it!=(c).end(); it++)
#define riter(it,c) for(auto it=(c).rbegin(); it!=(c).rend(); it++)

#define printmp(mp) for (auto it : mp) cout << it.first << ' ' << it.second << endl; 
#define print2d(v) for(auto &i:v) {for(auto &j:i) cout << j << ' ' ; cout << endl ;} 
#define print(v) for (auto &i : v)  cout << i << ' ' ;  cout << endl
#define input(v) for (auto &i : v)  cin >> i ; 

#define rv(x) return(void(cout<<x<<endl))
//           r  l   u   d
int dx[] = {+0, +0, -1, +1, -1, -1, +1, +1};
int dy[] = {+1, -1, +0, +0, +1, -1, +1, -1};

#define pi pair<int, int>
#define vi vector<int>
#define vpi vector<pi>
#define vbl vector<bool>
#define vvi vector<vi>
#define vvpi vector<vpi>
#define OO 1e18
const int MOD = 1e9+7;

const int SZ = 1e5;
int dp[SZ];
int c , d , n , m , k ; 
int run(int rem)
{
    if(rem<=0) return 0 ; 

    int &ret=dp[rem];
    if(~ret) return ret;

    ret=min(c+run(rem-n),d+run(rem-1)); 
    return ret; 
}

void solve()
{
    cin >> c >> d >> n >> m >> k ; 
    int rem=n*m-k; 
    memset(dp,-1,sizeof(dp));
    cout << run(rem);
} 

int32_t main()
{
    The_Special_One
    int t = 1;
    // cin >> t; 
    while (t--)
    {
        solve();
    }
    return 0;
}

/*  
    - read statement,constrains,sample explanatioon well && hunt keywords,know the correct squence of the problem && solution.
    - analyse the problem and try to conclude things from it.
    - start with naive solution if it fit constraint waddi else see how to optimize it(is there technique || algo solve that).
    - prove your approuch first before start -> mathematicaly,logicaly,by test cases...etc.
    - try another approuch || fix current approuch || try write code from begining again.
    - is there corner case || boundray error || type error ....etc.
    - try to solve problem in a paper.
    - see tutorial , people solutions if you did your best || if you solved it too(is there another approuch || technique you don't know).
*/