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;
const int N = 2005;
int v[N];
int dp[N][N];
int n, p, q;
bool check(int w){
int lst, lst2;
for(int i =0 ; i<N; i++){
for(int j = 0; j < N; j++){
dp[i][j] = INT_MAX;
dp[0][j] = 0;
}
}
lst = lst2 = 0;
for(int i =1 ; i<=n; i++){
while(lst < i && v[i] - v[lst + 1] + 1 > w)
lst++;
while(lst2 < i && v[i] - v[lst2 + 1] + 1 > 2*w)
lst2++;
for(int j = 0; j <= i; j++ ){
if(dp[lst][j] != INT_MAX)
dp[i][j] = min(dp[i][j], dp[lst][j] + 1);
if(j)
dp[i][j] = min(dp[i][j], dp[lst2][j-1]);
}
}
for(int i = 0; i <=q; i++){
if(dp[n][i] <=p)
return true;
}
return false;
}
int main()
{
//freopen(".in","r",stdin);
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>p>>q;
for(int i =1 ; i<=n; i++){
cin>>v[i];
}
sort(v+1, v+n+1);
if(p + q >= n){
cout<<"1";
return 0;
}
int pas = 0;
for(int p2 = 1<<29; p2>0; p2>>=1){
if(check(pas + p2) == false)
pas+=p2;
}
cout<<pas + 1;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |