// #pragma GCC diagnostic warnign "-std=c++11"
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize ("O3")
// #pragma GCC optimization ("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define eb emplace_back
#define mp make_pair
#define pb push_back
#define pp pop_back
#define endl '\n'
#define ff first
#define ss second
#define stop exit(0)
#define sz(x) (int)x.size()
#define pause system("pause")
#define all(x) (x).begin(),(x).end()
#define deb(x) cout << #x << "-" << x << endl
typedef char chr;
typedef string str;
typedef long long ll;
typedef vector <int> vii;
typedef pair <int,int> pii;
const long long INF = LLONG_MAX;
const int inf = INT_MAX;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const int dx[] = {0,0,-1,1};
const int dy[] = {-1,1,0,0};
const double PI = 2 * acos(0.0);
const int N = 2e3 + 5;
int n,p,q,arr[N],ans;
int dp[N][N];
bool check(int w) {
vector <int> s;
s.push_back(-INF);
for (int i = 1; i <= n; i++) {
s.pb(arr[i]);
for (int j = 0; j <= q; j++) {
int l1 = (lower_bound(all(s),arr[i]-w+1))-s.begin();
dp[i][j] = dp[l1-1][j]+1;
int l2 = (lower_bound(all(s),arr[i]-2*w+1)-s.begin());
if (j) dp[i][j] = min(dp[i][j],dp[l2-1][j-1]);
}
}
for (int i = 1; i <= q; i++) {
if (dp[n][i] <= p) return true;
}
return false;
}
inline void test_case () {
cin >> n >> p >> q;
for (int i = 1; i <= n; i++) {
cin >> arr[i];
}
if (p+q > n) {
cout << 1 << endl;
return;
}
int l = 0; int r = 1e9;
while (l <= r) {
int mid = (l+r)/2;
dp[0][0] = 0;
if (check(mid)) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
cout << ans << endl;
}
signed main () {
ios_base :: sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int T = 1;
// cin >> T;
while(T--) {
test_case();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
31324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
