This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2005;
int n , p , q , ans;
int a[N] , cnt[N] , Max2w[N] ,Maxw[N];
int f[N][N];
bool check(int mid){
int cur1 = 1, cur2 = 1;
for(int i = 1 ; i <= n ; ++ i){
for(int j = i ; j <= n ; ++ j){
if(a[j] - a[i] + 1 <= mid) Maxw[i] = j;
if(a[j] - a[i] + 1 <= 2*mid) Max2w[i] = j;
}
/*for(;cur1 <= n && a[cur1] - a[i] + 1 <= mid ; ++ cur1);
Maxw[i] = cur1 - 1;
for(;cur2 <= n && a[cur2] - a[i] + 1 <= 2*mid ; ++ cur2);
Max2w[i] = cur2 - 1;*/
}
memset(f,-1,sizeof f);
f[1][0] = Maxw[1];
f[0][1] = Max2w[1];
if(Maxw[1] == n || Max2w[1] == n) return true;
for(int i = 0 ; i <= p ; ++ i)
for(int j = 0 ; j <= q ; ++ j)
if(f[i][j] != -1){
if(f[i][j] == n) return true;
f[i][j + 1] = max(f[i][j + 1] , Max2w[f[i][j] + 1]);
f[i + 1][j] = max(f[i + 1][j] , Maxw[f[i][j] + 1]);
}
return false;
}
signed main(){
//freopen("1.inp","r",stdin);
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> p >> q;
a[n+1] = 1e9;
for(int i = 1 ;i <= n ; ++ i )
cin >> a[i];
sort(a + 1 , a + n + 1);
if( p+q >= n ){
cout << 1;
return 0;
}
int l = 1 , r = a[n] - a[1] + 1;
while(l <= r){
int mid = ( l + r ) / 2;
bool kt = check(mid);
if(kt){
ans = mid;
r = mid - 1;
}
else l = mid + 1;
}
cout << ans;
}
Compilation message (stderr)
watching.cpp: In function 'bool check(long long int)':
watching.cpp:13:6: warning: unused variable 'cur1' [-Wunused-variable]
int cur1 = 1, cur2 = 1;
^~~~
watching.cpp:13:16: warning: unused variable 'cur2' [-Wunused-variable]
int cur1 = 1, cur2 = 1;
^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |