Proportional Cake

因为 $X/Y = P/Q$ ，我们把蛋糕分成前后两组，分别有 $X_1, Y_1$ 和 $X_2, Y_2$ ，则： $Q(X_1+X_2) = P(Y_1+Y_2)$ ，也就有： $Q \cdot X_1 - P \cdot Y_1 = -(Q \cdot X_2 - P \cdot Y_2)$ 。所以我们保存前后subset对应在 $Q \cdot X - P \cdot Y$ ，然后meet-in-the-middle就可以了。

注意题目要求必须至少选一个蛋糕，所以要跳过两边都不选的记录。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int n, p, q;
int a[45], b[45], c[45];
vector<pi> ml, mr;
 
void generate(int l, int r, vector<pi> &m) {
    for (int bm = 0; bm < (1 << (r-l+1)); bm++) {
        int x = 0, y = 0, C = 0;
        for (int i = 0; i < r-l+1; i++)
            if (bm & (1 << i)) {
                x += a[l+i];
                y += b[l+i];
                C += c[l+i];
            }
        m.push_back({q*x-p*y, C});
    }
    sort(m.begin(), m.end());
}
 
int main() {
    scanf("%d %d %d", &n, &p, &q);
    for (int i = 0; i < n; i++)
        scanf("%d %d %d", &a[i], &b[i], &c[i]);
    generate(0, n/2-1, ml);
    generate(n/2, n-1, mr);
 
    int ans = 1e9;
    for (auto e: ml) {
        int d = e.first, C = e.second;
        pi t = {-d, 0};
        auto it = lower_bound(mr.begin(), mr.end(), t);
        if (it != mr.end() && C == 0 && it->second == 0)
            it++;       // skip zero-cost entry
        if (it != mr.end() && it->first == -d)
            ans = min(ans, C + it->second);
    }
    printf("%d", ans == 1e9 ? -1 : ans);
 
    return 0;
}