Language: C++

/**
    OJ :
    Program Code :
    Md. Mujahedul Azad (Turin)
    Hajee Mohammad Danesh Science & Technology University
**/

#include<bits/stdc++.h>
using namespace std;

#define pi              2*acos(0.0)
#define all(v)          v.begin(),v.end()
#define ff              first
#define se              second
#define pb              push_back
#define mp              make_pair
#define Sort(a)         sort(all(a))
#define RSort(a)        Sort(a), reverse(all(a))
#define sz(x)           (int)x.size()
#define max3(a,b,c)     max(a, max(b, c))
#define min3(a,b,c)     min(a, min(b, c))
#define maxall(v)       *max_element(all(v))
#define minall(v)       *min_element(all(v))
#define sq(a)           ((a) * (a))
#define abs(x)          (((x)<0)?-(x):(x))
#define precision(x)    cout << setprecision(x) << fixed
#define mem(a,v)        memset(a, v, sizeof(a))
#define fillAra(a,n,v)  fill(a, a+n, v)
#define fillVec(a, v)   fill(all(a), v)
#define countOne(a)     __builtin_popcount(a)
#define parity(a)       __builtin_parity(a)
#define btz(a)          __builtin_ctz(a)
#define gf              << ' ' <<
#define nl              << '\n'
#define cinIg           cin.sync(); cin.get()
#define FasterIO        ios_base::sync_with_stdio(false);cin.tie(NULL)
#define TestCases       int cases, tc; sfi(tc); for(cases=1; cases<=tc; cases++)
#define TestCasespp     int cases, tc; cin>>tc; for(cases=1; cases<=tc; cases++)
#define un(a)           Sort(a), (a).erase(unique(all(a)),a.end())
#define common(a,b)     Sort(a), Sort(b), a.erase(set_intersection(all(a), all(b), a.begin()), a.end())
#define uncommon(a,b)   Sort(a), Sort(b), a.erase(set_symmetric_difference(all(a), all(b), a.begin()), a.end())

/**------- ShortCuts----------*/
typedef long long             ll;
typedef unsigned long long    ull;
typedef double                db;
typedef long double           ldb;
typedef pair<int, int>        pii;
typedef pair<ll, ll>          pll;
typedef pair<int, pii>        iii;
typedef vector<int>           vi;
typedef vector<ll>            vl;
typedef vector<pii>           vii;
typedef vector<iii>           viii;
typedef vector<vi>            vvi;
typedef map<int, int>         mapii;
typedef map<int, bool>        mapib;
typedef map<int, string>      mapis;
typedef set<int>              seti;

/**------- Char Chk----------*/
inline bool isLow(char ch){if(ch>='a' && ch<='z') return true; return false;}
inline bool isUpp(char ch){if(ch>='A' && ch<='Z') return true; return false;}
inline bool isDig(char ch){if(ch>='0' && ch<='9') return true; return false;}

/**------- Double Chk----------*/
inline bool are_equal(db a, db b){return fabs(a-b)<numeric_limits<db>::epsilon();}
inline bool greater_than(db a, db b){return (a-b) > ((fabs(a)<fabs(b)?fabs(b):fabs(a)) * numeric_limits<db>::epsilon());}
inline bool less_than(db a, db b){return (b-a) > ((fabs(a)<fabs(b)?fabs(b):fabs(a)) * numeric_limits<db>::epsilon());}

/**------- Functions ---------*/
template<typename T> string toString(T x){stringstream ss; ss<<x; return ss.str();}
template<typename T> T SOD(T n){__typeof(n) sum=0, i=1; for(; i*i<=n; i++) sum += (n%i)?0:((sq(i)==n)?i:i+n/i); return sum;}
template<typename T> T stringToT(string s, T a){T p; istringstream ss(s); ss>>p; return p;}

template<typename T>ostream& operator << (ostream& os, const vector<T> &v){os << "["; for(int i=0; i<v.size(); i++){ os << v[i]; if(i != sz(v)-1) os << ", ";} os << "]"; return os;}
template<typename T>ostream& operator << (ostream& os, const set<T> &v){ os << "["; for(auto it : v){os << it;if(it != *v.rbegin())os << ", ";}os << "]";return os;}
template<typename T, typename S> ostream& operator << (ostream& os, const map<T, S> &v){for(auto it : v) os << it.ff << " : " << it.se nl; return os;}
template<typename T, typename S> ostream& operator << (ostream& os, const pair<T, S> &v){os << "(" << v.ff << ", " << v.se << ")";return os;}

