Submission #51470

#TimeUsernameProblemLanguageResultExecution timeMemory
51470mergesortWatching (JOI13_watching)C++14
50 / 100
112 ms3964 KiB
#include<bits/stdc++.h> using namespace std; int a[2005],n,p,q; int len1[2005],len2[2005],dp[2005][2005]; bool check(int w) { for(int i=1;i<=n;++i){ len1[i]=len2[i]=i; for(int j=i+1;j<=n;++j){ if(a[i]+w-1>=a[j])len1[i]=j; if(a[i]+2*w-1>=a[j])len2[i]=j; } } len1[n+1]=len2[n+1]=n; dp[0][1]=len2[1];dp[1][0]=len1[1]; for(int i=1;i<=p;++i){ for(int j=1;j<=q;++j){ int pos1=dp[i-1][j],pos2=dp[i][j-1]; if(pos1>=n || pos2>=n)dp[i][j]=n; pos1++; pos2++; dp[i][j]=max(len1[pos1],len2[pos2]); } } if(dp[p][q]>=n)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; } //cout<<check(4)<<"\n****"<<endl; 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...