#include <bits/stdc++.h>
using namespace std;
int l,r,mid,n,p,q,a[2005],dp[2005][2005];
vector <int> v;
deque <int> dq;
map <int,bool> m;
int main(){
scanf("%d%d%d",&n,&p,&q);
for (int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
sort(a+1,a+1+n);
for (int i=1;i<=n;i++){
for (int j=i;j<=n;j++){
if (!m[a[j]-a[i]+1])
v.push_back(a[j]-a[i]+1);
if (!m[(a[j]-a[i]+1)/2+(a[j]-a[i]+1)%2])
v.push_back((a[j]-a[i]+1)/2+(a[j]-a[i]+1)%2);
m[(a[j]-a[i]+1)/2+(a[j]-a[i]+1)%2]=true;
m[a[j]-a[i]+1]=true;
}
}
sort(v.begin(),v.end());
l=0; r=(int)v.size()-1;
while (l < r){
mid=(l+r)/2;
for (int i=0;i<=min(n,q);i++){ //used how many large
for (int j=1;j<=n;j++){
dp[i][j]=1e9;
}
}
for (int i=0;i<=min(n,q);i++){ //used how many large
if (i > 0){
dq.push_back(0);
for (int j=1;j<=n;j++){
/* while (!dq.empty() && a[j]-a[dq.front()+1]+1 > 2*v[mid]) dq.pop_front();
if (dq.empty()){
l=mid+1;
while (!dq.empty()) dq.pop_front();
goto out;
}
else
dp[i][j]=dp[i-1][dq.front()];
while (!dq.empty() && dp[i-1][j] <= dp[i-1][dq.back()]) dq.pop_back();
dq.push_back(j);
}
while (!dq.empty()) dq.pop_back();Z*/
}
dq.push_back(0);
for (int j=1;j<=n;j++){
/* while (!dq.empty() && a[j]-a[dq.front()+1]+1 > v[mid]) dq.pop_front();
if (!dq.empty())
dp[i][j]=min(dp[i][j],dp[i][dq.front()]+1);
while (!dq.empty() && dp[i][j] <= dp[i][dq.back()]) dq.pop_back();
dq.push_back(j);*/
}
while (!dq.empty()) dq.pop_back();
}
if (dp[min(n,q)][n] <= p)
r=mid;
else
l=mid+1;
out:;
}
printf("%d\n",v[l]);
return 0;
}
Compilation message
watching.cpp: In function 'int main()':
watching.cpp:68:1: error: expected '}' at end of input
68 | }
| ^
watching.cpp:8:11: note: to match this '{'
8 | int main(){
| ^
watching.cpp:64:3: warning: label 'out' defined but not used [-Wunused-label]
64 | out:;
| ^~~
watching.cpp:9:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
9 | scanf("%d%d%d",&n,&p,&q);
| ~~~~~^~~~~~~~~~~~~~~~~~~
watching.cpp:11:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
11 | scanf("%d",&a[i]);
| ~~~~~^~~~~~~~~~~~
