Submission #473106

#TimeUsernameProblemLanguageResultExecution timeMemory
473106nicolaalexandraWatching (JOI13_watching)C++14
100 / 100
156 ms16104 KiB
#include <bits/stdc++.h> #define DIM 2010 #define INF 1000000000 using namespace std; int v[DIM],dp[DIM][DIM]; int n,p,q,i; int get_poz (int x){ int st = 1, dr = n, sol = 0; while (st <= dr){ int mid = (st+dr)>>1; if (v[mid] >= x){ sol = mid; dr = mid-1; } else st = mid+1; } return sol; } int verif (int val){ int poz = 1 , poz2 = 1; for (int i=1;i<=n;i++){ while (v[i] - v[poz] + 1 > val) poz++; while (v[i] - v[poz2] + 1 > 2*val) poz2++; //int poz = get_poz (v[i] - val + 1); //int poz2 = get_poz (v[i] - 2 * val + 1); for (int j=0;j<=q;j++){ dp[i][j] = dp[poz-1][j] + 1; if (j) dp[i][j] = min (dp[i][j],dp[poz2-1][j-1]); } } if (dp[n][q] <= p) return 1; return 0; } int main (){ //ifstream cin ("date.in"); //ofstream cout ("date.out"); cin>>n>>p>>q; for (i=1;i<=n;i++) cin>>v[i]; sort (v+1,v+n+1); p = min (p,n), q = min (q,n); int st = 1, dr = INF, sol = 0; while (st <= dr){ int mid = (st+dr)>>1; if (verif(mid)){ sol = mid; dr = mid-1; } else st = mid+1; } cout<<sol; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...