Submission #4063313

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
// ==================================================
using i64 = int64_t; using u64 = uint64_t;
#define rep(i,a,b) for(i64 i=(int64_t)(a);i<(int64_t)(b);i++)
#define repn(i,n) rep(i,0,n)
#define din(t, ...) t __VA_ARGS__;_din(__VA_ARGS__)
#define stlv(t,n) vector<t> n
#define stls(t,n) set<t> n
void _din() {} void dout() { cout << endl; }
template <typename T, typename ... Args> inline void _din(T& head, Args& ... rest) { cin >> head; _din(rest...); }
template <typename T, typename ... Args> inline void dout(T head, Args ... rest) { cout << head; if (sizeof...(rest)) cout << ' '; dout(rest...); }
template <typename T>inline void vsortg(vector<T>& v) { sort(v.begin(), v.end(), greater<T>()); }
template <typename T>inline void vsortl(vector<T>& v) { sort(v.begin(), v.end(), less<T>()); }
template <typename T> inline T nmax(T f1, T f2) { return max(f1, f2); }
template <typename T, typename ... Args> inline T nmax(T first, Args ... rest) { return nmax(first, nmax(rest...)); }
template <typename T> inline T nmin(T f1, T f2) { return min(f1, f2); }
template <typename T, typename ... Args> inline T nmin(T first, Args ... rest) { return nmin(first, nmin(rest...)); }
// ==================================================
using it = vector<int>::iterator;
inline void ck(const it& bg, const it& ed, int& d, int& t, int& b, bool& res)
{
	int ft = t;
	for (auto i = upper_bound(bg, ed, b * t), bg = i; i != ed; i++)
	{
		int rest = *i - b * t;
		ft -= (rest + d - 1) / d;
		if (ft < 0)
		{
			res = false;
			break;
		}
	}
}
int main()
{
	din(int, n, a, b);
	stlv(int, m(n));
	repn(i, n) { din(, m[i]); }
	vsortl(m);
	int d = a - b;
	int rb = (m[m.size() - 1] + d - 1) / d + 1, lb = 1;
	int t = (lb + rb) / 2;
	auto li = m.begin();
	while (true)
	{
		if (lb == rb) break;
		bool res = true;
		int ft = t;
		ck(li, m.end(), d, t, b, res);
		if (res) rb = t;
		else lb = t + 1;
		t = (lb + rb) / 2;
	}
	bool res = true;
	ck(m.begin(), m.end(), d, lb, b, res);
	if (res) dout(lb);
	else dout(lb + 1);
}

Submission Info

Judge Result