#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back //emplace_back
#define pp pop_back
#define pii pair<ll, ll> //pair<int, int>
#define all(x) (x).begin(),(x).end()
#define mp(a,b) make_pair(a , b)
#define sz(x) (ll)(x).size()
#define F first
#define S second
#define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
#define debug(x) cout << #x << " : " << x << endl << flush
#define endl '\n'
#define arr(x) array<ll , (x)>
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define FAST ios_base::sync_with_stdio(0);cin.tie(0);
ll Sum(ll a , ll b , ll MOD)
{
a %= MOD;
b %= MOD;
a += b;
return a % MOD;
}
ll Mul(ll a , ll b , ll MOD)
{
a %= MOD;
b %= MOD;
a *= b;
return a % MOD;
}
ll Pow(ll a , ll b , ll MOD)
{
ll res = 1;
while(b)
{
if((b & 1))res = Mul(res , a , MOD);
a = Mul(a , a , MOD);
b >>= 1;
}
return res;
}
ll Min(ll a , ll b)
{
if(a > b)return b;
return a;
}
ll Max(ll a , ll b)
{
if(a > b)return a;
return b;
}
ll Ceil(ll a , ll b)
{
if(a % b)return (a/b)+1;
return a/b;
}
/////////////////////
//VALS
ll n, p, q;
const ll maxn = 2e3+10;
const ll INF = 1e18;
ll a[maxn];
/////////////////////
//FUNCTIONS
bool chk(ll x)
{
// debug(x);
ll dp[n+1][p+1];//dp[i][j] -> until pref i, if we have j small , what is the minimum number of large we need
ll lstsmall[n], lstbig[n];
For(i, n)
lstsmall[i] = lower_bound(a, a+n, a[i] - x + 1) - a;
For(i, n)
lstbig[i] = lower_bound(a, a+n, a[i] - x - x + 1) - a;
// if(x == 5)
// For(i, n)
// {
// debug(i);
// debug(lstsmall[i]);
// debug(lstbig[i]);
// }
// debug("_____________________");
For(i, p+1)dp[0][i] = 0;
for (int i = 1; i <= n; i++)
{
For(j, p+1)
{
dp[i][j] = 1e18;
dp[i][j] = min(dp[i][j], dp[lstbig[i-1] - 1][j] + 1);
if (j >= 1)
{
dp[i][j] = min(dp[i][j], dp[i][j - 1]);
dp[i][j] = min(dp[i][j], dp[lstsmall[i-1] - 1][j - 1]);
}
}
}
For(i, p+1)
{
// debug(i);
// debug(dp[n][i]);
if(dp[n][i] <= q)return 1;
}
return 0;
}
/////////////////////
//SOLVE
void solve()
{
cin >> n >> p >> q;
For(i, n)cin >> a[i];
For(i, n)a[i]--;
if(p + q >= n)
{
cout << 1 << endl;
return;
}
ll l = 0, r = 1e9;
while(r - l > 1)
{
// debug(":L");
ll mid = (r + l) >> 1;
if(chk(mid))r = mid;
else l = mid;
}
cout << r << endl;
}
/////////////////////
//MAIN
int main()
{
FAST;
ll t = 1;
// cin >> t;
while(t--)
{
solve();
}
}
/////////////////////
/*
ZZZZZZZ A M M IIIIIII N N
Z A A M M M M I NN N
Z A A M M M M I N N N
Z AAAAAAA M M M I N N N
Z A A M M I N N N
Z A A M M I N NN
ZZZZZZZ A A M M IIIIIII N N TREE
*/
Compilation message
watching.cpp: In function 'bool chk(long long int)':
watching.cpp:17:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
17 | #define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
| ^
watching.cpp:85:2: note: in expansion of macro 'For'
85 | For(i, n)
| ^~~
watching.cpp:17:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
17 | #define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
| ^
watching.cpp:87:2: note: in expansion of macro 'For'
87 | For(i, n)
| ^~~
watching.cpp:17:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
17 | #define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
| ^
watching.cpp:98:2: note: in expansion of macro 'For'
98 | For(i, p+1)dp[0][i] = 0;
| ^~~
watching.cpp:17:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
17 | #define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
| ^
watching.cpp:102:9: note: in expansion of macro 'For'
102 | For(j, p+1)
| ^~~
watching.cpp:17:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
17 | #define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
| ^
watching.cpp:115:2: note: in expansion of macro 'For'
115 | For(i, p+1)
| ^~~
watching.cpp: In function 'void solve()':
watching.cpp:17:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
17 | #define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
| ^
watching.cpp:129:2: note: in expansion of macro 'For'
129 | For(i, n)cin >> a[i];
| ^~~
watching.cpp:17:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
17 | #define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
| ^
watching.cpp:130:2: note: in expansion of macro 'For'
130 | For(i, n)a[i]--;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
