好题。爱做。
标签：二分。
求最大的最小值，考虑二分答案。然后问题就转化成了（求 \(n\) 次）：有两种物品，每种物品有一个代价和价值，求获得不少于给定价值所需的最小代价。
下文记物品的代价为 \(w\)，价值为 \(v\)，所拿的数量为 \(cnt\)。
假设有两种物品 \(S\) 与 \(T\)，\(S\) 物品的性价比（价值 / 代价）比 \(T\) 高，那么有一种较优的拿法是全拿 \(S\)。但手玩一下发现，这不一定是最优的。那我们从大到小枚举所拿 \(S\) 物品的个数，剩下的价值用 \(T\) 物品补齐，然后计算出代价，取最小值即可。
但是直接枚举是会 TLE 的。注意到当我们拿了很多的 \(T\) 物品的时候，我们把若干 \(T\) 物品替换成相同价值的 \(S\) 物品会更优。具体地说，假如 \(cnt_T \times v_T\) 是 \(v_S\) 的倍数，那我们只需要把所有的 \(T\) 物品换成 \(\frac{cnt_T \times v_T}{v_S}\) 个 \(S\) 物品即可。
所以，\(cnt_T\) 的上界为 \(\text{lcm}(v_T, v_S) / v_T\)，再拿多就不优了。由于 \(\text{lcm}(v_T, v_S) \le v_T \times v_S\)，同理可以计算出少拿 \(S\) 物品的个数的上界，因此枚举上界不会超过 \(10^4\)。
然后就做完了。时间复杂度 \(O(n k\log V)\)。\(k\) 是单组枚举上界，不超过 \(10^4\)；\(V\) 是二分价值的值域，不超过 \(10^9\)。
（我赛时更豪放一点，\(k\) 开到了 \(10^5\)）
code :
#include <iostream>
#include <cstdio>
using namespace std;typedef long long ll;
typedef double db;
const int N = 110;
int a[N], b[N], c[N], d[N], n;
ll X;ll get(ll i, ll x) {db c1 = b[i] * 1.0 / a[i], c2 = d[i] * 1.0 / c[i];if(c1 > c2) swap(a[i], c[i]), swap(b[i], d[i]);ll cnt1 = (x + a[i] - 1) / a[i], res = 1e18;int k = 0;while(~cnt1 && k <= 100000) {ll cnt2 = (max(0ll, x - cnt1 * a[i]) + c[i] - 1) / c[i];res = min(res, cnt1 * b[i] + cnt2 * d[i]);cnt1--;k++;}return res;
}
bool chk(ll mid) {ll res = 0;for (int i = 1; i <= n; i++) res += get(i, mid);return res <= X;
}int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n >> X;for (int i = 1; i <= n; i++) cin >> a[i] >> b[i] >> c[i] >> d[i];ll l = 0, r = 1e9;while(l < r) {ll mid = (l + r + 1) / 2;if(chk(mid)) l = mid;else r = mid - 1;}cout << l;return 0;
}
