#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, p, q, a = 0 , b;
vector<int> A;
vector<vector<int>> dp(2010, vector<int> (2010, 0));
bool check(int w) {
a = 0;
dp[0][0] = 0;
int I = min(n, q);
int J = min(n, q);
for(int i = 0;i<=I;i++) {
for(int j = 0;j<=J;j++) {
if(i == 0 and j == 0) continue;
if(i > 0)
{
a=dp[i-1][j];
b = a;
while(a<n and A[b]+w-1>=A[a])
a++;
}
dp[i][j]=a;
if(j > 0)
{
a=dp[i][j-1];
b = a;
while(a<n and A[b]+2*w-1>=A[a])
a++;
}
dp[i][j]=max(a, dp[i][j]);
}
}
return (dp[I][J]>=n);
}
int32_t main () {
cin >> n >> p >> q;
for(int i = 0;i<n;i++) {
int ai;
cin >> ai;
A.push_back(ai);
}
sort(A.begin(), A.end());
int r = 1e9, l = 0, ans = 0;
while(l<=r) {
int mid = (l+r)/2;
if(check(mid)) {
r = mid - 1;
}
else {
l = mid + 1;
}
}
cout<<l<<endl;
return 0;
}
Compilation message
watching.cpp: In function 'int32_t main()':
watching.cpp:43:22: warning: unused variable 'ans' [-Wunused-variable]
43 | int r = 1e9, l = 0, ans = 0;
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
31964 KB |
Output is correct |
2 |
Correct |
15 ms |
31948 KB |
Output is correct |
3 |
Correct |
15 ms |
31960 KB |
Output is correct |
4 |
Incorrect |
15 ms |
31892 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
31948 KB |
Output is correct |
2 |
Correct |
19 ms |
31904 KB |
Output is correct |
3 |
Correct |
464 ms |
32032 KB |
Output is correct |
4 |
Incorrect |
22 ms |
32176 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |