Submission #2245038

---

Source Code Expand

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<tuple>
#define LL long long
#define TT std::tuple<int,int,int>
int N, MA, MB;
int dp[2][4010][4010];
std::vector<TT> med;
int INF = 100000000;
int ans = INF;
int main() {
	std::cin >> N >> MA >> MB;
	for (int i = 0; i < N; i++) {
		int a, b, c;
		std::cin >> a >> b >> c;
		med.push_back(TT{ a,b,c });
	}
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j <= 4000; j++) {
			for (int k = 0; k <= 4000; k++) {
				if (j == 0 && k == 0)continue;
				dp[i][j][k] = INF;
			}
		}
	}
	for (int i = 1; i <= N; i++) {
		int a, b, c;
		std::tie(a, b, c) = med[i - 1];
		for (int j = 1; j <= 4000; j++) {
			for (int k = 1; k <= 4000; k++) {
				dp[i%2][j][k] = dp[(i - 1)%2][j][k];
				if (j - a >= 0 && k - b >= 0) {
					dp[i%2][j][k] = std::min(dp[i%2][j][k], dp[(i - 1)%2][j - a][k - b] + c);
				}
			}
		}
	}
	int D = 1;
	while (MA*D <= 4000 && MB*D <= 4000) {
		ans = std::min(ans, dp[N%2][MA*D][MB*D]);
		D++;
	}
	if (ans == INF)ans = -1;
	std::cout << ans << std::endl;
	return 0;
}

Submission Info

Judge Result