#include <bits/stdc++.h>
using namespace std;
const int R = 1e9;
int n, p, q;
set<int> s;
bool check(int w)
{
int dp[p+1][q+1];
for(int i=0; i<=p; i++)
for(int j=0; j<=q; j++)
dp[i][j] = 0;
bool ret = 0;
dp[0][0] = 0;
for(int i=0; i<=p && i <= n+3; i++)
{
for(int j=0; j<=q && i+j<=n+3; j++)
{
if(i > 0)
{
auto t = s.lower_bound(dp[i-1][j]+1);
if(t == s.end())
ret = 1;
else
dp[i][j] = max(dp[i][j], (*t)+w-1);
}
if(j > 0)
{
auto t = s.lower_bound(dp[i][j-1]+1);
if(t == s.end())
ret = 1;
else
dp[i][j] = max(dp[i][j], (*t)+2*w-1);
}
}
}
if(dp[p][q] >= *s.rbegin())
ret = 1;
return ret;
}
int binary()
{
int l = 1, r = R;
while(l < r)
{
int m = (l+r)/2;
if(check(m))
r = m;
else
l = m+1;
}
return l;
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> n >> p >> q;
for(int i=0; i<n; i++)
{
int a; cin >> a;
s.insert(a);
}
cout << binary();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |