Submission #1104854

---

Source Code Expand

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#define ll long long int
#define pii pair<int, int>
#define mod 1000000007
#define fr(n) for (int i = 0; i < n; i++)
#define fr1(n) for (int i = 1; i <= n; i++)
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    int n, x, y, a[42] = {}, b[42] = {}, c[42] = {};
    ll d[402][402] = {}, z = mod;
    fr(402) for (int j = 0; j < 402; j++) d[i][j] = mod;
    d[0][0] = 0;
    cin >> n >> x >> y;
    fr(n) cin >> a[i] >> b[i] >> c[i];
    for (int k = 0; k < n; k++) for (int i = 0; i < 401; i++) for (int j = 0; j < 401; j++) {
        if (i + a[k] < 401 && j + b[k] < 401) d[i + a[k]][j + b[k]] = min(d[i + a[k]][j + b[k]], d[i][j] + c[k]);
    }
    for (int t = 1; t * x < 402 && t * y < 402; t++) z = min(z, d[t * x][t * y]);
    if (z > 10000000) cout << -1 << '\n';
    else cout << z << '\n';
}

Submission Info

Judge Result