Submission #1610110

---

Source Code Expand

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

Submission Info

Judge Result