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 fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ll int
#define tc ll test;cin >> test;while(test--)
#define vi vector<ll>
#define pll pair<ll,ll>
#define pb push_back
#define mp make_pair
#define INF 1e18
#define MOD 1000000007
#define ff first
#define ss second
#define in >>
#define out <<
#define space << " " <<
#define spacef << " "
#define fo(i,a,b) for(ll i = a; i <= b; i++)
#define nextline out "\n"
#define print(x) for(auto i : x ) cout out i spacef
#define mmax(x,i) x = max(x,i)
#define mmin(x,i) x = min(x,i)
#define N 2005
ll n;
vi a(N);
bool check(ll w , ll p , ll q){
ll dp[n+5][p+5];
// dp[i][j] = minimum number of large cameras needed till i if we use j small cameras
// base case :
fo(i,0,p) dp[0][i] = 0;
fo(i,1,n){
auto it = lower_bound(a.begin()+1,a.begin()+n+1,a[i]-2*w+1);
ll pos = it-a.begin();
dp[i][0] = dp[pos-1][0]+1;
}
// recursive relation :
fo(i,1,n){
fo(j,1,p){
auto low1 = lower_bound(a.begin()+1,a.begin()+n+1,a[i]-w+1);
ll pos1 = low1-a.begin();
dp[i][j] = dp[pos1-1][j-1];
auto low2 = lower_bound(a.begin()+1,a.begin()+n+1,a[i]-2*w+1);
ll pos2 = low2-a.begin();
mmin(dp[i][j],dp[pos2-1][j]+1);
}
}
return dp[n][p] <= q;
}
int main() {
fast;
ll p,q;
cin in n in p in q;
if(p+q >= n){
cout out "1";
return 0;
}
fo(i,1,n) cin in a[i];
sort(a.begin()+1,a.begin()+n+1);
ll low = 1 , high = a[n];
ll ans;
while(low <= high){
ll mid = (low+high)/2;
if(check(mid,p,q)){
ans = mid;
high = mid-1;
}
else{
low = mid+1;
}
}
cout out ans;
return 0;
}
Compilation message (stderr)
watching.cpp: In function 'int main()':
watching.cpp:95:14: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
95 | cout out ans;
| ^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |