#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
using namespace std;
const ll N = 2e3 + 6;
const ll Log2 = 19;
const ll inf = 1e9 + 7;
typedef pair<ll,ll> LL;
vector<ll> v;
ll n,P,Q,a[N],dp[N][2*N],val,jump[N][2]; /// 0 if short jump 1 long jump
ll Find(ll x){
ll p = lower_bound(v.begin(),v.end(),x) - v.begin() + 1;
return p;
}
ll f(ll pos,ll p){
if (pos > n) return 0;
if (dp[pos][p] != -1) return dp[pos][p];
ll ans = inf;
if (p) ans = f(jump[pos][0],p - 1);
ans = min(ans,1 + f(jump[pos][1],p));
return dp[pos][p] = ans;
}
bool chk(ll m){
memset(dp,-1,sizeof(dp)); val = m;
for (ll i = 1;i <= n;i++){
jump[i][0] = Find(a[i] + m); jump[i][1] = Find(a[i] + 2*m);
}
return f(1,P) <= Q;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
#define task "tst"
if (fopen(task".in", "r")){
freopen(task".in", "r", stdin);
//freopen(task".out", "w", stdout);
}
cin>>n>>P>>Q;
for (ll i = 1;i <= n;i++) cin>>a[i]; sort(a + 1,a + n + 1);
for (ll i = 1;i <= n;i++) v.push_back(a[i]); v.push_back(inf);
if (P + Q >= n) return cout<<1,0;
ll l,m,h; l = 0; h = inf;
while(l <= h){
m = (l + h)/2;
if (chk(m)) h = m - 1;
else l = m + 1;
}
cout<<l;
}
Compilation message
watching.cpp: In function 'int main()':
watching.cpp:45:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
45 | for (ll i = 1;i <= n;i++) cin>>a[i]; sort(a + 1,a + n + 1);
| ^~~
watching.cpp:45:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
45 | for (ll i = 1;i <= n;i++) cin>>a[i]; sort(a + 1,a + n + 1);
| ^~~~
watching.cpp:46:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
46 | for (ll i = 1;i <= n;i++) v.push_back(a[i]); v.push_back(inf);
| ^~~
watching.cpp:46:50: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
46 | for (ll i = 1;i <= n;i++) v.push_back(a[i]); v.push_back(inf);
| ^
watching.cpp:41:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
41 | freopen(task".in", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
270 ms |
63340 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
269 ms |
63340 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
271 ms |
63340 KB |
Output is correct |
8 |
Correct |
273 ms |
63468 KB |
Output is correct |
9 |
Correct |
272 ms |
63340 KB |
Output is correct |
10 |
Correct |
273 ms |
63340 KB |
Output is correct |
11 |
Correct |
264 ms |
63468 KB |
Output is correct |
12 |
Correct |
273 ms |
63400 KB |
Output is correct |
13 |
Correct |
277 ms |
63468 KB |
Output is correct |
14 |
Correct |
273 ms |
63340 KB |
Output is correct |
15 |
Correct |
270 ms |
63340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
275 ms |
63472 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
492 KB |
Output is correct |
4 |
Correct |
2 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
280 ms |
63468 KB |
Output is correct |
8 |
Correct |
321 ms |
63468 KB |
Output is correct |
9 |
Correct |
439 ms |
63596 KB |
Output is correct |
10 |
Runtime error |
840 ms |
262148 KB |
Execution killed with signal 9 |
11 |
Halted |
0 ms |
0 KB |
- |