#include <bits/stdc++.h>
#define FLASH ios_base::sync_with_stdio(0);
#define ll long long
#define debt(x,y)cout<<"#x = "<<(x)<<" and "<<"#y = "<<(y)<<endl;
#define deb(x)cout<<"#x = "<<(x)<<endl;
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define endl "\n"
#define arr(a,n) for(ll i=1;i<=n;i++) cout<<a[i]<<" "; cout << "\n";
#define vecc(a,n) for(ll i=0;i<n;i++) cout<<a[i]<<" "; cout << "\n";
using namespace std;
ll dp[2010][2010];
vector<ll>massiv;
ll n,p,q;
ll f(ll w)
{
memset(dp,0,sizeof(dp));
ll pointbig=0;
ll pointsmall=0;
for(ll i=0;i<n;i++)
{
while(pointsmall<n && massiv[i]-massiv[pointsmall]>=w)pointsmall++;
while(pointbig<n && massiv[i]-massiv[pointbig]>=2*w)pointbig++;
for(ll j=0;j<=min(q,n);j++)
{
if(j==0)
{
if(pointsmall==0)dp[i][j]=1;
else dp[i][j]=dp[pointsmall-1][j]+1;
}
else
{
if(pointbig==0)dp[i][j]=0;
else if(pointsmall==0)dp[i][j]=min(dp[pointbig-1][j-1],1LL);
else dp[i][j]=min(dp[pointsmall-1][j]+1,dp[pointbig-1][j-1]);
}
}
}
ll minn=LLONG_MAX;
for(ll i=0;i<=min(q,n);i++)minn=min(minn,dp[n-1][i]);
if(minn<=p)return 1;
else return 0;
}
int main(){
FLASH;
cin>>n>>p>>q;
for(ll i=1;i<=n;i++){ll x;cin>>x;massiv.pb(x);}
sort(all(massiv));
ll nac=0;
ll konec=massiv.back()+10;
ll minn=LONG_MAX;
while(nac<=konec)
{
ll mid=nac+(konec-nac)/2;
ll check=f(mid);
if(check==1){minn=min(minn,mid);konec=mid-1;}
else nac=mid+1;
}
cout<<minn<<endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
133 ms |
32000 KB |
Output is correct |
| 2 |
Incorrect |
125 ms |
32120 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
133 ms |
31996 KB |
Output is correct |
| 2 |
Incorrect |
115 ms |
32000 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
