#include <bits/stdc++.h>
#define X first
#define Y second
#define MP make_pair
#define ll long long
using namespace std;
const int N = 2e3 + 3;
int n, p, q, a[N], dp[N][N], nx1[N], nx2[N];
queue< pair<int, int> > ord;
bool check(int lk){
memset(dp, -1, sizeof(dp));
for(int i = 1;i <= n;i++){
nx1[i] = upper_bound(a + i, a + n + 1, a[i] + lk - 1) - a - 1;
nx2[i] = upper_bound(a + i, a + n + 1, a[i] + lk + lk - 1) - a - 1;
}
dp[0][0] = 0;
ord.push(MP(0, 0));
bool good = 0;
while(!ord.empty()){
int x = ord.front().X, y = ord.front().Y;
ord.pop();
if(x - 1 >= 0)
dp[x][y] = max(dp[x][y], nx1[dp[x - 1][y] + 1]);
if(y - 1 >= 0)
dp[x][y] = max(dp[x][y], nx2[dp[x][y - 1] + 1]);
if(x + 1 <= p){
if(dp[x + 1][y] == -1)
ord.push(MP(x + 1, y));
dp[x + 1][y] = max(dp[x + 1][y], dp[x][y]);
}
if(y + 1 <= q){
if(dp[x][y + 1] == -1)
ord.push(MP(x, y + 1));
dp[x][y + 1] = max(dp[x][y + 1], dp[x][y]);
}
good |= dp[x][y] == n;
}
return good;
}
int main () {
scanf("%d %d %d", &n, &p, &q);
p = min(p, n), q = min(q, n);
for(int i = 1;i <= n;i++)
scanf("%d", a + i);
sort(a + 1, a + n + 1);
int tl = 1, tr = 100000000, tp = 100000000;
while(tl <= tr){
int tm = (tl + tr) / 2;
//cerr << tm << " " << check(tm) << "\n";
if(check(tm))
tr = tm - 1, tp = tm;
else
tl = tm + 1;
}
printf("%d", tp);
}
Compilation message
watching.cpp: In function 'int main()':
watching.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
47 | scanf("%d %d %d", &n, &p, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp:50:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
50 | scanf("%d", a + i);
| ~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
68 ms |
15980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
67 ms |
15980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
