Submission #1872275

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
int N, Ma, Mb, a[40], b[40], c[40], dp[41][401][401];
constexpr int inf{ numeric_limits<int>::max() / 3 };
int main() {
    cin >> N >> Ma >> Mb;
    for(int i{}; i < N; ++i)
        cin >> a[i] >> b[i] >> c[i];
    fill(dp[0][0], dp[41][0], inf);
    dp[0][0][0] = 0;
    for(int i{}; i < N; ++i)
        for(int j{}; j <= 400; ++j)
            for(int k{}; k <= 400; ++k) {
                dp[i + 1][j][k] = min(dp[i + 1][j][k], dp[i][j][k]);
                if(j + a[i] <= 400 && k + b[i] <= 400)
                    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 i{ 1 }; i <= 400; ++i)
        for(int j{ 1 }; j <= 400; ++j)
            if(i * Mb == j * Ma)
                ans = min(ans, dp[N][i][j]);
    cout << (ans < inf ? ans : -1) << endl;
}

Submission Info

Judge Result