106C - Buns - CodeForces Solution

#pragma GCC optimize ("O3")

#include <bits/stdc++.h>

#define ll long long
#define endl '\n'
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define file freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
using namespace std;

const int OO = 0x3f3f3f3f, N = 1e3 + 5, mod = 1e9 + 7;

int a[N], b[N], c[N], d[N];
int hve, n, e, sld;
ll dp[10][1005];

ll go(int idx, int lft) {
    if (idx == n) {
        ll can = lft / e;
        return can * sld;
    }

    ll &ans = dp[idx][lft];
    if (~ans) {
        return ans;
    }

    ans = go(idx + 1, lft);
    for (int i = 1; i * b[idx] <= a[idx] && i * c[idx] <= lft; i++) {
        ans = max(ans, go(idx + 1, lft - (i * c[idx])) + (i * d[idx]));
    }

    return ans;
}

void solve() {
    cin >> hve >> n >> e >> sld;
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
    }
    memset(dp, -1, sizeof dp);
    cout << go(0, hve);
}

int main() {
    fast;
    int tc = 1;
//    cin >> tc;
    while (tc--) {
        solve();
    }
}