#include <bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC target ("avx2")
#define ll long long
#define ff first
#define ss second
#define int ll
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define pb push_back
#define pii pair <int, int>
#define pdd pair <double, double>
#define vi vector <int>
using namespace std;
using namespace __gnu_pbds;
template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
const int inf = 1e15;
const int mod = 1e9+7;
const int N = 2e5+100;
int n, a, b;
vector <int> v;
bool check(int k){
vector <int> dp(n+100);
dp[0] = 1;
for (int i = 0, j = 1; i < n; ++i){
if (i > 1) dp[i] += dp[i-1];
if (dp[i] <= 0) continue;
j = max(j, i + 1);
while (j < n && v[j] - v[i] <= k) ++j;
if (i + a <= min(i + b, j)) {
dp[i+a]++;
dp[min(i + b, j) + 1]--;
}
}
dp[n] += dp[n-1];
return dp[n] > 0;
}
void solve(){
cin >> n >> a >> b; v.resize(n);
for (int i = 0; i < n; ++i) cin >> v[i];
sort(all(v));
int l = -1, r = 1e9;
for (; r - l > 1; ){
int m = (l + r) / 2;
if (check(m)) r = m;
else l = m;
}
cout << r;
}
signed main(){
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int tt = 1;
while (tt--){
solve();
cout << '\n';
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
208 KB |
Output is correct |
2 |
Correct |
19 ms |
2492 KB |
Output is correct |
3 |
Correct |
3 ms |
452 KB |
Output is correct |
4 |
Correct |
304 ms |
22704 KB |
Output is correct |
5 |
Correct |
280 ms |
22712 KB |
Output is correct |
6 |
Correct |
24 ms |
2504 KB |
Output is correct |
7 |
Correct |
245 ms |
20428 KB |
Output is correct |
8 |
Correct |
0 ms |
316 KB |
Output is correct |
9 |
Correct |
0 ms |
208 KB |
Output is correct |
10 |
Correct |
0 ms |
312 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
316 KB |
Output is correct |
2 |
Correct |
0 ms |
208 KB |
Output is correct |
3 |
Correct |
0 ms |
312 KB |
Output is correct |
4 |
Correct |
1 ms |
208 KB |
Output is correct |
5 |
Correct |
0 ms |
208 KB |
Output is correct |
6 |
Correct |
0 ms |
208 KB |
Output is correct |
7 |
Correct |
0 ms |
208 KB |
Output is correct |
8 |
Correct |
0 ms |
208 KB |
Output is correct |
9 |
Correct |
0 ms |
208 KB |
Output is correct |
10 |
Correct |
0 ms |
208 KB |
Output is correct |
11 |
Correct |
0 ms |
208 KB |
Output is correct |
12 |
Correct |
0 ms |
316 KB |
Output is correct |
13 |
Correct |
1 ms |
208 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
208 KB |
Output is correct |
2 |
Correct |
19 ms |
2492 KB |
Output is correct |
3 |
Correct |
3 ms |
452 KB |
Output is correct |
4 |
Correct |
304 ms |
22704 KB |
Output is correct |
5 |
Correct |
280 ms |
22712 KB |
Output is correct |
6 |
Correct |
24 ms |
2504 KB |
Output is correct |
7 |
Correct |
245 ms |
20428 KB |
Output is correct |
8 |
Correct |
0 ms |
316 KB |
Output is correct |
9 |
Correct |
0 ms |
208 KB |
Output is correct |
10 |
Correct |
0 ms |
312 KB |
Output is correct |
11 |
Correct |
1 ms |
208 KB |
Output is correct |
12 |
Correct |
0 ms |
208 KB |
Output is correct |
13 |
Correct |
0 ms |
208 KB |
Output is correct |
14 |
Correct |
0 ms |
208 KB |
Output is correct |
15 |
Correct |
0 ms |
208 KB |
Output is correct |
16 |
Correct |
0 ms |
208 KB |
Output is correct |
17 |
Correct |
0 ms |
208 KB |
Output is correct |
18 |
Correct |
0 ms |
208 KB |
Output is correct |
19 |
Correct |
0 ms |
316 KB |
Output is correct |
20 |
Correct |
1 ms |
208 KB |
Output is correct |
21 |
Correct |
8 ms |
868 KB |
Output is correct |
22 |
Correct |
9 ms |
1256 KB |
Output is correct |
23 |
Correct |
15 ms |
1608 KB |
Output is correct |
24 |
Correct |
36 ms |
2012 KB |
Output is correct |
25 |
Correct |
133 ms |
13228 KB |
Output is correct |
26 |
Correct |
327 ms |
18272 KB |
Output is correct |
27 |
Correct |
34 ms |
2004 KB |
Output is correct |
28 |
Correct |
15 ms |
1716 KB |
Output is correct |
29 |
Correct |
0 ms |
316 KB |
Output is correct |
30 |
Correct |
410 ms |
22712 KB |
Output is correct |
31 |
Correct |
405 ms |
22712 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
208 KB |
Output is correct |
2 |
Correct |
19 ms |
2492 KB |
Output is correct |
3 |
Correct |
3 ms |
452 KB |
Output is correct |
4 |
Correct |
304 ms |
22704 KB |
Output is correct |
5 |
Correct |
280 ms |
22712 KB |
Output is correct |
6 |
Correct |
24 ms |
2504 KB |
Output is correct |
7 |
Correct |
245 ms |
20428 KB |
Output is correct |
8 |
Correct |
0 ms |
316 KB |
Output is correct |
9 |
Correct |
0 ms |
208 KB |
Output is correct |
10 |
Correct |
0 ms |
312 KB |
Output is correct |
11 |
Correct |
8 ms |
868 KB |
Output is correct |
12 |
Correct |
9 ms |
1256 KB |
Output is correct |
13 |
Correct |
15 ms |
1608 KB |
Output is correct |
14 |
Correct |
36 ms |
2012 KB |
Output is correct |
15 |
Correct |
133 ms |
13228 KB |
Output is correct |
16 |
Correct |
327 ms |
18272 KB |
Output is correct |
17 |
Correct |
34 ms |
2004 KB |
Output is correct |
18 |
Correct |
15 ms |
1716 KB |
Output is correct |
19 |
Correct |
0 ms |
316 KB |
Output is correct |
20 |
Correct |
410 ms |
22712 KB |
Output is correct |
21 |
Correct |
405 ms |
22712 KB |
Output is correct |
22 |
Correct |
1 ms |
208 KB |
Output is correct |
23 |
Correct |
0 ms |
208 KB |
Output is correct |
24 |
Correct |
0 ms |
208 KB |
Output is correct |
25 |
Correct |
0 ms |
208 KB |
Output is correct |
26 |
Correct |
0 ms |
208 KB |
Output is correct |
27 |
Correct |
0 ms |
208 KB |
Output is correct |
28 |
Correct |
0 ms |
208 KB |
Output is correct |
29 |
Correct |
0 ms |
208 KB |
Output is correct |
30 |
Correct |
0 ms |
316 KB |
Output is correct |
31 |
Correct |
1 ms |
208 KB |
Output is correct |
32 |
Correct |
11 ms |
1488 KB |
Output is correct |
33 |
Correct |
143 ms |
12200 KB |
Output is correct |
34 |
Correct |
136 ms |
12484 KB |
Output is correct |
35 |
Correct |
415 ms |
22688 KB |
Output is correct |
36 |
Correct |
290 ms |
22708 KB |
Output is correct |
37 |
Correct |
294 ms |
22684 KB |
Output is correct |
38 |
Correct |
189 ms |
14920 KB |
Output is correct |