Submission #1103645

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>

using namespace std;

template<class T1, class T2>
void chmin(T1 &a, T2 b) {
	if (b < a) a = b;
}

int dp[41][444][444];

int main() {
	fill_n(**dp, sizeof(dp) / 4, 1e9);

	int n, ma, mb;
	cin >> n >> ma >> mb;

	dp[0][0][0] = 0;

	for (int i = 0; i < n; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		for (int j = 0; j < 410; j++) {
			for (int k = 0; k < 410; k++) {
				chmin(dp[i + 1][j][k], dp[i][j][k]);
				chmin(dp[i + 1][j + a][k + b], dp[i][j][k] + c);
			}
		}
	}

	int ans = 1e9;
	for (int i = 1; i < 410; i++) {
		for (int j = 1; j < 410; j++) {
			if (ma * j == i * mb) {
				ans = min(ans, dp[n][i][j]);
			}
		}
	}
	if (ans == 1e9) ans = -1;
	cout << ans << endl;
}

Submission Info

Judge Result