Submission #66746161

---

Source Code Expand

#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
using namespace std;

map<pair<int,pii>,int> dp; 

int solve(int n, int h, int m, vector<pii> &mo, int idx) {
    if(idx == n) {
        return 0;
    }
    if(h < mo[idx].first && m < mo[idx].second) {
        return 0;
    }
    if(dp.find({idx,{h,m}}) != dp.end()) {
        return dp[{idx,{h,m}}];
    }
    int nom = 0, mag = 0;
    if(h >= mo[idx].first) {
        nom = solve(n, h-mo[idx].first, m, mo, idx+1) + 1;
    }
    if(m >= mo[idx].second) {
        mag = solve(n, h, m-mo[idx].second, mo, idx+1) + 1;
    }
    return dp[{idx,{h,m}}] = max(nom, mag);
}

int main() {
	int tc = 1;
	//cin >> tc;
	while(tc--) {
	    int n, h, m;
	    cin >> n >> h >> m;
	    vector<pii> monsters(n);
	    for(auto &i : monsters) {
	        cin >> i.first >> i.second;
	    }
	    cout << solve(n, h, m, monsters, 0);
	}
}

Submission Info

Judge Result