ll power(ll a, ll b){ll res = 1; while(b){if(b & 1) res *= a; a = sq(a); b >>= 1;} return res;}
ll bigmod(ll a, ll b, ll m) {ll res = 1; while(b) { if(b & 1) { res = ( (res % m) * (a % m) ) %m ; } a= ((a%m) * (a%m)) %m; b >>= 1; } return res; }
ll modInverse(ll a, ll m) {return bigmod(a,m-2,m);}

/**------- Scanf----------*/
#define sf                 scanf
#define sfi(a)             scanf("%d", &a)
#define sfc(a)             scanf("%c", &a)
#define sfl(a)             scanf("%lld", &a)
#define sfu(a)             scanf("%llu", &a)
#define sfs(a)             scanf("%s", a)
#define sfd(a)             scanf("%lf", &a)
#define sfii(a, b)         scanf("%d %d", &a, &b)
#define sfll(a, b)         scanf("%lld %lld", &a, &b)
#define sfuu(a, b)         scanf("%llu %llu", &a, &b)
#define sfdd(a, b)         scanf("%lf %lf", &a, &b)
#define sfiii(a, b, c)     scanf("%d %d %d", &a, &b, &c)
#define sflll(a, b, c)     scanf("%lld %lld %lld", &a, &b, &c)
#define sfuuu(a, b, c)     scanf("%llu %llu %llu", &a, &b, &c)
#define sfddd(a, b, c)     scanf("%lf %lf %lf", &a, &b, &c)

/**------- Printf----------*/
#define pf                 printf
#define pfig(a)            pf("%d ", a)
#define pfgap              pf(" ")
#define pfi(a)             printf("%d\n", a)
#define pfc(a)             printf("%c\n", a)
#define pfl(a)             printf("%lld\n", a)
#define pfu(a)             printf("%llu\n", a)
#define pfs(a)             printf("%s\n", a)
#define pfd(a)             printf("%.2lf\n", a)
#define pfii(a, b)         printf("%d %d\n", a, b)
#define pfll(a, b)         printf("%lld %lld\n", a, b)
#define pfuu(a, b)         printf("%llu %llu\n", a, b)
#define pfdd(a, b)         printf("%.2lf %.2lf\n", a, b)
#define pfiii(a, b, c)     printf("%d %d %d\n", a, b, c)
#define pflll(a, b, c)     printf("%lld %lld %lld\n", a, b, c)
#define pfuuu(a, b, c)     printf("%llu %llu %llu\n", a, b, c)
#define pfddd(a, b, c)     printf("%.2lf %.2lf %.2lf\n", a, b, c)
#define pnl                printf("\n")

/**--------File------------*/
#define output             freopen("output.txt","w",stdout)
#define input              freopen("input.txt","r",stdin)
#define inOut              input, output
#define Case               printf("Case %d: ", cases)
#define Casepp             cout << "Case " << cases << ": "

/**--------Constant------------*/
#define mx2                101
#define mx3                1001
#define mx4                10001
#define mx5                100001
#define mx6                1000001
#define INF                0x3f3f3f3f
#define eps                1e-8

/**--------Loops--------------*/
#define frab(i, a, b)      for(__typeof(b) i=(a); i<=(b); i++)
#define fr0(i, n)          frab(i, 0, n-1)
#define fr1(i, n)          frab(i, 1, n)
#define rfrab(i, a, b)     for(__typeof(b) i=(b); i>=a; i--)
#define rfr0(i, n)         rfrab(i, (n)-1, 0)
#define rfr1(i, n)         rfrab(i, n, 1)
#define frabv(i, a, b, v)  for(__typeof(b) i=(a); i<=(b); i+=v)
#define rfrabv(i, a, b, v) for(__typeof(b) i=(b); i>=a; i-=v)
#define frstl(i, s)        for(__typeof((s).end()) i=(s).begin(); i != (s).end(); i++)

