Submission #1128677

---

Source Code Expand

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define MOD 1000000007
#define rep(i,n) for(i=0;i<n;i++)
#define loop(i,a,n) for(i=a;i<n;i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

typedef vector<int> vi;
typedef pair<int,int> pii;

int main(void) {
  int i,j;
  int n,ma,mb;
  cin>>n>>ma>>mb;
  vi a(n),b(n),c(n);
  rep(i,n)
    cin>>a[i]>>b[i]>>c[i];

  map<pii,int> x;
  rep(i,1<<(n/2)){//前半を全列挙                                                                 
    int ta=0,tb=0,tc=0;
    rep(j,n/2)
      if((i&(1<<j))!=0){//iのj桁目が1のとき                                                      
        ta+=a[j];
        tb+=b[j];
        tc+=c[j];
      }
    if(x.count(pii(ta,tb)))//存在するとき                                                        
      x[pii(ta,tb)]=min(x[pii(ta,tb)],tc);
    else
      x[pii(ta,tb)]=tc;
  }

  map<pii,int> y;
  rep(i,1<<(n-n/2)){//後半を全列挙                                                               
    int ta=0,tb=0,tc=0;
    rep(j,n-n/2)
      if((i&(1<<j))!=0){//iのj桁目が1のとき                                                      
        ta+=a[j+n/2];
        tb+=b[j+n/2];
        tc+=c[j+n/2];
      }
    if(y.count(pii(ta,tb)))//存在するとき                                                        
      y[pii(ta,tb)]=min(y[pii(ta,tb)],tc);
    else
      y[pii(ta,tb)]=tc;
  }

  int ans=INF;
  for(map<pii,int>::iterator itr=x.begin();itr!=x.end();itr++){
    int ta=(*itr).first.first;
    int tb=(*itr).first.second;
    for(i=1;i*max(ma,mb)<405;i++)
      if(y.count(pii(i*ma-ta,i*mb-tb)))
        ans=min(ans,(*itr).second+y[pii(i*ma-ta,i*mb-tb)]);
  }
  if(ans<INF)
    cout<<ans<<endl;
  else
    cout<<-1<<endl;
}

Submission Info

Judge Result