Submission #1610167

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define INF 900000000
#define LINF 9000000000000000000

typedef long long ll;
typedef pair<int, int> P;

int n, m1, m2;
int a[40], b[40], c[40];
int dp[41][401][401];

int main(){
	cin.tie(0);
  ios::sync_with_stdio(false);

	cin >> n >> m1 >> m2;
	for (int i = 0; i <= n; i++) cin >> a[i] >> b[i] >> c[i];

	for (int i = 0; i <= 40; i++) for (int j = 0; j < 401; j++) for (int k = 0; k < 401; k++)
		dp[i][j][k] = INF;

	dp[0][0][0] = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= 400; j++) {
			for (int k = 0; k <= 400; k++) {
				if (dp[i][j][k] == INF) continue;
				dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k]);
				dp[i+1][j+a[i]][k+b[i]] = min(dp[i][j][k]+c[i], dp[i+1][j+a[i]][k+b[i]]);
			}
		}
	}

	int ans = INF;
	for (int j = 1; j <= 400; j++) {
		for (int k = 1; k <= 400; k++) {
			if (j*m2 == k*m1) {
				ans = min(ans, dp[n][j][k]);
			}
		}
	}

	if (ans == INF) ans = -1;
	cout << ans << endl;

	return 0;
}

Submission Info

Judge Result