Submission #1776228

---

Source Code Expand

#include <iostream>
#include <iomanip>
#include <cstring>
#include <algorithm> 
#include <queue>
#include <functional>
#include <map>
#include <vector>
#include <string>
using namespace std;
typedef long long ll;
const int INF = 100000;

int dp[45][405][405];

int main(void){
    int n, a[45], b[45], c[45], ma, mb, suma = 0, sumb = 0;

    cin >> n >> ma >> mb;
    for (int i = 0; i < n; i++){
        cin >> a[i] >> b[i] >> c[i];
        suma += a[i]; sumb += b[i];
    }

    for (int i = 0; i <= suma; i++)
        for (int j = 0; j <= sumb; j++) dp[0][i][j] = INF;

    dp[0][0][0] = 0;

    for (int i = 0; i < n; i++){
        for (int j = 0; j <= suma; j++){
            for (int k = 0; k <= sumb; k++){
                dp[i + 1][j][k] = dp[i][j][k];
                if (a[i] <= j && b[i] <= k) dp[i + 1][j][k] = min(dp[i + 1][j][k], dp[i][j - a[i]][k - b[i]] + c[i]);
            }
        }
    }

    int ans = INF;
    for (int i = 1; i <= suma; i++){
        for (int j = 1; j <= sumb; j++){
            if (ma*j == mb*i) ans = min(ans, dp[n][i][j]);
        }
    }

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

}

Submission Info

Judge Result