This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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){
if(w<=0)return false;
for(int i=0;i<n;i++){
int ppp=0;
while(i-ppp>=0&&a[i]-w+1LL<=a[i-ppp])ppp++;
int pp=0;
while(i-pp>=0&&a[i]-2LL*w+1<=a[i-pp])pp++;
for(int j=0;j<=q;j++){
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(ll b=1e9;b>=1LL;b/=2LL)
while(!check(x+b))x+=b;
cout<<x+1<<endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |