Submission #1610029

---

Source Code Expand

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int INF = 1e9;
int MOD = 1e9+7;
int dp[1000][1000];
main(){
    fill(dp[0],dp[1000],INF);
    dp[0][0] = 0;
    int N,MA,MB,A[40],B[40],C[40],mini = INF;
    cin >> N >> MA >> MB;
    for(int i = 0;i < N;i++){
        cin >> A[i] >> B[i] >> C[i];
    }
    for(int i = 0;i < N;i++){
        for(int j = 0;j < 1000;j++){
            for(int k = 0;k < 1000;k++){
                if(j-A[i] < 0 || k-B[i] < 0)continue;
                dp[j][k] = min(dp[j][k],dp[j-A[i]][k-B[i]] + C[i]);
            }
        }
    }
    for(int i = 1;max(MA,MB)*i < 1000;i++){
        mini = min(mini,dp[MA*i][MB*i]);
    }
    if(mini == INF)cout << -1 << endl;
    else cout << mini << endl;
}

Submission Info

Judge Result