/**-------Upper & Lower Bound-------*/
#define LB(a, v)            (lower_bound(all(a), v))
#define UB(a, v)            (upper_bound(all(a), v))

/**--------DeBug------------*/
#define watch(x)            cout<<(#x)<<" is "<<x<<"\n"
#define chk                 cout<<"Wtf"<<"\n"

const int mod = 1e9 + 7;
const int mx  = 2*mx5;

int n, ma, mb;
struct info{
    int a, b, c;
};
vector<info> va, vb;
vector<info> sa, sb;

void generateFun(){
    int tot = (1 << va.size());
    for(int i=1; i<tot; i++){
        int aa = 0, bb = 0, cc = 0;
        for(int j=0; j<va.size(); j++)
            if(i & (1<<j))
                aa += va[j].a,
                bb += va[j].b,
                cc += va[j].c;
        sa.pb({aa, bb, cc});
    }

    tot = (1 << vb.size());
    for(int i=1; i<tot; i++){
        int aa = 0, bb = 0, cc = 0;
        for(int j=0; j<vb.size(); j++)
            if(i & (1<<j))
                aa += vb[j].a,
                bb += vb[j].b,
                cc += vb[j].c;
        sb.pb({aa, bb, cc});
    }
    sort(all(sb));
}

int main(){
    sfiii(n, ma, mb);
    for(int i=0; i<n; i++){
        int a, b, c;
        sfiii(a,b,c);
        if(i&1) va.pb({a, b, c});
        else vb.pb({a, b, c});
    }
    generateFun();

    int ans = INF;

    for(int i=0; i<sa.size(); i++){
        info u = sa[i];
        for(int k=1; k<401; k++){
            int na = ma*k, nb = mb*k;
            if(na<u.a || nb<u.b) continue;
            int ra = na-u.a, rb = nb-u.b;
            int lw = 0, hh = sb.size()-1, res = -1;
            while(lw<=hh){
                int mid = (lw+hh)/2;
                if(sb[mid].a<ra) lw = mid+1;
                else if(sb[mid].a>ra) hh = mid-1;
                else{
                    if(sb[mid].b<rb) lw = mid+1;
                    else if(sb[mid].b>rb) hh = mid-1;
                    else {res=mid; break;}
                }
            }
            if(res != -1) ans = min(ans, u.c+sb[res].c);
        }
    }

    if(ans == INF) ans = -1;
    pfi(ans);

    return 0;
}



Compiler output:
In file included from /usr/include/c++/14/bits/stl_algobase.h:71,
                 from /usr/include/c++/14/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:51,
                 from a.cc:8:
/usr/include/c++/14/bits/predefined_ops.h: In instantiation of 'constexpr bool __gnu_cxx::__ops::_Iter_less_iter::operator()(_Iterator1, _Iterator2) const [with _Iterator1 = __gnu_cxx::__normal_iterator<info*, std::vector<info> >; _Iterator2 = __gnu_cxx::__normal_iterator<info*, std::vector<info> >]':
/usr/include/c++/14/bits/stl_algo.h:1777:14:   required from 'void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<info*, vector<info> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
 1777 |           if (__comp(__i, __first))
      |               ~~~~~~^~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1817:25:   required from 'void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<info*, vector<info> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
 1817 |           std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
      |           ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1908:31:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<info*, vector<info> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
 1908 |           std::__final_insertion_sort(__first, __last, __comp);
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:4772:18:   required from 'void std::sort(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<info*, vector<info> >]'
 4772 |       std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
      |       ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:189:9:   required from here
  189 |     sort(all(sb));
      |     ~~~~^~~~~~~~~
/usr/include/c++/14/bits/predefined_ops.h:45:23: error: no match for 'operator<' (operand types are 'info' and 'info')
   45 |       { return *__it1 < *__it2; }
      |                ~~~~~~~^~~~~~~~
