#include <bits/stdc++.h>
#define LL long long
using namespace std;
int main()
{
LL n,p,q;
scanf("%lld %lld %lld",&n,&p,&q);
LL arr[n+5];
for(LL a=1;a<=n;a++)scanf("%lld",&arr[a]);
sort(arr+1,arr+n+1);
LL left=1,right=10,ans=-1;
q=min(q,n+5);
p=min(p,n+5);
LL all=p+q;
while(left<=right)
{
LL mid=(left+right)/2;
// printf("mid=%lld\n",mid);
LL dp[n+5][p+5];
// now, p , minimum q
for(LL a=0;a<=n+1;a++)for(LL b=0;b<=p;b++)dp[a][b]=1e9;
LL lastp=1,lastq=1;
dp[1][0]=0;
for(LL a=1;a<=n;a++)
{
while(lastp!=n+1 && arr[lastp]-arr[a]+1<=mid)lastp++;
while(lastq!=n+1 && arr[lastq]-arr[a]+1<=2*mid)lastq++;
for(LL b=p;b>=0;b--)
{
// printf("%lld %lld\n",a,b);
// if(dp[a][b]>=2500)continue;
dp[lastp][b+1]=min(dp[lastp][b+1],dp[a][b]);
dp[lastq][b]=min(dp[lastq][b],dp[a][b]+1);
// printf("dp[%lld][%lld] = %lld\n",lastp,b+1,dp[lastp][b+1]);
// printf("dp[%lld][%lld] = %lld\n",lastq,b,dp[lastq][b]);
}
}
bool bisa=false;
for(LL b=0;b<=p;b++)
{
if(dp[n+1][b]<=q){
bisa=1;
break;
}
}
if(bisa){
ans=mid;
right=mid-1;
}
else left=mid+1;
}
printf("%lld\n",ans);
}
Compilation message
watching.cpp: In function 'int main()':
watching.cpp:14:5: warning: unused variable 'all' [-Wunused-variable]
14 | LL all=p+q;
| ^~~
watching.cpp:7:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
7 | scanf("%lld %lld %lld",&n,&p,&q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp:9:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
9 | for(LL a=1;a<=n;a++)scanf("%lld",&arr[a]);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
