#include <bits/stdc++.h>
using namespace std;
int n;
vector <int> events;
vector <vector <int>> dp;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int p, q;
cin >> n >> p >> q;
events = vector <int> (n+1);
for (int i = 1; i <= n; i++)
cin >> events[i];
sort(events.begin(), events.end());
if (p + q >= n) {
cout << 1 << '\n';
return 0;
}
dp = vector <vector <int>> (n+1, vector <int> (p+1, 1e9));
int lo = 1, hi = 2;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
dp[0][0] = 0;
vector <int> prev(n+1), prev2(n+1);
int pt = 0, pt2 = 0;
for (int i = 1; i <= n; i++) {
while (events[i] - mid >= events[pt])
pt++;
prev[i] = pt;
while (events[i] - mid*2 >= events[pt2])
pt2++;
prev2[i] = pt2;
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= p; j++) {
dp[i][j] = 1e9;
if (j-1 >= 0)
dp[i][j] = dp[i][j-1];
int it = prev2[i];
dp[i][j] = min(dp[i][j], dp[max(0, it-1)][j] + 1);
if (j > 0) {
it = prev[i];
dp[i][j] = min(dp[i][j], dp[max(0, it-1)][j-1]);
}
}
}
if (dp[n][p] > q)
lo = mid + 1;
else
hi = mid;
}
cout << lo << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
