#include <bits/stdc++.h>
using namespace std;
int a[2001];
int dp[2001][2001];
int pre1[2001],pre2[2001];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,p,q;
cin >> n >> p >> q;
for(int i=1;i<=n;i++){
cin >> a[i];
}
sort(a+1,a+n+1);
if(p+q>=n){
cout << 1;
return 0;
}
a[0]=-1000000000;
int l=1,r=1000000000;
while(l!=r){
int mid=l+r>>1;
int k=0,y=0;
for(int i=1;i<=p;i++){
dp[0][i]=0;
}
for(int i=1;i<=n;i++){
dp[i][0]=1e9;
while(a[i]-mid>a[k+1]) k++;
while(a[i]-2*mid>a[y+1]) y++;
pre1[i]=k;
pre2[i]=y;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=p;j++){
int b=a[i]-mid+1;
int id=pre1[i];
b=a[i]-2*mid+1;
int id1=pre2[i];
dp[i][j]=min(dp[id][j-1],dp[id1][j]+1);
}
}
if(dp[n][p]>q){
l=mid+1;
}
else r=mid;
}
//cout << l << endl;
int mid=l,k=0,y=0;
for(int i=1;i<=p;i++){
dp[0][i]=0;
}
for(int i=1;i<=n;i++){
dp[i][0]=1e9;
while(a[i]-mid>a[k+1]) k++;
while(a[i]-2*mid>a[y+1]) y++;
pre1[i]=k;
pre2[i]=y;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=p;j++){
int b=a[i]-mid+1;
int id=pre1[i];
b=a[i]-2*mid+1;
int id1=pre2[i];
dp[i][j]=min(dp[id][j-1],dp[id1][j]+1);
//cout << dp[i][j] << ' ' << i << ' ' << j << endl;
}
}
if(dp[n][p]>q){
l++;
}
cout << l;
}
Compilation message
watching.cpp: In function 'int main()':
watching.cpp:23:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
23 | int mid=l+r>>1;
| ~^~
watching.cpp:37:9: warning: variable 'b' set but not used [-Wunused-but-set-variable]
37 | int b=a[i]-mid+1;
| ^
watching.cpp:63:8: warning: variable 'b' set but not used [-Wunused-but-set-variable]
63 | int b=a[i]-mid+1;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
8428 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
