This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
const int N = 2000 + 5;
int n, p, q;
int a[N];
set<pair<int, int>> st;
int dp[N][N];
bool check(int mid){
for(int i = 1; i <= n; i++){
for (int j = 0; j <= n; j++) dp[i][j] = 1e9;
for(int j = 0; j <= i; j++){
/// a[i]-mid+1 a[i]
auto it = st.lower_bound({a[i] - mid + 1, 0});
it--; int l1 = (*it).second;
auto it1 = st.lower_bound({a[i] - 2 * mid + 1, 0});
it1--; int l2 = (*it1).second;
if (j == 0) dp[i][j] = dp[l2][j] + 1;
else dp[i][j] = min(dp[l1][j - 1], dp[l2][j] + 1);
if (i == n && j <= p && dp[i][j] <= q) return 1;
}
}
return 0;
}
int main(){
cin >> n >> p >> q;
p = min(p, n);
q = min(q, n);
st.insert({-1e9, 0});
for(int i = 1; i <= n; i++){
cin >> a[i];
}
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; i++) {
st.insert({a[i], i});
}
int l = 1, r = 1e9;
int ans = 0;
while(l <= r){
int mid = l + (r-l)/2;
if(check(mid)){
r = mid-1;
ans = mid;
}else {
l = mid + 1;
}
}
cout << ans << endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |