Submission #1603761

---

Source Code Expand

#include<bits/stdc++.h>

#define INF (int)(1e9)
#define N_MAX (40)
#define AB_MAX (400)

using namespace std;

typedef long long int Int;


Int a[N_MAX],b[N_MAX],c[N_MAX];
Int dp[N_MAX+1][AB_MAX+1][AB_MAX+1];

int main(void)
{
    Int N,Ma,Mb;
    cin>>N>>Ma>>Mb;

    for(int i = 0;i <= N_MAX;i++) {
	for(int j = 0;j <= AB_MAX;j++) {
	    for(int k = 0;k <= AB_MAX;k++) {
		dp[i][j][k] = INF;
	    }
	}
    }

    for(int i = 0;i < N;i++)
    {
	cin>>a[i]>>b[i]>>c[i];
    }

    dp[0][0][0] = 0;
    for(int i = 0;i < N_MAX;i++) {
	for(int j = 0;j <= AB_MAX;j++) {
	    for(int k = 0;k <= AB_MAX;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+1][j+a[i]][k+b[i]],dp[i][j][k]+c[i]);
	    }
	}
    }

    Int ans = INF;
    for(int j = 1;j <= AB_MAX;j++) {
	for(int k = 1;k <= AB_MAX;k++) {
	    if(j*Mb==k*Ma)
		ans = min(ans,dp[N][j][k]);
	}
    }

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


    return 0;
}

Submission Info

Judge Result