fork download
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. vector<int64_t> s;
  5. vector<int64_t> e;
  6. int64_t cnp(int64_t l, int64_t r, int64_t tar)
  7. {
  8. if(l>r) return 9999999999999999;
  9. if(l==r)
  10. {
  11. //int arc = e[l];
  12. if(e[l]<=tar)
  13. return l;
  14. return 9999999999999999;
  15. }
  16. int64_t mid = (l+r)/2;
  17. if(e[mid]<=tar)
  18. return min(mid,cnp(l,mid-1,tar));
  19. return cnp(mid+1,r,tar);
  20. }
  21. int main()
  22. {
  23. /*freopen("input.inp","r",stdin);
  24.   freopen("output.out","w",stdout);*/
  25. int64_t n, k;
  26. cin >> n >> k;
  27. vector<int64_t> a(n);
  28. for(int64_t i = 0;i<n;i++)
  29. cin >> a[i];
  30. sort(a.begin(),a.end());
  31. s.assign(n,0);
  32. e.assign(n,0);
  33. for(int64_t i = 1;i<n;i++)
  34. s[i] = (i)*(a[i]-a[i-1])+s[i-1];
  35. for(int64_t i = n-2;i>=0;i--)
  36. e[i] = (n-i-1)*(a[i+1]-a[i]) + e[i+1];
  37. int64_t min_cost = 9999999999999999;
  38. for(int64_t i = 0;i<n;i++)
  39. {
  40. if(s[i]<=k)
  41. {
  42. int64_t x = cnp(i,n-1,k-s[i]);
  43. //cout << i << ' ' << x << '\n';
  44. if(x==i)
  45. {
  46. cout << 0;
  47. return 0;
  48. }
  49. int64_t tt = max(min((k-s[i]-e[x])/(i+1),a[i+1]-a[i]),min((k-s[i]-e[x])/(n-x),a[x]-a[x-1]));
  50. min_cost = min(min_cost,a[x]-a[i]-tt);
  51. }
  52. }
  53. cout << min_cost << '\n';
  54. /*for(int i = 0;i<n;i++)
  55.   cout << a[i] << ' ';
  56.   cout << '\n';
  57.   for(int i = 0;i<n;i++)
  58.   cout << s[i] << ' ';
  59.   cout << '\n';
  60.   for(int i = 0;i<n;i++)
  61.   cout << e[i] << ' ';*/
  62. return 0;
  63. }
  64.  
Runtime error #stdin #stdout #stderr 0s 4548KB
stdin
Standard input is empty
stdout
Standard output is empty
stderr
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc