Submission #1609385

---

Source Code Expand

#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <cstring>
#include <cmath>
#include <stack>
#include <iomanip>
#include <tuple>
#include <functional>

#define int long long
#define CONTAINS(v,n) (find((v).begin(), (v).end(), (n)) != (v).end())
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
#define ARY_SORT(a, size) sort((a), (a)+(size))
#define MAX(a,b) (((a) > (b)) ? (a) : (b))
#define MIN(a,b) (((a) < (b)) ? (a) : (b))
#define REMOVE(v,a) v.erase(remove(v.begin(), v.end(), a), v.end())
#define REP(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define REPE(i, n) for (int (i) = 0; (i) <= (n); (i)++)
using namespace std;

int N, Ma, Mb;
int a[40];
int b[40];
int c[40];

int dp[41][401][401];

signed main()
{
	cin >> N >> Ma >> Mb;
	REP(i, N) cin >> a[i] >> b[i] >> c[i];

	REPE(i, N)REP(j, 400)REPE(k, 400) dp[i][j][k] = INT_MAX;

	dp[0][0][0] = 0;
	REP(i, N)
	{
		REP(j, 400)REPE(k, 400)
		{
			if (dp[i][j][k] < INT_MAX)
			{
				dp[i + 1][j + a[i]][k + b[i]] = MIN(dp[i + 1][j + a[i]][k + b[i]], dp[i][j][k] + c[i]);
				dp[i + 1][j][k] = MIN(dp[i + 1][j][k], dp[i][j][k]);
			}
		}
	}

	int min = INT_MAX;
	REP(j, 400)REPE(k, 400)
	{
		if (j * Mb == Ma * k && j*k != 0)
		{
			min = MIN(min, dp[N][j][k]);
		}
	}

	if (min == INT_MAX)
	{
		cout << "-1" << endl;
	}
	else
	{
		cout << min << endl;
	}
}

Submission Info

Judge Result