fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define LL long long
  6. #define DD double
  7. #define mem(a, b) memset(a, b, sizeof(a))
  8. #define fast ios_base::sync_with_stdio(0);cin.tie(0)
  9.  
  10. const int mx1 = 15;
  11. const int mx2 = 105;
  12. const int mx3 = 1005;
  13. const int mx4 = 10005;
  14. const int mx5 = 100005;
  15. const int mx6 = 1000005;
  16. const LL inf = 1e18;
  17. const DD EPSILON = 1e-10;
  18.  
  19. LL _toggle(LL N, int pos) {return N = N ^ (1ll << pos);}
  20. LL _set(LL N, int pos) {return N = N | (1ll << pos);}
  21. LL _reset(LL N, int pos) {return N = N & ~(1ll << pos);}
  22. LL _set_bit(LL N, int pos, bool B){if(B){N |= (1LL << pos);}else{N &= ~(1LL << pos);}return N;}
  23. bool _get(LL N, int pos) {return (bool)(N & (1ll << pos));}
  24. bool _upper(char a) {return a >= 'A' && a <= 'Z';}
  25. bool _lower(char a) {return a >= 'a' && a <= 'z';}
  26. bool _digit(char a) {return a >= '0' && a <= '9';}
  27. DD _fmax(DD a, DD b) {if(fabs(a - b) < EPSILON) return a; return (a > b) ? a : b;}
  28. DD _fmin(DD a, DD b) {if(fabs(a - b) < EPSILON) return a; return (a < b) ? a : b;}
  29. bool _less(DD a, DD b) {if(fabs(a - b) < EPSILON) return false; return a < b;}
  30. bool _eql(DD a, DD b) {if(fabs(a - b) < EPSILON) return true; return a == b;}
  31.  
  32. int dx[] = {1, -1, 0, 0, -1, -1, 1, 1};
  33. int dy[] = {0, 0, 1, -1, -1, 1, -1, 1};
  34.  
  35. ///******************************************************///
  36. /*
  37. g++-14 E.cpp -o E
  38. */
  39.  
  40.  
  41. void clearAll()
  42. {
  43.  
  44. }
  45.  
  46. void solve()
  47. {
  48.     LL n, k;
  49.     cin >> n >> k;
  50.     vector<LL> a(n + 5, 0), p(n + 5, 0), b(n + 5, 0), q(n + 5, 0);
  51.     for(LL i = 1; i <= n; i++){
  52.         cin >> a[i] >> p[i] >> b[i] >> q[i];
  53.     }
  54.     LL lt = 1, rt = 1e9, mid;
  55.     while(lt <= rt){
  56.         mid = (lt + rt) / 2;
  57.         LL curTotalCost = 0;
  58.         for(LL i = 1; i <= n; i++){
  59.             LL curMnCost = 1e9;
  60.             LL needA, needB;
  61.             needA = (mid + a[i] - 1) / a[i];
  62.             for(LL j = 0; j <= 200; j++){
  63.                 if(needA - j < 0){
  64.                     break;
  65.                 }
  66.                 needB = (mid - j * a[i] + b[i] - 1) / b[i];
  67.                 curMnCost = min(curMnCost, (needA - j) * p[i] + needB * q[i]);
  68.             }
  69.             needB = (mid + b[i] - 1) / b[i];
  70.             for(LL j = 0; j <= 200; j++){
  71.                 if(needB - j < 0){
  72.                     break;
  73.                 }
  74.                 needA = (mid - j * b[i] + a[i] - 1) / a[i];
  75.                 curMnCost = min(curMnCost, needA * p[i] + (needB - j) * q[i]);
  76.             }
  77.             curTotalCost += curMnCost;
  78.         }
  79.         // cout << curTotalCost << ' ' << mid << '\n';
  80.         if(curTotalCost <= k){
  81.             lt = mid + 1;
  82.         }
  83.         else{
  84.             rt = mid - 1;
  85.         }
  86.     }
  87.     // LL curTotalCost = 0;
  88.     // for(LL i = 1; i <= n; i++){
  89.     //     LL curMnCost = 1e9;
  90.     //     LL needA, needB;
  91.     //     needA = (rt + a[i] - 1) / a[i];
  92.     //     for(LL j = 0; j <= 200; j++){
  93.     //         if(needA - j < 0){
  94.     //             break;
  95.     //         }
  96.     //         needB = (rt - j * a[i] + b[i] - 1) / b[i];
  97.     //         curMnCost = min(curMnCost, (needA - j) * p[i] + needB * q[i]);
  98.     //     }
  99.     //     needB = (rt + b[i] - 1) / b[i];
  100.     //     for(LL j = 0; j <= 200; j++){
  101.     //         if(needB - j < 0){
  102.     //             break;
  103.     //         }
  104.     //         needA = (rt - j * b[i] + a[i] - 1) / a[i];
  105.     //         curMnCost = min(curMnCost, needA * p[i] + (needB - j) * q[i]);
  106.     //     }
  107.     //     curTotalCost += curMnCost;
  108.     // }
  109.     cout << rt << '\n';
  110. }
  111.  
  112. void precalculation()
  113. {
  114.  
  115. }
  116.  
  117. int main()
  118. {
  119.     //freopen("input.txt", "r", stdin);
  120.     //freopen("output.txt", "w", stdout);
  121.     fast;
  122.     precalculation();
  123.     int TC = 1;
  124.     // cin >> TC;
  125.     while(TC--){
  126.         solve();
  127.     }
  128. }
  129.  
  130.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
1 1
1 10000000 1 10000000
stdout
copy 
200
https://ideone.com/fX1B6V
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!