Advertisement
Guest User

Untitled

a guest
Apr 24th, 2017
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.32 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. typedef long long LL;
  9.  
  10. int cmp(int a, int b) {
  11.     return a > b;
  12. }
  13.  
  14. LL divCeil(LL numerator, LL denumerator) {
  15.     return (numerator + denumerator - 1) / denumerator;
  16. }
  17.  
  18. bool check(vector<int> &as, int x, int y, int toCheck) {
  19.     int hardRebukeCount = 0;
  20.     for (int a : as) {
  21.         /*
  22.         p * x + (toCheck - p) * y >= a
  23.         p * (x - y) + toCheck * y >= a
  24.         p >= (a - toCheck * y) / (x - y)
  25.         */
  26.         if (a - 1L * toCheck * y <= 0) {
  27.             continue;
  28.         }
  29.         int p = divCeil(a - toCheck * y, x - y);
  30.         hardRebukeCount += p;
  31.         if (hardRebukeCount > toCheck) {
  32.             return false;
  33.         }
  34.     }
  35.     return true;
  36. }
  37.  
  38. int main() {
  39.     ifstream cin("in.txt");
  40.  
  41.     int n, x, y;
  42.     cin >> n >> x >> y;
  43.     vector<int> a(n);
  44.     for (int i = 0; i < n; i++) {
  45.         cin >> a[i];
  46.     }
  47.     sort(a.begin(), a.end(), cmp);
  48.  
  49.     int l = 0, r = divCeil(a[0], x) + 1;
  50.     while (l + 1 != r) {
  51.         int m = (l + r) / 2;
  52.         if (check(a, x, y, m)) {
  53.             r = m;
  54.         } else {
  55.             l = m;
  56.         }
  57.     }
  58.     int res = r;
  59.     if (check(a, x, y, l)) {
  60.         res = l;
  61.     }
  62.     cout << res << "\n";
  63.     return 0;
  64. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement