fork download
copy 
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <bits/stdc++.h>
  6. #include <set>
  7. #include <ext/pb_ds/assoc_container.hpp>
  8. #include <ext/pb_ds/tree_policy.hpp>
  9. #include <map>
  10. #define ll long long
  11. using namespace __gnu_pbds;
  12. using namespace std;
  13. template <class T>
  14. using ordered_set = tree<T , null_type , less<T> , rb_tree_tag , tree_order_statistics_node_update>;
  15. template <class T>
  16. using ordered_set1 = tree<T , null_type , greater<T> , rb_tree_tag , tree_order_statistics_node_update>;
  17. // less<T>/greater<T> = ascending/descending.
  18. // less_equal<>/greater_equal<> for ordered multiset
  19. // ordered_multiset note : s.find(), s.erase() don't work + s.upper_bound() and s.lower_bound() swap jobs;
  20. void fastIO(void) {
  21.     ios_base::sync_with_stdio(false);
  22.     cin.tie(NULL);
  23.     cout.tie(NULL);
  24.     //freopen("stdin", "r", stdin);
  25.     //freopen("stdout", "w", stdout);
  26. }
  27. ll n,k;
  28. struct ingredient {
  29.     ll cookiecount;
  30.     ll remainder;
  31.     ll req;
  32. };
  33. bool cmp(ingredient x, ingredient y) {
  34.     return x.cookiecount<y.cookiecount;
  35. }
  36. bool cmp2(ingredient x,ll y) {
  37.     return x.cookiecount < y;
  38. }
  39. bool enough(ll cookienum,vector<ingredient> &can) {
  40.     ll lastindex=lower_bound(can.begin(),can.end(),cookienum,cmp2)-can.begin();
  41.     ll temp = k;
  42.     for (ll i =0; i<lastindex; i++) {
  43.         if (temp<=0) return false;
  44.         temp = temp - (cookienum-can[i].cookiecount-1)*can[i].req - can[i].remainder;
  45.     }
  46.     return true;
  47. }
  48. int main() {
  49.     fastIO();
  50.     cin>>n>>k;
  51.     vector<ll> owned(n);
  52.     vector<ingredient> v(n);
  53.     for (ll i = 0; i<n; i++) {
  54.         cin>>v[i].req;
  55.     }
  56.     for (ll i = 0; i<n; i++) {
  57.         cin>>owned[i];
  58.     }
  59.     for (ll i = 0; i<n; i++) {
  60.         v[i].cookiecount=owned[i]/v[i].req;
  61.         v[i].remainder=v[i].req-(owned[i]%v[i].req);
  62.     }
  63.     sort(v.begin(),v.end(),cmp);
  64.     ll l = 0, r = 2e9,mid,ans=0;
  65.     while (l<=r) {
  66.         mid=(l+r)/2;
  67.         if (enough(mid,v)){
  68.             ans=mid;
  69.             l = mid + 1;
  70.         }
  71.         else {
  72.             r = mid - 1;
  73.         }
  74.     }
  75.     cout<<ans;
  76. }
  77.  
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
4 3
4 3 5 6
11 12 14 20
stdout
copy 
3
https://ideone.com/VQqTP5
language:
C++ (gcc 8.3)
created:
2 hours 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!