Submission #51459

#TimeUsernameProblemLanguageResultExecution timeMemory
51459vivukhueWatching (JOI13_watching)C++14
100 / 100
126 ms16380 KiB
#include <bits/stdc++.h> #define fw(i,l,r) for (int i=l;i<r;i++) using namespace std; int n,p,q; int a[2001]; int fars[2001]; int farl[2001]; int dp[2001][2001]; bool check(int w) { for(int i=0;i<n;i++) { fars[i] = upper_bound(a,a+n,a[i]+w-1) - a; farl[i] = upper_bound(a,a+n,a[i]+2*w-1) - a; } memset(dp,-1,sizeof(dp)); dp[0][0] = 0; for(int i=0;i<=p;i++) { for(int j=0;j<=q;j++) { if(dp[i][j]!=-1) { if(dp[i][j]==n) return true; dp[i+1][j] = max(dp[i+1][j],fars[dp[i][j]]); dp[i][j+1] = max(dp[i][j+1],farl[dp[i][j]]); } } } return false; } signed main() { cin>>n>>p>>q; for(int i=0;i<n;i++) cin>>a[i]; if(p+q>=n) { cout<<1; return 0; } sort(a,a+n); //for(int i=0;i<n;i++) //cout<<a[i]<<" "; int L=1,R=1e9; while(L!=R) { int mid = (L+R)/2; if(check(mid)) R = mid; else L = mid+1; } cout<<L; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...