Submission #4063203
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...)); }
// ==================================================
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;
while (true)
{
if (lb == rb) break;
bool res = true;
int ft = t;
for (auto i = upper_bound(m.begin(), m.end(), b*t); i != m.end(); i++)
{
int rest = *i - b * t;
ft -= (rest + d - 1) / d;
if (ft < 0)
{
res = false;
break;
}
}
if (res) rb = t;
else lb = t + 1;
t = (lb + rb) / 2;
}
dout(lb);
}
Submission Info
Submission Time |
|
Task |
D - Widespread |
User |
Mask |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
1847 Byte |
Status |
WA |
Exec Time |
50 ms |
Memory |
640 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 400 |
Status |
|
|
Set Name |
Test Cases |
Sample |
a01, a02, a03 |
All |
a01, a02, a03, b04, b05, b06, b07, b08, b09, b10, b11, b12, b13 |
Case Name |
Status |
Exec Time |
Memory |
a01 |
AC |
1 ms |
256 KB |
a02 |
AC |
1 ms |
256 KB |
a03 |
AC |
1 ms |
256 KB |
b04 |
AC |
1 ms |
256 KB |
b05 |
WA |
45 ms |
640 KB |
b06 |
AC |
50 ms |
640 KB |
b07 |
WA |
45 ms |
640 KB |
b08 |
WA |
45 ms |
640 KB |
b09 |
AC |
47 ms |
640 KB |
b10 |
WA |
47 ms |
640 KB |
b11 |
WA |
47 ms |
640 KB |
b12 |
WA |
47 ms |
640 KB |
b13 |
WA |
47 ms |
640 KB |