Submission #51446

#TimeUsernameProblemLanguageResultExecution timeMemory
51446mergesortWatching (JOI13_watching)C++14
0 / 100
3 ms664 KiB
#include<bits/stdc++.h> using namespace std; int a[2500],n,p,q; bool check(int w) { int use_1=p,use_2=q,cur_pos=1; int len1=w-1,len2=2*w-1; while(cur_pos<=n){ int j=0,x=0,y=0,k=0; while(a[cur_pos]+len2>=a[cur_pos+j] && cur_pos+j<=n && use_2){ x++; j++; } while(a[cur_pos]+len1>=a[cur_pos+k]&& cur_pos+k<=n && use_1){ y++; k++; } if(x>=y*2 && use_2){ use_2--; cur_pos=cur_pos+j; } else{ if(use_1){ use_1--; cur_pos=cur_pos+k; } } if(!use_1 && !use_2 && cur_pos<=n ){ return false; } } if(use_1>=0 && use_2>=0)return true; else return false; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin>>n>>p>>q; for(int i=1 ;i<=n;++i)cin>>a[i]; sort(a+1,a+1+n); if(p+q>=n){ cout<<"1"; return 0; } int l=0,r=1e9; while(l+1<r){ int mid=(l+r)/2; if(check(mid))r=mid; else l=mid; } int ans=1e9; if(check(r))ans=min(ans,r); if(check(l))ans=min(ans,l); cout<<ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...