Code : Sensor Optimization Dilemma 2

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

#define int long long

// Assumption : Green machine is the efficient machine.
// green_output/green_price >= red_output/red_price
int get_min_cost(int green_output, int green_price, int red_output,
                 int red_price, int need) {
    if (green_output * red_price < red_output * green_price) {
        return get_min_cost(red_output, red_price, green_output, green_price,
                            need);
    }

    int ans = 1e9;

    int lcm = (red_output * green_output) / __gcd(red_output, green_output);
    int limit = lcm / red_output;
    for (int red_machines = 0; red_machines <= limit; red_machines++) {
        int remain = max(0LL, need - red_machines * red_output);
        int green_machines =
            remain / green_output + (remain % green_output ? 1 : 0);
        ans = min(ans, red_machines * red_price + green_machines * green_price);
    }

    return ans;
}

void solve() {
    int n, x;
    cin >> n >> x;
    vector<int> a(n), p(n), b(n), q(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> p[i] >> b[i] >> q[i];
    }

    int low = 0, high = 1e9, res = 0;
    while (low <= high) {
        int mid = (low + high) / 2;
        int have = x;
        for (int i = 0; i < n; i++) {
            have -= get_min_cost(a[i], p[i], b[i], q[i], mid);
            if (have < 0) {
                break;
            }
        }
        if (have >= 0) {
            res = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    cout << res << "\n";
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    solve();
}