MinhNGUYEN2k4

Untitled

Sep 20th, 2021
500
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define Task "ADVERT"
  4. #define watch(x) cout << #x << " = " << x << endl
  5. #define F first
  6. #define S second
  7. #define pb push_back
  8. #define mp make_pair
  9.  
  10. using namespace std;
  11.  
  12. typedef pair <int,int> pii;
  13. typedef pair <pii,int> ppi;
  14. typedef pair <int,pii> pip;
  15. typedef pair <pii,pii> ppp;
  16.  
  17. const int oo = 1e12;
  18. const int MOD = 0x3f3f3f3f;
  19. const int MAXN = 1e5 + 1;
  20.  
  21. int n, w, h, a[MAXN], b[MAXN];
  22.  
  23. bool advert(double k)
  24. {
  25.     double H = h, W = w;
  26.     int i = 1;
  27.     while (H >= 0 && i <= n)
  28.     {
  29.         double ai = a[i] * k, bi = b[i] * k;
  30.         if (b[i] != b[i - 1])
  31.         {
  32.             W = w - ai;
  33.             H -= bi;
  34.             if (W < 0) return 0;
  35.         }
  36.         else
  37.         {
  38.             if (W >= ai)
  39.             {
  40.                 W -= ai;
  41.             }
  42.             else
  43.             {
  44.                 W = w - ai;
  45.                 H -= bi;
  46.                 if (W < 0) return 0;
  47.             }
  48.         }
  49.         ++i;
  50.     }
  51.     if (H < 0) return false;
  52.     return true;
  53. }
  54.  
  55. signed main()
  56. {
  57.     ios_base::sync_with_stdio(false);
  58.     cin.tie(0);cout.tie(0);
  59.     cin >> n >> w >> h;
  60.     for (int i = 1; i <= n; i++) cin >> a[i] >> b[i];
  61.     double l = 0, r = 1e9;
  62.     while (r - l > 1e-4)
  63.     {
  64.         double mid = (l + r) / 2;
  65.         if (advert(mid)) l = mid;
  66.         else r = mid;
  67.     }
  68.     cout << setprecision(6) << fixed << l;
  69.     return 0;
  70. }
  71.  
RAW Paste Data