Submission #1104855

---

Source Code Expand

#include <map>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n, a[45], b[45], c[45], ma, mb, dp[450][450];
int main() {
	cin >> n >> ma >> mb;
	for (int i = 1; i <= n; i++) cin >> a[i] >> b[i] >> c[i];
	memset(dp, -1, sizeof(dp));
	dp[0][0] = 0;
	for (int A = 1; A <= 400; A++)
		for (int B = 1; B <= 400; B++) {
			for (int i = 1; i <= n; i++) {
				if (A - a[i] < 0 || B - b[i] < 0) continue;
				if (dp[A - a[i]][B - b[i]] != -1)
					if (dp[A - a[i]][B - b[i]] + c[i] < dp[A][B] || dp[A][B] == -1)
						dp[A][B] = dp[A - a[i]][B - b[i]] + c[i];
			}
		}
	int ans = -1;
	for (int i = 1; i * max(ma, mb) <= 400; i++)
		if ((ans >= dp[i * ma][i * mb] && dp[i * ma][i * mb] != -1) || ans == -1)
			ans = dp[i * ma][i * mb];
	cout << ans << endl;
	return 0;
}

Submission Info

Judge Result