#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
ll const inf = 1e9;
ll const mod = 1e9 + 7;
ld const eps = 1e-13;
ll n, p, q;
ll a[2000];
bool ok(ll w){
ll dp[n + 1][q + 1];
dp[0][0] = 0;
fr(i, 1, q + 1) dp[0][i] = inf;
fr(i, 1, n + 1){
ll jlong;
ll jshort;
for(int j = i; j >= 1; j --){
if(a[i - 1] - a[j - 1] + 1 <= w) jshort = j;
if(a[i - 1] - a[j - 1] + 1 <= 2 * w) jlong = j;
}
fr(Q, 0, q + 1){
dp[i][Q] = inf;
if(Q > 0){
int bef = 0;
if(jlong > 0) bef = dp[jlong - 1][Q - 1];
dp[i][Q] = bef;
}
ll bef = 0;
if(jshort > 0) bef = dp[jshort - 1][Q];
dp[i][Q] = min(dp[i][Q], bef + 1);
}
}
ll BEST = inf;
fr(i, 0, q + 1){
BEST = min(BEST, dp[n][i]);
}
return BEST <= p;
}
void solve(){
cin >> n >> p >> q;
q = min(n, q);
sort(a, a + n);
fr(i, 0, n){
cin >> a[i];
}
ll ans = 0;
ll mx = 1e9;
for(ll b = mx / 2; b >= 1; b /= 2){
while(b + ans <= mx && !ok(b + ans)) ans += b;
}
cout << ans + 1 <<endl;
}
int main()
{
solve();
return 0;
}
Compilation message
watching.cpp: In function 'bool ok(ll)':
watching.cpp:25:20: warning: 'jlong' may be used uninitialized in this function [-Wmaybe-uninitialized]
ll jlong;
^~~~~
watching.cpp:26:20: warning: 'jshort' may be used uninitialized in this function [-Wmaybe-uninitialized]
ll jshort;
^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
75 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
