Submission #1103594

---

Source Code Expand

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

struct cww{cww(){
    ios::sync_with_stdio(false);cin.tie(0);
    cout<<fixed;
    cout<<setprecision(10);
}}star;
#define fin "\n"
#define FOR(i,bg,ed) for(int i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)

#define fi first
#define se second
#define pb push_back

template <typename T>inline void chmin(T &l,T r){l=min(l,r);}
template <typename T>inline void chmax(T &l,T r){l=max(l,r);}

template <typename T>
istream& operator>>(istream &is,vector<T> &v){
    for(auto &it:v)is>>it;
    return is;
}

typedef vector<int> V;
typedef vector<V> VV;
const LL INF=1e8;
int main(){
    int N,A,B;
    cin>>N>>A>>B;
    VV dp(401,V(401,INF));
    dp[0][0]=0;
    REP(latte,N){
        int a,b,c;
        cin>>a>>b>>c;
        auto nxt=dp;
        for(int i=a;i<=400;i++)
            for(int j=b;j<=400;j++)
                chmin(nxt[i][j],dp[i-a][j-b]+c);
        swap(dp,nxt);
    }
    int M=A,K=B,res=INF;
    for(;M<=400&&K<=400;M+=A,K+=B)
        chmin(res,dp[M][K]);
    if(res==INF)cout<<-1<<endl;
    else cout<<res<<endl;

    return 0;
}

Submission Info

Judge Result