fork(16) download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define pii pair<int,int>
  6. #define ll long long
  7. #define N (int)(5e5+10)
  8. #define mod 1000000007
  9. #define mp make_pair
  10. #define pb push_back
  11. #define nd second
  12. #define st first
  13. #define inf mod
  14. #define endl '\n'
  15. #define sag (sol|1)
  16. #define sol (root<<1)
  17. #define bit(x,y) ((x>>y)&1)
  18.  
  19. ll t;
  20. int a[N],i,j,k,n,m,x,y,z;
  21.  
  22. int main(){
  23. 	cin >> n >> k;
  24.  
  25. 	for(i=1 ; i<=n ; i++)
  26. 		scanf("%d",a+i);
  27.  
  28. 	int bas=1;, son=2*inf;
  29.  
  30. 	while(bas<son){
  31. 		int ort = ((ll)bas+son)/2;
  32. 		if(bas==ort)
  33. 			ort++;
  34. 		t = 0;
  35. 		for(i=1 ; i<=n ; i++)
  36. 			t += max(0 , ort-a[i]);
  37. 		if(t <= k)
  38. 			bas = ort;
  39. 		else
  40. 			son = ort-1;
  41. 	}
  42.  
  43. 	t = k;
  44.  
  45. 	for(i=1 ; i<=n ; i++){
  46. 		t -= max(0 , bas-a[i]);
  47. 		a[i] = max(a[i] , bas);
  48. 	}
  49.  
  50. 	for(i=1 ; i<=n ; i++)
  51. 		if(a[i] == bas and t){
  52. 			t--;
  53. 			a[i]++;
  54. 		}
  55.  
  56. 	bas=1, son=2*inf;
  57.  
  58. 	while(bas<son){
  59. 		int ort = ((ll)bas+son)/2;
  60. 		t = 0;
  61. 		for(i=1 ; i<=n ; i++)
  62. 			t += max(0 , a[i]-ort);
  63. 		if(t <= k)
  64. 			son = ort;
  65. 		else
  66. 			bas = ort+1;
  67. 	}
  68.  
  69. 	t = k;
  70.  
  71. 	for(i=1 ; i<=n ; i++){
  72. 		t -= max(0 , a[i]-bas);
  73. 		a[i] = min(a[i] , bas);
  74. 	}
  75.  
  76. 	for(i=1 ; i<=n ; i++)
  77. 		if(a[i] == bas and t){
  78. 			t--;
  79. 			a[i]--;
  80. 		}
  81.  
  82. 	cout << *max_element(a+1,a+1+n) - *min_element(a+1,a+1+n) << endl;
  83.  
  84. }
  85.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp: In function 'int main()':
prog.cpp:28:12: error: expected primary-expression before ',' token
  int bas=1;, son=2*inf;
            ^
prog.cpp:28:14: error: 'son' was not declared in this scope
  int bas=1;, son=2*inf;
              ^
stdout
copy 
Standard output is empty
https://ideone.com/cc3KO5
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!