#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n, p, q;
cin >> n >> p >> q;
vector<int> v(n);
for(int i =0; i < n; i++) cin >> v[i];
sort(v.begin(), v.end());
//for(int i =0; i < n; i++) cout << v[i];
int l = 1, r = 1e9;
int rez=1e9;
while(l<r)
{
int m = l+(r-l)/2;
int dp[p+1][q+1]={0};
if(p > 0)
dp[1][0]=v[0]+m-1;
if(q > 0)
dp[0][1]=v[0]+2*m-1;
int c =0;
for(int j = 2; j <= q; j++)
{
auto y = upper_bound(v.begin(), v.end(), dp[0][j-1]);
if(*y>=v[v.size()-1])
{
rez=min(rez, m);
r=m;
c=1;
break;
}
dp[0][j]=*y+2*m-1;
}
if(c)continue;
for(int i = 2; i <= p; i++)
{
auto x = upper_bound(v.begin(), v.end(), dp[i-1][0]);
if(*x>=v[v.size()-1])
{
rez=min(rez, m);
r=m;
c=1;
break;
}
dp[i][0]=*x+m-1;
}
if(c)continue;
for(int i = 1; i <= p; i++)
{
for(int j = 1; j <= q; j++)
{
auto x = upper_bound(v.begin(), v.end(), dp[i-1][j]);
auto y = upper_bound(v.begin(), v.end(), dp[i][j-1]);
if(*x>=v[v.size()-1]|| *y>=v[v.size()-1])
{
rez=min(rez, m);
r=m;
c=1;
break;
}
dp[i][j]=max(*x+m-1, *y+2*m-1);
}
if(c)break;
}
if(c)continue;
if(dp[p][q]>= v[v.size()-1])
{
rez=min(rez, m);
r=m;
}
else
{
l=m+1;
}
}
rez=min(l, rez);
cout << rez << "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |