YEZAELP

o58_oct_c1_evergreen

Jul 29th, 2021
569
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using lli = long long;
  5. const lli INF = 1e10;
  6. const lli N = 1e3 + 10;
  7. lli ar[N];
  8. lli n, k;
  9.  
  10. lli Area(lli l, lli r){
  11.     lli base = r - l + 1;
  12.     if(base <= 0) return 0;
  13.     if(base % 2 != 0) return (base + 1) * (base + 1) / 4;
  14.     return base * (base + 2) / 4;
  15. }
  16.  
  17. bool check(lli x){
  18.     lli sum = 0;
  19.     for(int i=1;i<=n;i++){
  20.         lli area = Area(ar[i] - x, ar[i] + x);
  21.         lli overlap = i + 1 <= n ? Area(ar[i+1] - x, ar[i] + x): 0;
  22.         sum += area - overlap;
  23.     }
  24.     return sum >= k;
  25. }
  26.  
  27. int main(){
  28.  
  29.     scanf("%lld%lld", &n, &k);
  30.  
  31.     for(lli i=1;i<=n;i++)
  32.         scanf("%lld", &ar[i]);
  33.  
  34.     sort(ar + 1, ar + n + 1);
  35.  
  36.     lli l = 0, r = INF, ans = INF;
  37.     while(l <= r){
  38.         lli mid = (l + r) / 2;
  39.         bool ch = check(mid);
  40.         if(ch) r = mid - 1, ans = min(ans, mid);
  41.         else l = mid + 1;
  42.     }
  43.  
  44.     printf("%lld", ans);
  45.  
  46.     return 0;
  47. }
RAW Paste Data