Submission #1689557

---

Source Code Expand

#include <algorithm>
#include <array>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <sstream>
#include <unordered_map>
#include <vector>


#define INF 4000000000000000000LL
#define MOD 1000000007
#define ALL(x) std::begin(x), std::end(x)


long long N, A, B, h[111111];


bool check(int c)
{
  int cc = 0;

  for (int i = 0; i < N; i ++) {
    if (h[i] < c * B)
        break;

    if (A == B) {
      if (h[i] > c * B)
        return false;
    }
    else {
      cc += (h[i] - c * B + A - B - 1) / (A - B);
    
      if (cc > c)
        return false;
    }
  }

  return true;
}


int main(int argc, char** argv)
{
  std::cin.tie(0);
  std::ios_base::sync_with_stdio(0);

  std::cout << std::fixed << std::setprecision(6);

  std::cin >> N >> A >> B;

  for (int i = 0; i < N; i ++)
    std::cin >> h[i];

  std::sort(h, h + N, std::greater<int>());

  long long l = -1, u = 1000000000;

  while (u - l > 1) {
    long long m = (l + u) / 2;

    (check(m) ? u : l) = m;
  }

  std::cout << u << std::endl;

  return 0;
}

Submission Info

Judge Result