fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define FIO ios_base::sync_with_stdio(0); cin.tie(0);
  3. #define pb push_back
  4. #define x first
  5. #define y second
  6. using namespace std;
  7. typedef long long ll;
  8. const long long N = 1e5 + 5, N1 = 2e5 + 5, MOD = 1e9 + 7, HS = 31, HS2 = 47, M2 = 1e9 + 9;
  9. const ll OO = 1e9;
  10. const double EPS = 1e-9;
  11. const double PI = acos(-1);
  12.  
  13.  
  14. int n, k, num;
  15. int a[N], b[N];
  16.  
  17.  
  18. bool valid(ll num){
  19.     int magic = k;
  20.  
  21.     for(int i = 0; i < n; ++i){
  22.         if(num * a[i] <= b[i]) continue;
  23.         if(num * a[i] <= b[i] + magic){
  24.             magic -= num * a[i] - b[i];
  25.             continue;
  26.         }
  27.  
  28.         return false;
  29.     }
  30.  
  31.     return true;
  32. }
  33.  
  34.  
  35. int bs(){
  36.     int l=-1, m, h=2e9+1;
  37.  
  38.     while(h > l+1){
  39.         m = l+(h-l)/2;
  40.         if(valid(m)) l = m;
  41.         else h = m;
  42.     }
  43.  
  44.     return l;
  45. }
  46.  
  47.  
  48. int main(){
  49.     FIO 
  50.     cin >> n >> k;
  51.  
  52.     for(int i = 0; i < n; ++i) cin >> a[i];
  53.     for(int i = 0; i < n; ++i) cin >> b[i];
  54.  
  55.     cout << bs() << "\n";
  56.  
  57.     return 0;
  58. }
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2000000000
https://ideone.com/c15NQF
language:
C++14 (gcc 8.3)
created:
17 days 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!