[USACO18OPEN] Talent Show G

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, W;
int w[255], t[255]; // w:重量 t:才艺
int v[255];         // 对应价值
int f[1005];        // f[i] 存 i 重量下的最大价值
bool check(int mid)
{
    for (int i = 1; i <= n; i++)
        v[i] = (1000 * t[i] - mid * w[i]);
    for (int i = 0; i <= W; i++)
        f[i] = -1'000'000'000'000'000'000;
    f[0] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = W; j >= 0; j--)
        {
            // j->j+v[i]
            int jj = min(W, j + w[i]);
            f[jj] = max(f[jj], f[j] + v[i]);
        }
    return f[W] >= 0;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> W;
    for (int i = 1; i <= n; i++)
        cin >> w[i] >> t[i];
    int l = 1;
    int r = 1000000;
    int ans;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if (check(mid))
        {
            ans = mid;
            l = mid + 1;
        }
        else
            r = mid - 1;
    }
    cout << ans;
    return 0;
}