Fshl0

Talent Show

Jun 7th, 2021
745
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. typedef long long ll;
  5.  
  6. const ll maxN = 300;
  7. const ll maxW = 1009;
  8.  
  9. int n, W, w[maxN], t[maxN];
  10. ll dp[maxW];
  11.  
  12. bool chk (ll x) {
  13.     for (int i = 1; i <= W; i++)
  14.         dp[i] = -INT_MAX;
  15.     dp[0] = 0;
  16.     for (int i = 0; i < n; i++) {
  17.         ll value = 1ll * 1000 * t[i] - 1ll * x * w[i];
  18.         for (int j = W; j >= 0; j--) {
  19.             ll nxt = min (W, j + w[i]);
  20.             if (dp[j] != -INT_MAX && dp[nxt] < dp[j] + value)
  21.                 dp[nxt] = dp[j] + value;
  22.         }
  23.     }
  24.     return dp[W] >= 0;
  25. }
  26.  
  27. int main () {
  28.     freopen ("talent.in", "r", stdin);
  29.     freopen ("talent.out", "w", stdout);
  30.     cin >> n >> W;
  31.     for (ll i = 0; i < n; i++)
  32.         cin >> w[i] >> t[i];
  33.     ll l = 0, r = 1000000 * 250 + 1;
  34.     while (r - l > 1) {
  35.         ll mid = l + (r - l) / 2;
  36.         if (chk (mid))
  37.             l = mid;
  38.         else r = mid - 1;
  39.     }
  40.     int res = chk (r) ? r : l;
  41.     cout << res << "\n";
  42.     return 0;
  43. }
  44.  
RAW Paste Data