#include <bits/stdc++.h>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
//#define int long long
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
int main() {
int n, p, q;
cin >> n >> p >> q;
p = min(n, p);
q = min(n, q);
vector<int> v(n+1);
for(int i=1; i<=n; i++) cin >> v[i];
sort(1+all(v));
vector<vector<vector<bool> > > dp(n+5, vector<vector<bool>>(p+5, vector<bool>(q+5)));
auto f = [&](int mid) {
for(int i=0; i<=n; i++)
for(int j=0; j<=p; j++)
for(int k=0; k<=q; k++) dp[i][j][k] = 0;
dp[0][0][0] = 1;
for(int i=1; i<=n; i++) {
for(int j=0; j<=p; j++) {
for(int k=0; k<=q; k++) {
if(j) {
int l=1, r=i, pos=0;
while(l <= r) {
int m = (l + r) / 2;
if(v[i] - v[m] < mid) pos = m, r = m - 1;
else l = m + 1;
}
if(dp[pos-1][j-1][k]) dp[i][j][k] = 1;
}
if(k) {
int l=1, r=i, pos=0;
while(l <= r) {
int m = (l + r) / 2;
if(v[i] - v[m] < 2ll * mid) pos = m, r = m - 1;
else l = m + 1;
}
if(dp[pos-1][j][k-1]) dp[i][j][k] = 1;
}
}
}
}
for(int i=0; i<=p; i++)
for(int j=0; j<=q; j++)
if(dp[n][i][j]) return 1;
return 0;
};
int l=0, r=1e9, ans = 1e9;
while(l <= r) {
int mid = (l + r) / 2;
if(f(mid)) ans = mid, r = mid - 1;
else l = mid + 1;
}
cout << ans << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
1376 KB |
Output is correct |
2 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |