Submission #779927

#TimeUsernameProblemLanguageResultExecution timeMemory
779927khoquennguoiminhthuongWatching (JOI13_watching)C++17
0 / 100
4 ms8276 KiB
#include<bits/stdc++.h> using namespace std; int dp[2005][2005]; int n,p,q; int a[2005]; bool check(int x) { for(int i=1; i<=n; i++) for(int j=0; j<=p; j++) dp[i][j]=1e9; for(int i=0; i<=p; i++)dp[0][i]=0; int dd1=1,dd2=1; for(int i=1; i<=n; i++) { while(a[i]-a[dd1]+1>x)dd1++; while(a[i]-a[dd2]+1>2*x)dd2++; for(int j=0; j<=p; j++) { dp[i][j]=min(dp[i][j],dp[dd2-1][j]+1); dp[i][j+1]=min(dp[i][j+1],dp[dd1-1][j]); //cout<<i<<" "<<j<<" "<<dp[i][j]<<'\n'; } } return dp[n][p]<=q; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>p>>q; for(int i=1; i<=n; i++)cin>>a[i]; sort(a+1,a+n+1); p=min(p,n); q=min(q,n); int l=0,r=1e9,mid,kq=1e9; while(l<=r) { mid=(l+r)/2; if(check(mid)==1) { r=mid-1; kq=mid; } else l=mid+1; } cout<<kq; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...