Submission #51449

#TimeUsernameProblemLanguageResultExecution timeMemory
51449huynhsmdWatching (JOI13_watching)C++17
0 / 100
3 ms564 KiB
#include<bits/stdc++.h> using namespace std; #define int long long const int N = 2005; int n , p , q , ans = 1e9; int a[N] , cnt[N]; bool check(int mid){ int x = p , y = q; bool ok = false; for(int i = 1 ; i <= n &&(p > 0 || q > 0); ++ i){ int cur1 = i , idem1 = 0; for(; cur1 <= n ; ++ cur1){ if(a[cur1] - a[i] >= mid ) break; idem1 ++; } int cur2 = i , idem2 = 0; for(; cur2 <= n ; ++ cur2){ if(a[cur2] - a[i] >= 2*mid ) break; idem2 ++; } if(p == 0) q-- , i = cur2 - 1; else if(q == 0) p-- , i = cur1 - 1; else if(idem2 >= idem1 * 2) q-- , i = cur2 - 1; else p-- , i = cur1 - 1; if(i == n) ok =true; } p = x ; q =y; return ok; } signed main(){ //freopen("1.inp","r",stdin); ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> p >> q; a[n+1] = 1e9; for(int i = 1 ;i <= n ; ++ i ) cin >> a[i]; sort(a + 1 , a + n + 1); if( p+q >= n ){ cout << 1; return 0; } int l = 1 , r = a[n] - a[1] + 1; while(l <= r){ int mid = ( l+ r ) / 2; bool kt = check(mid); if(kt){ ans = mid; r = mid - 1; } else l = mid + 1; } cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...