fork(4) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define pb push_back
  6. #define orta (bas + son >> 1)
  7. #define sag (k + k + 1)
  8. #define sol (k + k)
  9. #define endl '\n'
  10. #define foreach(i,x) for(type(x)i=x.begin();i!=x.end();i++)
  11. #define FOR(ii,aa,bb) for(int ii=aa;ii<=bb;ii++)
  12. #define ROF(ii,aa,bb) for(int ii=aa;ii>=bb;ii--)
  13. #define mp make_pair
  14. #define nd second
  15. #define st first
  16. #define type(x) __typeof(x.begin())
  17.  
  18. typedef pair < int ,int > pii;
  19.  
  20. typedef long long ll;
  21.  
  22. const long long linf = 1e18+5;
  23. const int mod = (int) 1e9 + 7;
  24. const int logN = 17;
  25. const int inf = 1e9;
  26. const int N = 5e5 + 5;
  27.  
  28. int n, k, C[N];
  29.  
  30. void doit() {
  31.  
  32. 	sort(C + 1, C + n + 1);
  33.  
  34. 	int last = C[1], temp = k;
  35.  
  36. 	FOR(i, 2, n) {
  37. 		if((C[i] - last) * (ll) (i - 1) <= k) {
  38. 			k -= (C[i] - last) * (i - 1); 
  39. 			last = C[i];
  40. 		} 
  41. 	}
  42.  
  43. 	int j = 0; while(j + 1 <= n && C[j + 1] <= last) j++;
  44.  
  45. 	int go = k / j, left = k % j;
  46.  
  47. 	FOR(i, 1, j) C[i] = last + go + (i <= left);
  48.  
  49. 	k = temp;
  50. }
  51.  
  52. void rev() { FOR(i, 1, n) C[i] = -C[i];  }
  53.  
  54. int main() {
  55.  
  56. 	scanf("%d %d", &n, &k);
  57.  
  58. 	FOR(i, 1, n)
  59. 		scanf("%d", &C[i]);
  60.  
  61. 	doit(); rev();
  62.  
  63. 	doit(); rev();
  64.  
  65. 	sort(C + 1, C + n + 1);
  66.  
  67. 	printf("%d\n", C[n] - C[1]);
  68.  
  69. 	return 0;
  70. }
  71.  
Success #stdin #stdout 0s 5416KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/WT1j4B
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!