#pragma GCC optimize("O3", "inline")
#include <bits/stdc++.h>
using namespace std;
#define ins insert
#define pb push_back
#define int long long int
#define pii pair<int, int>
#define endl '\n'
#define drop(x) cout<<(x)<<endl; return;
#define all(x) x.begin(),x.end()
const int prime = 23,inf = 2e18,mod = 1e9 +7,sze =1e6;
struct node{
int qalanbalaca;
int qalanboyuk;
int maxgedir;
};
void mal(){
int n,p,q;
cin>>n>>p>>q;
vector<int> arr(n);
for(int i=0;i<n;i++){
cin>>arr[i];
}
sort(all(arr));
int l = 1;
int r = 1e18;
int ans=r;
while(l<=r){
int mid = (l+r)/2;
int w = mid-1;
int bigw = mid*2 -1;
bool check=false;
// int w = 4;
// int bigw = 8;
// /*
// burdan sonrasi dp olaraq yazim?
// i ci yere boyuk qoysam,
// */
vector<vector<node>> dp(n,vector<node>(3,{-1,-1,-1}));
// int w =4 ;
int mxg = (--upper_bound(all(arr),arr[0] + w)) - arr.begin();
int mxg2 = (--upper_bound(all(arr),arr[0] + bigw)) - arr.begin();
// cout<<mxg<<endl;
dp[0][1] = {p-1,q,mxg}; // 0 use small camera, 1 use big
dp[0][2] = {p,q-1,mxg2}; // 0 use small camera, 1 use big
if(mxg>=n-1 || mxg2>=n-1){
check=true;
}
else{
for(int i =1;i<n;i++){
// i ciye 0 qoysaq, yada 1 qoysaq ? qoya bilriik hec?
node gelen_enazp = {-1,-1,-1};
node gelen_enazq = {-1,-1,-1};
int mxa =-1;
int mxb =-1;
for(int j=0;j<i;j++){
if(dp[j][1].maxgedir>=i-1){
int qalan =dp[j][1].qalanbalaca*(w+1) + dp[j][1].qalanboyuk*(bigw+1);
if(qalan >= gelen_enazp.qalanbalaca*(w+1) + gelen_enazp.qalanboyuk*(bigw+1)){
if(dp[j][1].qalanbalaca){
gelen_enazp = dp[j][1];
mxa = (--upper_bound(all(arr),arr[i] + w) - arr.begin());
}
}
}
else{
int x = (dp[j][1].qalanbalaca ? (--upper_bound(all(arr),arr[dp[j][1].maxgedir+1] + w) - arr.begin()) : -1);
if(x>=i){
int qalan =dp[j][1].qalanbalaca*(w+1) + dp[j][1].qalanboyuk*(bigw+1);
if(qalan >= gelen_enazp.qalanbalaca*(w+1) + gelen_enazp.qalanboyuk*(bigw+1)){
if(dp[j][1].qalanbalaca){
gelen_enazp = dp[j][1];
mxa = x;
}
}
}
}
if(dp[j][2].maxgedir>=i-1){
int qalan = dp[j][2].qalanbalaca*(w+1) + dp[j][2].qalanboyuk*(bigw+1);
if(qalan >= gelen_enazp.qalanbalaca*(w+1) + gelen_enazp.qalanboyuk*(bigw+1)){
if(dp[j][2].qalanbalaca){
gelen_enazp = dp[j][2];
mxa = (--upper_bound(all(arr),arr[i] + w) - arr.begin());
}
}
}
else{
int x = (dp[j][2].qalanbalaca ? (--upper_bound(all(arr),arr[dp[j][2].maxgedir+1] + w) - arr.begin()) : -1);
if(x>=i){
int qalan =dp[j][2].qalanbalaca*(w+1) + dp[j][2].qalanboyuk*(bigw+1);
if(qalan >= gelen_enazp.qalanbalaca*(w+1) + gelen_enazp.qalanboyuk*(bigw+1)){
if(dp[j][2].qalanbalaca){
gelen_enazp = dp[j][2];
mxa = x;
}
}
}
}
if(dp[j][1].maxgedir>=i-1){
int qalan =dp[j][1].qalanbalaca*(w+1) + dp[j][1].qalanboyuk*(bigw+1);
if(qalan >= gelen_enazq.qalanbalaca*(w+1) + gelen_enazq.qalanboyuk*(bigw+1)){
if(dp[j][1].qalanboyuk){
gelen_enazq = dp[j][1];
mxb = (--upper_bound(all(arr),arr[i] + bigw) - arr.begin());
}
}
}
else{
int x = (dp[j][1].qalanboyuk ? (--upper_bound(all(arr),arr[dp[j][1].maxgedir+1] + bigw) - arr.begin()) : -1);
if(x>=i){
int qalan =dp[j][1].qalanbalaca*(w+1) + dp[j][1].qalanboyuk*(bigw+1);
if(qalan >= gelen_enazq.qalanbalaca*(w+1) + gelen_enazq.qalanboyuk*(bigw+1)){
if(dp[j][1].qalanboyuk){
gelen_enazq = dp[j][1];
mxb = x;
}
}
}
}
if(dp[j][2].maxgedir>=i-1){
int qalan = dp[j][2].qalanbalaca*(w+1) + dp[j][2].qalanboyuk*(bigw+1);
if(qalan >= gelen_enazq.qalanbalaca*(w+1) + gelen_enazq.qalanboyuk*(bigw+1)){
if(dp[j][2].qalanboyuk){
gelen_enazq = dp[j][2];
mxb = (--upper_bound(all(arr),arr[i] + bigw) - arr.begin());
}
}
}
else{
int x = (dp[j][2].qalanboyuk ? (--upper_bound(all(arr),arr[dp[j][2].maxgedir+1] + bigw) - arr.begin()) : -1);
if(x>=i){
int qalan = dp[j][2].qalanbalaca*(w+1) + dp[j][2].qalanboyuk*(bigw+1);
if(qalan >= gelen_enazq.qalanbalaca*(w+1) + gelen_enazq.qalanboyuk*(bigw+1)){
if(dp[j][2].qalanboyuk){
gelen_enazq = dp[j][2];
mxb=x;
}
}
}
}
}
/*
optimallari goturduk, istifade vaxti
*/
if(gelen_enazp.qalanbalaca>0){
int mxgedir = mxa;
gelen_enazp.qalanbalaca -= 1;
gelen_enazp.maxgedir = mxgedir;
}
if(gelen_enazq.qalanboyuk>0){
int mxgedir = mxb;
gelen_enazq.qalanboyuk -= 1;
gelen_enazq.maxgedir = mxgedir;
}
dp[i][1] = gelen_enazp;
dp[i][2] = gelen_enazq;
if(dp[i][1].maxgedir>=n-1 || dp[i][2].maxgedir>=n-1){
// cout<<mid<<":ans "<<i<<"ciyer "<<dp[i][1].maxgedir<<" : "<<dp[i][2].maxgedir<<endl;
check=true;
break;
}
}
// cout<<dp[1][1].maxgedir<<" "<<dp[1][2].maxgedir<<endl;
}
if(check){
// cout<<mid<<" "<<w<<" "<<bigw<<endl;
r=mid-1;
ans=mid;
}
else{
l=mid+1;
}
}
drop(ans);
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
int tt = 1;
// cin>>tt;
while(tt--){
mal();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
4 ms |
348 KB |
Output is correct |
| 5 |
Correct |
3 ms |
348 KB |
Output is correct |
| 6 |
Correct |
4 ms |
348 KB |
Output is correct |
| 7 |
Correct |
3 ms |
344 KB |
Output is correct |
| 8 |
Incorrect |
3 ms |
456 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
154 ms |
672 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Execution timed out |
1094 ms |
604 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
