Submission #1103625

---

Source Code Expand

#include <iostream>
#include <vector>
#include <map>
#include <cstdio>
#include <cstring>
#include <math.h>
#include <bitset>
#include <time.h>
#include <set>
#include <algorithm>
#define ll long long
#define Inf 123372036854775806ll
using namespace std;

ll dp[666][666];
int main() {
    int N,Ma,Mb;
    cin>>N>>Ma>>Mb;
    
    for(int i=0;i<=555;i++)
        for(int j=0;j<=555;j++)
            dp[i][j]=(i+j==0?0:Inf);
    
    for(int i=1;i<=N;i++) {
        int a,b,c;
        cin>>a>>b>>c;
        for(int x=555;x>=0;x--)
            for(int y=555;y>=0;y--) {
                if (x >= a && y >= b)
                    dp[x][y]=min(dp[x][y],c+dp[x-a][y-b]);
            }
    }
    ll ans=Inf;
    for(int t=1;max(t*Ma,t*Mb)<=555;t++)
        ans=min(ans,dp[t*Ma][t*Mb]);
    if (ans == Inf) {
        cout << -1 << endl;
    } else {
        cout << ans << endl;
    }
    
}

Submission Info

Judge Result