#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int nax=2e3+3;
int n,p,q;
ll a[nax];
int dp[nax][nax];
bool check(ll w){
for(int i=0;i<n;i++){
int ppp=0;
while(i-ppp>=0&&a[i]-w+1<a[i-ppp])ppp++;
int pp=0;
while(i-pp>=0&&a[i]-2*w+1<a[i-pp])pp++;
for(int j=0;j<=q;j++){
if(i==0&&j==0){
dp[i][j]=1;
continue;
}
if(i-ppp<0)dp[i][j]=1;
else dp[i][j]=dp[i-ppp][j]+1;
if(j!=0){
if(i-pp<0)dp[i][j]=0;
else dp[i][j]=min(dp[i][j],dp[i-pp][j-1]);
}
}
}
return dp[n-1][q]<=p;
}
int main(){
cin>>n>>p>>q;
if(p+q>=n){
cout<<1<<endl;
return 0;
}
for(int i=0;i<n;i++)cin>>a[i];
sort(a,a+n);
ll x=-1;
for(int b=1e9;b>=1;b/=2)
while(!check(x+b))x+=b;
cout<<x+1<<endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
748 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
81 ms |
8424 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Incorrect |
47 ms |
8556 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |