//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define ll long long
#define fi first
#define se second
#define pb emplace_back
#define pii pair<int, int>
#define ms(s, n) memset(s, n, sizeof(s))
#define all(a) a.begin(), a.end()
#define uni(a) (sort(all(a)), a.resize(unique(all(a))-a.begin()))
#define sz(s) (int)((s).size())
#define MASK(i) (1LL << (i))
#define BIT(x, i) ((x >> (i)) & 1)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define F0R(i, b) for (int i = 0, _b = (b); i < _b; ++i)
#define FORd(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define F0Rd(i, b) for (int i = (b)-1; i >= 0; i--)
using namespace std;
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
template<typename T1,typename T2> bool ckmax(T1 &x,const T2 &y){if(x<y){x=y; return 1;} return 0;}
template<typename T1,typename T2> bool ckmin(T1 &x,const T2 &y){if(y<x){x=y; return 1;} return 0;}
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r){return l + rd()% (r-l+1);}
const int MOD = 1000000007;
const int mod = 998244353;
const int oo = 1061109567;
const long long INF = 4557430888798830399;
const double PI = acos(-1);
const int N = 2e3 + 1;
/*
/\_/\
(= ._.)
/ >? \>$
*/
int n, p, q;
int a[N];
namespace sub1{
const int M = 1e2 + 1;
bool dp[M][M][M];
bool check(int w){
memset(dp, 0, sizeof(dp));
dp[0][0][0] = 1;
FOR(i, 1, n) FOR(j, 0, p) FOR(k, 0, q){
int i1 = lower_bound(a+1,a+i,a[i]-w+1) - a;
int i2 = lower_bound(a+1,a+i,a[i]-w-w+1) - a;
if(j > 0) dp[i][j][k] |= dp[i1-1][j-1][k];
if(k > 0) dp[i][j][k] |= dp[i2-1][j][k-1];
}
FOR(i, 0, p) FOR(j, 0, q) if(dp[n][i][j]) return 1;
return 0;
}
}
namespace sub2{
int dp[N][N];
bool check(int w){
memset(dp, 0x3f, sizeof(dp));
dp[0][0] = 0;
FOR(i, 1, n) FOR(j, 0, p){
int i1 = lower_bound(a+1,a+i,a[i]-w+1) - a;
int i2 = lower_bound(a+1,a+i,a[i]-w-w+1) - a;
if(j > 0) dp[i][j] = min(dp[i][j], dp[i1-1][j-1]);
dp[i][j] = min(dp[i][j], dp[i2-1][j] + 1);
}
FOR(i, 0, p) if(dp[n][i] <= q) return 1;
return 0;
}
}
bool check(int w){
if(n <= 1e2) return sub1::check(w);
if(n <= 2e3) return sub2::check(w);
}
void sol(){
cin >> n >> p >> q;
FOR(i, 1, n) cin >> a[i];
sort(a+1,a+n+1);
if(p + q > n) return void(cout << 1 << '\n');
int l = 1, r = a[n]-a[1]+1, ans = -1;
while(l <= r){
int m = (l + r) >> 1;
if(check(m)) r = m-1, ans = m;
else l = m+1;
}
cout << ans << '\n';
}
signed main(){
#define TASK "EVENTS"
//if(fopen(TASK".inp", "r")){
// freopen(TASK".inp", "r", stdin);
// freopen(TASK".out", "w", stdout);
// }
fast; int t = 1;
// cin >> t;
while(t--) sol();
cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << " ms\n";
}
Compilation message
watching.cpp: In function 'bool check(int)':
watching.cpp:89:1: warning: control reaches end of non-void function [-Wreturn-type]
89 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
3 ms |
2396 KB |
Output is correct |
| 8 |
Correct |
6 ms |
2396 KB |
Output is correct |
| 9 |
Correct |
6 ms |
2396 KB |
Output is correct |
| 10 |
Correct |
44 ms |
2516 KB |
Output is correct |
| 11 |
Correct |
46 ms |
2396 KB |
Output is correct |
| 12 |
Correct |
104 ms |
2396 KB |
Output is correct |
| 13 |
Correct |
3 ms |
2396 KB |
Output is correct |
| 14 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 15 |
Correct |
4 ms |
2396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
17076 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
53 ms |
16988 KB |
Output is correct |
| 8 |
Correct |
202 ms |
17068 KB |
Output is correct |
| 9 |
Execution timed out |
1052 ms |
17060 KB |
Time limit exceeded |
| 10 |
Halted |
0 ms |
0 KB |
- |
