//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << " " <<
#define nl << "\n"
int n, p, q, a[2001];
bool possible(int w){
int dp[n+1][p+1];
for(int i=0; i<=n; ++i){
for(int j=0; j<=p; ++j){
dp[i][j] = i ? 1e10 : 0;
}
}
for(int i=1; i<=n; ++i){
int f0 = upper_bound(a, a+n, max(0LL, a[i]-w)) - a - 1;
int f1 = upper_bound(a, a+n, max(0LL, a[i]-2*w)) - a - 1;
int g0 = 0, g1 = 0;
while(g0+1<i and a[g0+1]+w-1<a[i]) ++g0;
while(g1+1<i and a[g1+1]+2*w-1<a[i]) ++g1;
assert(f0==g0 and f1==g1);
for(int j=0; j<=p; ++j){
// use
if(j){
dp[i][j] = min(dp[i][j], dp[f0][j-1]);
}
// don't
dp[i][j] = min(dp[i][j], dp[f1][j] + 1);
}
}
return dp[n][p]<=q;
}
signed main(){
ios_base::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> p >> q;
a[0] = 0;
for(int i=1; i<=n; ++i) cin >> a[i];
sort(a+1, a+n+1);
if(p>n or q>n){
cout << 1 nl;
return 0;
}
int low = 0, high = 1e9;
while(low<high){
int mid = (low+high)/2;
if(possible(mid)) high = mid;
else low = mid+1;
}
cout << low nl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
364 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
492 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
