#include <bits/stdc++.h>
using namespace std;
const int nx=2e3+10;
int n, p, q, dp[nx][nx], ans;
vector<int> v;
bool can(int w)
{
for (int i=0; i<n; i++)
{
int ps=(upper_bound(v.begin(), v.end(), v[i]-w)-v.begin())-1;
int pb=(upper_bound(v.begin(), v.end(), v[i]-2*w)-v.begin())-1;
for (int j=0; j<=q; j++) dp[i][j]=1e9, dp[i][j]=min((pb==-1||j==0)?(j==0?nx:1):dp[pb][j-1], (ps==-1)?1:dp[ps][j]+1);
}
return dp[n-1][q]<=p;
}
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>n>>p>>q;
v.resize(n);
for (auto &x:v) cin>>x;
sort(v.begin(), v.end());
if (p+q>=n)
{
cout<<1;
return 0;
}
int l=1, r=1e9+1000;
while (l<r)
{
int md=(l+r)/2;
//cout<<md<<'\n';
if (can(md)) r=md;
else l=md+1;
}
cout<<r;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
724 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
724 KB |
Output is correct |
8 |
Correct |
1 ms |
724 KB |
Output is correct |
9 |
Correct |
1 ms |
724 KB |
Output is correct |
10 |
Correct |
1 ms |
724 KB |
Output is correct |
11 |
Correct |
1 ms |
724 KB |
Output is correct |
12 |
Correct |
1 ms |
724 KB |
Output is correct |
13 |
Correct |
1 ms |
676 KB |
Output is correct |
14 |
Correct |
1 ms |
608 KB |
Output is correct |
15 |
Correct |
1 ms |
724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
8276 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
7 ms |
8476 KB |
Output is correct |
8 |
Correct |
68 ms |
14220 KB |
Output is correct |
9 |
Correct |
17 ms |
9332 KB |
Output is correct |
10 |
Correct |
16 ms |
9044 KB |
Output is correct |
11 |
Correct |
166 ms |
15948 KB |
Output is correct |
12 |
Correct |
88 ms |
16012 KB |
Output is correct |
13 |
Correct |
9 ms |
8404 KB |
Output is correct |
14 |
Correct |
9 ms |
8404 KB |
Output is correct |
15 |
Incorrect |
12 ms |
8460 KB |
Output isn't correct |
16 |
Halted |
0 ms |
0 KB |
- |