#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define X first
#define Y second
#define piii pair<int,pii>
#define id1 (id<<1)
#define id2 ((id<<1)|1)
#define MASK(i) (1LL<<(i))
#define TIME "\nTime elapsed : "<<(double)clock()/1000<<" ms"
#define all(x) x.begin(),x.end()
#define BIT(a,b) ((a>>(b))&1)
using namespace std;
const int maxn=1e6;
int mod=1e9+7;
const int INF=1e9;
template < class X,class Y>
bool minimize(X &x,Y y)
{
if(x>y){x=y;return 1;}
return 0;
}
template <class X, class Y>
bool maximize(X &x,Y y)
{
if(x<y){x=y;return 1;}
return 0;
}
template<class X,class Y>
ll POW(X a,Y b)
{
ll res(1);
while(b>0)
{
if(b&1)res = (1LL*res*a)%mod;
a = (1LL*a*a)%mod;
b>>=1;
}
return res;
}
int n,p,q;
int a[maxn+1];
bool ok[maxn+1];
int res;
struct st
{
int id,x,y,t;
};
queue<st> myq;
bool check(int mid)
{
memset(ok,0,sizeof ok);
while(!myq.empty())myq.pop();
if(1 <= p)
{
myq.push({1,1,0,1});
ok[1] = 1;
}
if(1 <= q){
myq.push({1,0,1,2});
ok[1] = 1;
}
while(!myq.empty())
{
int id = myq.front().id;
int x = myq.front().x;
int y = myq.front().y;
int t = myq.front().t;
int dis = t*mid;
myq.pop();
if(ok[n])break;
int pos = id;
while(id + 1 <= n && a[id+1] - a[pos] + 1 <= dis)
{
id++;
ok[id] = 1;
}
if(id + 1 <= n)
{
id++;
if(x + 1 <= p){
myq.push({id,x + 1,y,1});
ok[id] = 1;
}
if(y + 1 <= q){
ok[id] = 1;
myq.push({id,x,y+1,2});
}
}
}
return ok[n];
}
int main()
{
ios::sync_with_stdio(false);cin.tie(0);
if (fopen("events.inp","r")){
//freopen("events.inp","r",stdin);
//freopen("events.out","w",stdout);
}
cin>>n>>p>>q;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a + 1, a + n + 1);
if(p + q >= n)return cout<<1,0;
int l = 1,r = 1e9;
while(l <= r)
{
int mid = (l+r)>>1;
if(check(mid))
{
res = mid;
r = mid-1;
}
else
l = mid + 1;
}
cout<<res;
cerr<<TIME;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2652 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
3 |
Correct |
1 ms |
2652 KB |
Output is correct |
4 |
Correct |
0 ms |
2396 KB |
Output is correct |
5 |
Correct |
1 ms |
2396 KB |
Output is correct |
6 |
Correct |
1 ms |
2396 KB |
Output is correct |
7 |
Correct |
1 ms |
2652 KB |
Output is correct |
8 |
Correct |
14 ms |
2844 KB |
Output is correct |
9 |
Correct |
12 ms |
2648 KB |
Output is correct |
10 |
Runtime error |
439 ms |
262144 KB |
Execution killed with signal 9 |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2652 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
3 |
Correct |
1 ms |
2396 KB |
Output is correct |
4 |
Correct |
1 ms |
2396 KB |
Output is correct |
5 |
Correct |
1 ms |
2396 KB |
Output is correct |
6 |
Correct |
1 ms |
2396 KB |
Output is correct |
7 |
Runtime error |
577 ms |
262144 KB |
Execution killed with signal 9 |
8 |
Halted |
0 ms |
0 KB |
- |