paulomiranda98

Untitled

Feb 20th, 2021
843
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define F first
  3. #define S second
  4. #define all(x) x.begin(),x.end()
  5. #define endl '\n'
  6.  
  7. using namespace std;
  8.  
  9. using ll = long long;
  10. using pii = pair<int, int>;
  11. const int INF = 0x3f3f3f3f;
  12. const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
  13. const int MOD = 1000000007;
  14. const int dx[] = { 0, 0, -1, 1, 1, -1,  1, -1};
  15. const int dy[] = {-1, 1,  0, 0, 1, -1, -1,  1};
  16.  
  17.  
  18. ll AP(ll a, ll b){
  19.   return ((a+b)*(b-a+1))/2;
  20. }
  21. const int MAXN = 200010;
  22. int a[MAXN], b[MAXN];
  23. int n, m;
  24. ll f(ll x){
  25.   ll sum = 0;
  26.   for(int i=0; i<n; i++){
  27.     ll t = (a[i]-x)/b[i];
  28.     if(x <= a[i])
  29.       sum += (t+1);
  30.   }
  31.   return sum;
  32. }
  33.  
  34. int main() {
  35.   ios_base::sync_with_stdio(false); cin.tie(NULL);
  36.  
  37.   cin >> n >> m;
  38.  
  39.   for(int i=0; i<n; i++){
  40.     cin >> a[i];
  41.   }
  42.   for(int i=0; i<n; i++){
  43.     cin >> b[i];
  44.   }
  45.   ll lo=2, hi=1e9, mn=1;
  46.   while(lo<=hi){
  47.     ll mid = (lo+hi)/2;
  48.     if(f(mid) >= m){
  49.       mn = mid;
  50.       lo = mid+1;
  51.     }else{
  52.       hi = mid-1;
  53.     }
  54.   }
  55.  
  56.   ll sum = 0;
  57.   for(int i=0; i<n; i++){
  58.     ll t = (a[i]-mn)/b[i];
  59.     if(mn <= a[i]){
  60.       sum += a[i]*(t+1) - b[i]*AP(0, t);
  61.     }
  62.   }
  63.   ll get = f(mn);
  64.   if(mn == 1){
  65.     get += m;
  66.     sum += m;
  67.   }
  68.   if(get >= m){
  69.     sum -= (get-m)*mn;
  70.   }
  71.   cout << sum << endl;
  72.   return 0;
  73. }
  74.  
RAW Paste Data