#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define pb push_back
#define int long long int
#define endl '\n'
#define MOD (int)(1e9 + 7)
#define eray chrono::steady_clock().now().time_since_epoch().count()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define mid start+(end-start)/2
#define debug(x) cerr << #x << " = " << x << endl
#define binary(x) cerr << #x << " = " << bitset<8>(x) << endl
#define N (int)(2e3)+5
int n, p, q, a;
vector<int> v;
int dp[N][N];
int precalc[N][2];
int rec(int wai, int lit){
if(lit > p) return INT_MAX;
if(wai >= n) return 0;
if(~dp[wai][lit]) return dp[wai][lit];
dp[wai][lit] = min(rec(precalc[wai][0]+1, lit+1), rec(precalc[wai][1]+1, lit)+1);
return dp[wai][lit];
}
bool cont(int wai){
memset(dp, -1, sizeof dp);
for(int i = 0; i < n; i++){
auto ka = lower_bound(all(v), v[i]+wai);
auto sa = lower_bound(all(v), v[i]+wai*2);
if(ka == v.end()) precalc[i][0] = n-1;
else ka--, precalc[i][0] = ka-v.begin();
if(sa == v.end()) precalc[i][1] = n-1;
else sa--, precalc[i][1] = sa-v.begin();
}
if(rec(0, 0) > q) return false;
return true;
}
int32_t main(){
ios_base::sync_with_stdio(false);cin.tie(0); cout.tie(0);
cin >> n >> p >> q;
for(int i = 0; i < n; i++){
cin >> a;
v.pb(a);
}
int start = 1, end = MOD, ans = INT_MAX;
while(start <= end){
if(cont(mid)) {ans = min(ans, mid); end = mid-1;}
else start = mid+1;
}
cout << ans << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
131 ms |
31852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
138 ms |
31852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
