#include <bits/stdc++.h>
#define INF 1000000007
#define pb push_back
#define bw(i,r,l) for (int i=r-1;i>=l;i--)
#define fw(i,l,r) for (int i=l;i<r;i++)
using namespace std;
int n,p,q,a[2001],poss[2001],posl[2001],dp[2001][2001];
bool check(int w) {
fw (i,0,n) {
poss[i]=upper_bound(a,a+n,a[i]+w-1)-a;
posl[i]=upper_bound(a,a+n,a[i]+2*w-1)-a;
}
memset(dp,-1,sizeof(dp));
dp[0][0]=0; //DP[i][j] stores not the maximal place you can reach, but minimal you can't reach
fw (i,0,p+1) fw (j,0,q+1) if (dp[i][j]!=-1) {
if (dp[i][j]==n) return true;
dp[i+1][j]=max(dp[i+1][j],poss[dp[i][j]]);
dp[i][j+1]=max(dp[i][j+1],posl[dp[i][j]]);
}
return false;
}
int ans(int l,int r) {
int mid=(l+r)/2;
if (l==r) return l;
bool temp=check(mid);
if (temp) return ans(l,mid);
else return ans(mid+1,r);
}
signed main() {
//freopen("aome.inp","r",stdin);
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin>>n>>p>>q;
fw (i,0,n) cin>>a[i];
if (p+q>=n) {cout<<"1"; return 0;}
sort(a,a+n);
/*
DP[i][j]: Furthest position you can reach with i small cameras and j big ones.
Binary search for the answer, then create a board for the furthest position of each one.
Total complexity: O(PQ * log2(1e9))
*/
cout<<ans(1,1000000000);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
15992 KB |
Output is correct |
| 2 |
Correct |
3 ms |
15992 KB |
Output is correct |
| 3 |
Correct |
95 ms |
16088 KB |
Output is correct |
| 4 |
Correct |
2 ms |
16088 KB |
Output is correct |
| 5 |
Correct |
3 ms |
16088 KB |
Output is correct |
| 6 |
Correct |
2 ms |
16088 KB |
Output is correct |
| 7 |
Correct |
41 ms |
16176 KB |
Output is correct |
| 8 |
Correct |
54 ms |
16304 KB |
Output is correct |
| 9 |
Correct |
40 ms |
16304 KB |
Output is correct |
| 10 |
Correct |
40 ms |
16304 KB |
Output is correct |
| 11 |
Correct |
41 ms |
16332 KB |
Output is correct |
| 12 |
Correct |
41 ms |
16332 KB |
Output is correct |
| 13 |
Correct |
41 ms |
16332 KB |
Output is correct |
| 14 |
Correct |
40 ms |
16332 KB |
Output is correct |
| 15 |
Correct |
40 ms |
16332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
43 ms |
16332 KB |
Output is correct |
| 2 |
Correct |
2 ms |
16332 KB |
Output is correct |
| 3 |
Correct |
3 ms |
16332 KB |
Output is correct |
| 4 |
Correct |
2 ms |
16332 KB |
Output is correct |
| 5 |
Correct |
3 ms |
16332 KB |
Output is correct |
| 6 |
Correct |
3 ms |
16332 KB |
Output is correct |
| 7 |
Correct |
44 ms |
16356 KB |
Output is correct |
| 8 |
Correct |
60 ms |
16356 KB |
Output is correct |
| 9 |
Correct |
56 ms |
16356 KB |
Output is correct |
| 10 |
Correct |
94 ms |
16380 KB |
Output is correct |
| 11 |
Correct |
69 ms |
16380 KB |
Output is correct |
| 12 |
Correct |
154 ms |
16380 KB |
Output is correct |
| 13 |
Correct |
48 ms |
16380 KB |
Output is correct |
| 14 |
Correct |
80 ms |
16380 KB |
Output is correct |
| 15 |
Correct |
52 ms |
16380 KB |
Output is correct |
