#include <bits/stdc++.h>
using namespace std;
inline void setup()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
int n, p, q, a[2001], f[2001][2001], l = 1, r = 1e9, m, res = 1;
inline bool Check(int inp)
{
for (int i = 1, p1 = 1, p2 = 1; i <= n; ++i)
{
while (a[p1] + inp - 1 < a[i])
{
p1++;
}
while (a[p2] + 2 * inp - 1 < a[i])
{
p2++;
}
for (int j = 0; j <= p; ++j)
{
f[i][j] = (j > 0 ? min(f[p1 - 1][j - 1], f[p2 - 1][j] + 1) : f[p2 - 1][j] + 1);
}
}
return (f[n][p] <= q);
}
int main()
{
setup();
cin >> n >> p >> q;
p = min(p, n);
for (int i = 1; i <= n; ++i)
{
cin >> a[i];
}
sort(a + 1, a + 1 + n);
while (l <= r)
{
m = (l + r) >> 1;
if (Check(m))
{
r = m - 1;
res = m;
}
else
{
l = m + 1;
}
}
cout << res;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |