Submission #1103754

---

Source Code Expand

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<cassert>
#define PB push_back
#define MP make_pair
#define sz(v) (in((v).size()))
#define forn(i,n) for(in i=0;i<(n);++i)
#define forv(i,v) forn(i,sz(v))
#define fors(i,s) for(auto i=(s).begin();i!=(s).end();++i)
#define all(v) (v).begin(),(v).end()
using namespace std;
typedef long long in;
typedef vector<in> VI;
typedef vector<VI> VVI;
VVI mnc;
const in inf=1e18;
const in mx=42*12;
int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  in n,ga,gb;
  cin>>n>>ga>>gb;
  mnc.resize(mx,VI(mx,inf));
  mnc[0][0]=0;
  in a,b,c;
  forn(z,n){
    cin>>a>>b>>c;
    for(in i=mx-a-1;i>=0;--i){
      for(in j=mx-b-1;j>=0;--j){
	mnc[i+a][j+b]=min(mnc[i+a][j+b],mnc[i][j]+c);
      }
    }
  }
  in tm=inf;
  for(in x=1;x*max(ga,gb)<mx;++x){
    tm=min(tm,mnc[x*ga][x*gb]);
  }
  if(tm==inf)
    cout<<-1<<endl;
  else
    cout<<tm<<endl;
  return 0;
}

Submission Info

Judge Result