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<bits/stdc++.h>
using namespace std;
const int N = 2001;
int n, p, q;
int a[N];
int dp[N][N];
int BS(int l,int r,int val) {
if(l == r) return l;
int m = (l + r) / 2;
if(a[m] > val) return BS(l,m,val);
return BS(m + 1,r,val);
}
bool ch(int w) {
memset(dp,0,sizeof dp);
for(int i = 0 ; i <= p ; ++i)
for(int j = 0 ; j <= q ; ++j) {
if(i == 0 && j == 0) continue;
if(i > 0) {
int k = dp[i - 1][j] + 1;
dp[i][j] = max(dp[i][j],BS(1,n + 1,a[k] + w - 1) - 1);
}
if(j > 0) {
int k = dp[i][j - 1] + 1;
dp[i][j] = max(dp[i][j],BS(1,n + 1,a[k] + w * 2 - 1) - 1);
}
if(dp[i][j] == n) return 1;
}
return 0;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n >> p >> q;
if(p + q >= n) { cout << "1"; exit(0); }
for(int i = 1 ; i <= n ; ++i)
cin >> a[i];
sort(a + 1,a + 1 + n);
int L = 1, R = 1e9;
while(L != R) {
int M = (L + R) / 2;
if(ch(M)) R = M;
else L = M + 1;
}
cout << L << endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |