Submission #366874

#TimeUsernameProblemLanguageResultExecution timeMemory
366874MODDIWatching (JOI13_watching)C++14
100 / 100
226 ms16236 KiB
#include <bits/stdc++.h> using namespace std; int n, p, q; int D[2020][2020], arr[2020]; bool check(int w) { if (w <= 0) return false; int i,j=1,k=1,l; for (i=1;i<=n;i++){ while (arr[i] - arr[j] >= w) j++; while (arr[i] - arr[k] >= w * 2) k++; for (l=0;l<=q;l++) D[i][l] = D[j-1][l] + 1; for (l=0;l<=q;l++){ if (D[i][l+1] > D[k-1][l]) D[i][l+1] = D[k-1][l]; } } for (l=0;l<=q;l++) if (D[n][l] <= p) return true; return false; } int main(){ cin>>n>>p>>q; for(int i = 1; i <=n; i++){ cin>>arr[i]; } sort(arr + 1, arr + n + 1); if(n <= p + q) cout<<1<<endl; else{ int l = 1, r = 1000000000, mid; while (l < r){ mid = (l + r) / 2; if (check(mid)) r = mid - 1; else l = mid + 1; } while(check(mid)) mid--; while(!check(mid)) mid++; cout<<mid<<endl; return 0; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...