# include <bits/stdc++.h>
# define ll long long
using namespace std;
int N, P, Q;
vector<int> arr;
int mn[2001][2001];
int edge[2][2001];
bool cek(int a) {
// set edge nya dulu
for(int i=0;i<N;i++) {
int T = arr[i] + a - 1;
edge[0][i] = upper_bound(arr.begin(), arr.end(), T) - arr.begin();
T += a;
edge[1][i] = upper_bound(arr.begin(), arr.end(), T) - arr.begin();
// if(a == 4) cout<<i<<" "<<edge[0][i]<<" "<<edge[1][i]<<endl;
}
if(P < Q) {
for(int d=0;d<=N;d++) {
for(int a=0;a<=P;a++) mn[d][a] = 1e9;
}
priority_queue< pair<int, pair<int, int> > > PQ;
PQ.push(make_pair(0, make_pair(0, 0)));
while(!PQ.empty()) {
int x, y, z;
x = PQ.top().second.first;
y = PQ.top().second.second;
z = PQ.top().first;
PQ.pop();
if(-z > Q) continue;
if(mn[x][-y] != 1e9) continue;
// if(a == 1) cout<<x<<" "<<y<<" "<<z<<endl;
mn[x][-y] = z;
if(x == N) return 1;
PQ.push(make_pair(z, make_pair(edge[0][x], y-1)));
PQ.push(make_pair(z-1, make_pair(edge[1][x], y)));
}
return 0;
} else {
for(int d=0;d<=N;d++) {
for(int a=0;a<=Q;a++) mn[d][a] = 1e9;
}
priority_queue< pair<int, pair<int, int> > > PQ;
PQ.push(make_pair(0, make_pair(0, 0)));
while(!PQ.empty()) {
int x, y, z;
x = PQ.top().second.first;
y = PQ.top().second.second;
z = PQ.top().first;
PQ.pop();
if(-z > P) continue;
if(mn[x][-y] != 1e9) continue;
// if(a == 1) cout<<x<<" "<<y<<" "<<z<<endl;
mn[x][-y] = z;
if(x == N) return 1;
PQ.push(make_pair(z, make_pair(edge[1][x], y-1)));
PQ.push(make_pair(z-1, make_pair(edge[0][x], y)));
}
return 0;
}
for(int d=0;d<=N;d++) {
for(int a=0;a<=P;a++) mn[d][a] = 1e9;
}
priority_queue< pair<int, pair<int, int> > > PQ;
PQ.push(make_pair(0, make_pair(0, 0)));
while(!PQ.empty()) {
int x, y, z;
x = PQ.top().second.second;
y = PQ.top().second.first;
z = PQ.top().first;
PQ.pop();
if(-z > Q) continue;
if(mn[x][-y] != 1e9) continue;
// if(a == 1) cout<<x<<" "<<y<<" "<<z<<endl;
mn[x][-y] = z;
if(x == N) return 1;
PQ.push(make_pair(z, make_pair(edge[0][x], y - 1)));
PQ.push(make_pair(z-1, make_pair(edge[1][x], y)));
}
return 0;
}
int main() {
scanf("%d %d %d", &N, &P, &Q);
arr.resize(N);
for(int i=0;i<N;i++) scanf("%d", &arr[i]);
sort(arr.begin(), arr.end());
if(P + Q >= N) {
printf("1\n");
return 0;
}
// cout<<cek(4)<<endl;
int l = 1, r = 1e9, ans = -1;
while(l <= r) {
int mid = (l + r) / 2;
if(cek(mid)) {
ans = mid;
r = mid - 1;
} else l = mid + 1;
}
printf("%d\n", ans);
}
Compilation message
watching.cpp: In function 'int main()':
watching.cpp:94:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
94 | scanf("%d %d %d", &N, &P, &Q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp:96:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
96 | for(int i=0;i<N;i++) scanf("%d", &arr[i]);
| ~~~~~^~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
596 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
596 KB |
Output is correct |
8 |
Correct |
1 ms |
596 KB |
Output is correct |
9 |
Correct |
1 ms |
724 KB |
Output is correct |
10 |
Correct |
3 ms |
724 KB |
Output is correct |
11 |
Correct |
3 ms |
724 KB |
Output is correct |
12 |
Correct |
5 ms |
724 KB |
Output is correct |
13 |
Correct |
1 ms |
596 KB |
Output is correct |
14 |
Correct |
1 ms |
596 KB |
Output is correct |
15 |
Correct |
1 ms |
724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
8276 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
10 ms |
8424 KB |
Output is correct |
8 |
Correct |
304 ms |
9324 KB |
Output is correct |
9 |
Correct |
290 ms |
9324 KB |
Output is correct |
10 |
Correct |
302 ms |
9044 KB |
Output is correct |
11 |
Correct |
330 ms |
9044 KB |
Output is correct |
12 |
Execution timed out |
1046 ms |
15956 KB |
Time limit exceeded |
13 |
Halted |
0 ms |
0 KB |
- |