In file included from /usr/include/c++/14/bits/stl_algobase.h:67:
/usr/include/c++/14/bits/stl_iterator.h:1241:5: note: candidate: 'template<class _IteratorL, class _IteratorR, class _Container> bool __gnu_cxx::operator<(const __normal_iterator<_IteratorL, _Container>&, const __normal_iterator<_IteratorR, _Container>&)'
 1241 |     operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1241:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/predefined_ops.h:45:23: note:   'info' is not derived from 'const __gnu_cxx::__normal_iterator<_IteratorL, _Container>'
   45 |       { return *__it1 < *__it2; }
      |                ~~~~~~~^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1249:5: note: candidate: 'template<class _Iterator, class _Container> bool __gnu_cxx::operator<(const __normal_iterator<_Iterator, _Container>&, const __normal_iterator<_Iterator, _Container>&)'
 1249 |     operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1249:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/predefined_ops.h:45:23: note:   'info' is not derived from 'const __gnu_cxx::__normal_iterator<_Iterator, _Container>'
   45 |       { return *__it1 < *__it2; }
      |                ~~~~~~~^~~~~~~~
/usr/include/c++/14/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Val_less_iter::operator()(_Value&, _Iterator) const [with _Value = info; _Iterator = __gnu_cxx::__normal_iterator<info*, std::vector<info> >]':
/usr/include/c++/14/bits/stl_algo.h:1757:20:   required from 'void std::__unguarded_linear_insert(_RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<info*, vector<info> >; _Compare = __gnu_cxx::__ops::_Val_less_iter]'
 1757 |       while (__comp(__val, __next))
      |              ~~~~~~^~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1785:36:   required from 'void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<info*, vector<info> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
 1785 |             std::__unguarded_linear_insert(__i,
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
 1786 |                                 __gnu_cxx::__ops::__val_comp_iter(__comp));
      |                                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1817:25:   required from 'void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<info*, vector<info> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
 1817 |           std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
      |           ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1908:31:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<info*, vector<info> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
 1908 |           std::__final_insertion_sort(__first, __last, __comp);
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:4772:18:   required from 'void std::sort(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<info*, vector<info> >]'
 4772 |       std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
      |       ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:189:9:   required from here
  189 |     sort(all(sb));
      |     ~~~~^~~~~~~~~
/usr/include/c++/14/bits/predefined_ops.h:98:22: error: no match for 'operator<' (operand types are 'info' and 'info')
   98 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1241:5: note: candidate: 'template<class _IteratorL, class _IteratorR, class _Container> bool __gnu_cxx::operator<(const __normal_iterator<_IteratorL, _Container>&, const __normal_iterator<_IteratorR, _Container>&)'
 1241 |     operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1241:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/predefined_ops.h:98:22: note:   'info' is not derived from 'const __gnu_cxx::__normal_iterator<_IteratorL, _Container>'
   98 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1249:5: note: candidate: 'template<class _Iterator, class _Container> bool __gnu_cxx::operator<(const __normal_iterator<_Iterator, _Container>&, const __normal_iterator<_Iterator, _Container>&)'
 1249 |     operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1249:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/predefined_ops.h:98:22: note:   'info' is not derived from 'const __gnu_cxx::__normal_iterator<_Iterator, _Container>'
   98 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
/usr/include/c++/14/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Iter_less_val::operator()(_Iterator, _Value&) const [with _Iterator = __gnu_cxx::__normal_iterator<info*, std::vector<info> >; _Value = info]':
/usr/include/c++/14/bits/stl_heap.h:140:48:   required from 'void std::__push_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<info*, vector<info> >; _Distance = long int; _Tp = info; _Compare = __gnu_cxx::__ops::_Iter_less_val]'
  140 |       while (__holeIndex > __topIndex && __comp(__first + __parent, __value))
      |                                          ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_heap.h:247:23:   required from 'void std::__adjust_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<info*, vector<info> >; _Distance = long int; _Tp = info; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
  247 |       std::__push_heap(__first, __holeIndex, __topIndex,
      |       ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  248 |                        _GLIBCXX_MOVE(__value), __cmp);
      |                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_heap.h:356:22:   required from 'void std::__make_heap(_RandomAccessIterator, _RandomAccessIterator, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<info*, vector<info> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
  356 |           std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value),
      |           ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  357 |                              __comp);
      |                              ~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1593:23:   required from 'void std::__heap_select(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<info*, vector<info> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
 1593 |       std::__make_heap(__first, __middle, __comp);
      |       ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1868:25:   required from 'void std::__partial_sort(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<info*, vector<info> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
 1868 |