How can we tell if a given ratio *x* is achievable? What we want is a set
*S* of cows satisfying,

$\frac{\sum_{i \in S} T_i}{\sum_{i \in S} W_i} \ge x$ and $\sum_{i \in S} W_i \ge w$.

The first condition is more easily expressed as

$\sum_{i \in S} (T_i - x W_i) \ge 0$.

Binary searching with real numbers can be tricky, but here, our life is
simplified because we know we are only looking for
$\lfloor 1000x \rfloor$. We can let *y* = 1000*x* and then
we want to find the maximum integer *y* such that

$\sum_{i \in S} (1000T_i - y W_i) \ge 0$ and $\sum_{i \in S} W_i \ge w$

is satisfiable for some *S*. Let's call the quantity
$1000T_i - y W_i$ the
*adjusted-talent-score*.

To do this, we can use a simple knapsack DP, where we compute, for each *j*
and *k*, the maximum adjusted-talent-score achievable with a subset of the
first *j* cows and exactly *k* weight. The maximum total weight is
very high, but we can take a shortcut since we do not care about weights higher
than *w* - or at least, for a given set of cows with weight at least
*w*, we don't care what its *exact* weight is. The DP, then, is
$O(wn)$. The total runtime would be $O(wn \log(t))$ where
*t* is the maximum value of
*y*.

#include <cstdio> #include <algorithm> #include <cassert> using namespace std; #define NMAX 250 #define WMAX 1000 #define infinite 1000000000000000000LL // The inputs int weights[NMAX]; int talent[NMAX]; int n; int w; // The dp state. // For 0 <= i < w, this is the maximum adjusted-talent-score achievable // with weight exactly i. // For i=w, this is the maximum talent achievable // with weight AT LEAST w. long long dp[WMAX + 1]; // Check if a ratio of y/1000 is achievable. bool doable(int y) { for (int i = 0; i <= w; i++) { dp[i] = -infinite; } dp[0] = 0; for (int j = 0; j < n; j++) { long long value = 1000*(long long)talent[j] - y*(long long)weights[j]; int inc = weights[j]; for (int k = w; k >= 0; k--) { int k1 = min(w, k + inc); if (dp[k] != -infinite) { if (dp[k1] < dp[k] + value) { dp[k1] = dp[k] + value; } } } } return dp[w] >= 0; } int main() { scanf("%d", &n); scanf("%d", &w); assert(1 <= n && n <= NMAX); assert(1 <= w && w <= WMAX); for (int i = 0; i < n; i++) { scanf("%d", &weights[i]); scanf("%d", &talent[i]); assert(1 <= weights[i] && weights[i] <= 1000000); assert(1 <= talent[i] && talent[i] <= 1000); } // Binary search // Invariant: lo <= answer < hi int lo = 0; int hi = (1000 * 250 * 1000) + 1; while (hi > lo + 1) { int mid = (lo + hi) / 2; if (doable(mid)) { lo = mid; } else { hi = mid; } } printf("%d\n", lo); }