#include <bits/stdc++.h>
using namespace std;
#define MAXN 2001
int n,p,q;
int a[MAXN];
int dp[MAXN][MAXN];
bool check(int w)
{
for (int i=0;i<MAXN;i++)
{
for (int j=0;j<MAXN;j++) dp[i][j]=INT_MAX;
}
dp[0][0]=0;
for (int i=1;i<=n;i++)
{
int l1=0,r1=i-1;
int pos1=i-1;
while (l1<=r1)
{
int mid=(l1+r1)/2;
if (a[i]-a[mid]>=w) {pos1=mid;l1=mid+1;}
else r1=mid-1;
}
int l2=0,r2=i-1;
int pos2=i-1;
while (l2<=r2)
{
int mid=(l2+r2)/2;
if (a[i]-a[mid]>=2*w) {pos2=mid;l2=mid+1;}
else r2=mid-1;
}
for (long long j=0;j<=min(n,q);j++)
{
if (dp[pos1][j]==INT_MAX) continue;
dp[i][j]=min(dp[i][j],dp[pos1][j]+1);
}
for (long long j=0;j<min(n,q);j++)
{
if (dp[pos2][j]==INT_MAX) continue;
dp[i][j+1]=min(dp[i][j+1],dp[pos2][j]);
}
}
for (long long i=0;i<=min(n,q);i++)
{
if (dp[n][i]<=p) return true;
else continue;
}
return false;
}
int main()
{
cin>>n>>p>>q;
for (int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);
int l=1,r=1000000000;
int rez=1000000000;
while (l<=r)
{
int mid=(l+r)/2;
if (check(mid)) {rez=mid;r=mid-1;}
else l=mid+1;
}
cout<<rez<<endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
15964 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
53 ms |
16212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
