ulvis.paste.net

Paste Search Dynamic
Recent pastes
multiset
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. int n, x, k;
  5. multiset <int> a, olda;
  6.  
  7. bool ok(int tm) {
  8.     int m = tm;
  9.     while (m != 0 && !a.empty()) {
  10.         int back = *prev(a.end());
  11.         if (back > m * x) {
  12.             a.erase(prev(a.end()));
  13.             a.insert(back - x * m);
  14.             m = 0;
  15.         }
  16.         else {
  17.             a.erase(prev(a.end()));
  18.             if (back % x != 0 && back > x)
  19.                 a.insert(back % x);
  20.             m -= back / x;
  21.             if (back < x)
  22.                 m--;
  23.         }
  24.     }
  25.     int sum = 0;
  26.     for (auto i : a)
  27.         sum += i;
  28.     return sum <= k * tm;
  29. }
  30.  
  31. signed main() {
  32. #ifdef MY_DEBUG
  33.     freopen("../input.txt", "r", stdin);
  34.     freopen("../output.txt", "w", stdout);
  35. #else
  36.     ios_base::sync_with_stdio(0);
  37.     cin.tie(0);
  38.     //freopen("input.txt", "r", stdin);
  39.     //freopen("output.txt", "w", stdout);
  40. #endif
  41.  
  42.     cin >> n >> x >> k;
  43.     for (int  i = 0; i < n; ++i) {
  44.         int t;
  45.         cin >> t;
  46.         olda.insert(t);
  47.     }
  48.     int tl = 0, tr = 1e14 + 4;
  49.     while (tr - tl > 1) {
  50.         a = olda;
  51.         int tm = (tl + tr) / 2;
  52.         if (ok(tm))
  53.             tr = tm;
  54.         else
  55.             tl = tm;
  56.     }
  57.     cout << tr;
  58. }
Parsed in 0.011 seconds