#include <bits/stdc++.h>
#define ii pair <int, int>
#define x first
#define y second
#define db(x) cerr << #x << " = " << x << endl;
using namespace std;
inline void read(int &x){register int c = getchar();x = 0; int neg = 0;for (;((c<48 || c>57) && c != '-') ;c = getchar());if(c=='-') {neg=1;c=getchar();}for(;c>47 && c<58;c = getchar()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
inline void read(long long &x){register int c = getchar();x = 0; int neg = 0;for (;((c<48 || c>57) && c != '-') ;c = getchar());if(c=='-') {neg=1;c=getchar();}for(;c>47 && c<58;c = getchar()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
inline void writeln(long long x){char buffor[21];register int i=0;int neg=0; if (x<0) {neg=1; x= -x;}do{buffor[i++]=(x%10)+'0';x/=10;} while(x);i--;if (neg) putchar('-');while(i>=0) putchar(buffor[i--]);putchar('\n');}
inline void write(long long x){char buffor[21];register int i=0;int neg=0; if (x<0) {neg=1; x= -x;}do{buffor[i++]=(x%10)+'0';x/=10;} while(x);i--;if (neg) putchar('-');while(i>=0) putchar(buffor[i--]);putchar(' ');}
const int N = 2007;
int n, p, q;
int a[N];
int f[N][N];
ii nxt[N];
inline int BS(int i, long long d){
int l = i;
int r = n;
while (l <= r){
int mid = (l + r) / 2;
if (a[mid] - a[i] + 1 <= d)
l = mid + 1;
else
r = mid - 1;
}
return r;
}
bool check(int x){
for (int i = 1; i <= n; i++){
nxt[i].x = BS(i, x);
nxt[i].y = BS(i, 2 * x);
}
for (int i = 0; i <= p; i++)
for (int j = 0; j <= q; j++){
f[i][j] = 0;
if (j) f[i][j] = max(f[i][j], nxt[f[i][j - 1] + 1].y);
if (i) f[i][j] = max(f[i][j], nxt[f[i - 1][j] + 1].x);
if (f[i][j] >= n) return true;
}
return false;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
read(n); read(p); read(q);
p = min(p, n); q = min(q, n);
for (int i = 1; i <= n; i++)
read(a[i]);
sort(a + 1, a + n + 1);
int l = 1;
int r = 1000000000;
while (l <= r){
int mid = (l + r) / 2;
if (check(mid))
r = mid - 1;
else
l = mid + 1;
}
writeln(l);
}
Compilation message
watching.cpp: In function 'void read(int&)':
watching.cpp:9:39: warning: ISO C++1z does not allow 'register' storage class specifier [-Wregister]
inline void read(int &x){register int c = getchar();x = 0; int neg = 0;for (;((c<48 || c>57) && c != '-') ;c = getchar());if(c=='-') {neg=1;c=getchar();}for(;c>47 && c<58;c = getchar()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
^
watching.cpp: In function 'void read(long long int&)':
watching.cpp:10:45: warning: ISO C++1z does not allow 'register' storage class specifier [-Wregister]
inline void read(long long &x){register int c = getchar();x = 0; int neg = 0;for (;((c<48 || c>57) && c != '-') ;c = getchar());if(c=='-') {neg=1;c=getchar();}for(;c>47 && c<58;c = getchar()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
^
watching.cpp: In function 'void writeln(long long int)':
watching.cpp:11:63: warning: ISO C++1z does not allow 'register' storage class specifier [-Wregister]
inline void writeln(long long x){char buffor[21];register int i=0;int neg=0; if (x<0) {neg=1; x= -x;}do{buffor[i++]=(x%10)+'0';x/=10;} while(x);i--;if (neg) putchar('-');while(i>=0) putchar(buffor[i--]);putchar('\n');}
^
watching.cpp: In function 'void write(long long int)':
watching.cpp:12:61: warning: ISO C++1z does not allow 'register' storage class specifier [-Wregister]
inline void write(long long x){char buffor[21];register int i=0;int neg=0; if (x<0) {neg=1; x= -x;}do{buffor[i++]=(x%10)+'0';x/=10;} while(x);i--;if (neg) putchar('-');while(i>=0) putchar(buffor[i--]);putchar(' ');}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
760 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
248 KB |
Output is correct |
| 10 |
Correct |
2 ms |
380 KB |
Output is correct |
| 11 |
Correct |
2 ms |
632 KB |
Output is correct |
| 12 |
Correct |
3 ms |
632 KB |
Output is correct |
| 13 |
Correct |
2 ms |
376 KB |
Output is correct |
| 14 |
Correct |
2 ms |
376 KB |
Output is correct |
| 15 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
41 ms |
4088 KB |
Output is correct |
| 4 |
Correct |
26 ms |
8516 KB |
Output is correct |
| 5 |
Correct |
7 ms |
376 KB |
Output is correct |
| 6 |
Correct |
7 ms |
376 KB |
Output is correct |
| 7 |
Correct |
10 ms |
504 KB |
Output is correct |
| 8 |
Correct |
18 ms |
1272 KB |
Output is correct |
| 9 |
Correct |
22 ms |
3832 KB |
Output is correct |
| 10 |
Correct |
30 ms |
8700 KB |
Output is correct |
| 11 |
Correct |
14 ms |
1144 KB |
Output is correct |
| 12 |
Correct |
85 ms |
8092 KB |
Output is correct |
| 13 |
Correct |
6 ms |
504 KB |
Output is correct |
| 14 |
Correct |
6 ms |
376 KB |
Output is correct |
| 15 |
Correct |
6 ms |
504 KB |
Output is correct |
