#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, p, q, arr[2010];
int cost[2010];
bool can(int w) {
for(int i = 0; i < n; i++) cost[i] = 1;
int P = p, Q = q;
while(Q--) {
int cur = 0, curcost = 0, optL = 0, optR = 0, mx = -1;
for(int i = 0; i < n; i++) {
while(cur + 1 < n && arr[cur + 1] - arr[i] + 1 <= 2*w) {
curcost += cost[cur + 1];
cur++;
}
if(curcost > mx) mx = curcost, optL = i, optR = cur;
curcost -= cost[i];
}
for(int i = optL; i <= optR; i++) cost[i] = 0;
}
while(P--) {
int cur = 0, curcost = 0, optL = 0, optR = 0, mx = -1;
for(int i = 0; i < n; i++) {
while(cur + 1 < n && arr[cur + 1] - arr[i] + 1 <= w) {
curcost += cost[cur + 1];
cur++;
}
if(curcost > mx) mx = curcost, optL = i, optR = cur;
curcost -= cost[i];
}
for(int i = optL; i <= optR; i++) cost[i] = 0;
}
int cnt = 0;
for(int i = 0; i < n; i++) cnt += cost[i];
return cnt == 0;
}
int main() {
scanf("%d %d %d", &n, &p, &q);
for(int i = 0; i < n; i++)
scanf("%d", &arr[i]);
sort(arr,arr+n);
if(p + q >= n) {
puts("1");
return 0;
}
int lo = 1, hi = (int)1e9+10, ans;
while(lo <= hi) {
int mid = (lo + hi) >> 1;
if(can(mid)) hi = mid-1, ans = mid;
else lo = mid+1;
} printf("%d\n", ans);
return 0;
}
Compilation message
watching.cpp: In function 'int main()':
watching.cpp:42:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &n, &p, &q);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp:44:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &arr[i]);
~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
