Advertisement
Guest User

Untitled

a guest
Feb 8th, 2021
506
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.43 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define int long long
  3.  
  4. using namespace std;
  5. const int BS = 333;
  6. const int INF = 1e18;
  7.  
  8. int Ceil(int a, int b) { return a / b + (a % b > 0); }
  9.  
  10. struct CHT {
  11.   deque<tuple<int, int, int>> stk;
  12.  
  13.   void InsertLine(int a, int b) {
  14.     int p = -INF;
  15.     while (stk.size()) {
  16.       auto [pp, ap, bp] = stk.back();
  17.       if (ap == a) p = bp < b ? INF : -INF;
  18.       else p = Ceil(b - bp, ap - a);
  19.       if (p > pp) break;
  20.       stk.pop_back();
  21.     }
  22.     if (p != INF) stk.emplace_back(p, a, b);
  23.   }
  24.   int EvalMin(int x) {
  25.     if (stk.empty()) return INF;
  26.     while ((int)stk.size() > 1 && get<0>(stk[1]) <= x)
  27.       stk.pop_front();
  28.     auto [_, a, b] = stk.front();
  29.     return a * x + b;
  30.   }
  31. };
  32.  
  33. int32_t main() {
  34.   int n, S; cin >> n >> S;
  35.   vector<pair<int, int>> v(n);
  36.   for (int i = 0; i < n; ++i)
  37.     cin >> v[i].second;
  38.   for (int i = 0; i < n; ++i)
  39.     cin >> v[i].first;
  40.  
  41.   sort(v.rbegin(), v.rend());
  42.   vector<CHT> chts(n / BS + 1);
  43.   vector<int> da(n / BS + 1), db(da);
  44.   vector<int> a(n), b(n);
  45.   for (int i = 0; i < n; ++i)
  46.     tie(a[i], b[i]) = v[i];
  47.  
  48.   auto rebuild = [&](int bi) {
  49.     chts[bi].stk.clear();
  50.     int l = bi * BS, r = min(n, l + BS);
  51.     for (int i = l; i < r; ++i) {
  52.       if (b[i] < INF)
  53.         chts[bi].InsertLine(a[i], b[i]);
  54.     }
  55.   };
  56.  
  57.   for (int i = 0; i < n; i += BS)
  58.     rebuild(i / BS);
  59.  
  60.   int ans = 0;
  61.   for (int i = 0; i < n; ++i) {
  62.     pair<int, int> best = {INF, -1};
  63.     for (int j = 0; j < (int)chts.size(); ++j) {
  64.       int now = chts[j].EvalMin(da[j]) + db[j];
  65.       best = min(best, make_pair(now, j));
  66.     }
  67.     assert(best.second != -1);
  68.     int bi = best.second;
  69.     int l = bi * BS, r = min(n, l + BS);
  70.     int choose = -1;
  71.     for (int i = l; i < r; ++i) {
  72.       b[i] += db[bi] + da[bi] * a[i];
  73.       if (b[i] == best.first)
  74.         choose = i;
  75.     }
  76.  
  77.  
  78.     da[bi] = db[bi] = 0;
  79.     assert(choose != -1);
  80.     cerr << "choose: " << choose + 1 << " with cost: " << best.first << endl;
  81.  
  82.     if (b[choose] <= S) {
  83.       S -= b[choose];
  84.       ans += 1;
  85.     } else break;
  86.    
  87.     for (int i = 0; i < bi; ++i)
  88.       db[i] += a[choose];
  89.     for (int i = l; i < r; ++i) {
  90.       if (i < choose) b[i] += a[choose];
  91.       else b[i] += a[i];
  92.     }
  93.     for (int i = bi + 1; i < (int)da.size(); ++i)
  94.       da[i] += 1;
  95.     a[choose] = 0; b[choose] = INF;
  96.    
  97.    
  98.     rebuild(bi);
  99.   }
  100.   cout << ans << endl;
  101.  
  102.  
  103.   return 0;
  104. }
  105.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement