fork(1) download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. long long N, M, A[100001], S[100001], C[100001];
  5.  
  6. int main() {
  7. 	cin >> N >> M;
  8. 	for(int i = 0; i < N; i++)
  9. 		cin >> A[i];
  10. 	sort(A, A+N, greater<int>());
  11. 	S[0] = A[0];
  12. 	C[0] = 0;
  13. 	for(int i = 1; i < N; i++) {
  14. 		S[i] = S[i-1]+A[i];
  15. 		C[i] = S[i] - (i+1)*A[i];
  16. 	}
  17. 	A[N] = 0;
  18. 	C[N] = S[N-1]; // cut at 0
  19. 	/*
  20. 	for(int i = 0; i < N; i++)
  21. 		cout << A[i] << " ";
  22. 	cout << endl;
  23. 	for(int i = 0; i < N; i++)
  24. 		cout << S[i] << " ";
  25. 	cout << endl;
  26. 	for(int i = 0; i < N; i++)
  27. 		cout << C[i] << " ";
  28. 	cout << endl;
  29. 	/**/
  30. 	if(S[N-1] < M)
  31. 		cout << -1 << endl;
  32. 	else {
  33. 		int lo = 0, hi = N-1, mid;
  34. 		while(hi > lo) {
  35. 			// cout << lo << " " << hi << endl;
  36. 			mid = (lo+hi+1)/2;
  37. 			if(C[mid] > M)
  38. 				hi = mid-1;
  39. 			else
  40. 				lo = mid;
  41. 		}
  42. 		cout << lo << " " << C[lo] << endl;
  43. 		cout << A[lo+1] + (C[lo+1]-M)/(lo+1) << endl;
  44. 	}
  45. 	return 0;
  46. }
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin 
10 250
40 20 90 90 50 30 60 70 20 100
stdout 
6 220
35
https://ideone.com/Leg1rT
language:
C++ (gcc 8.3)
created:
7 days 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!