fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ll;
  4. vector <ll> b ;
  5. ll n,k ;
  6.  
  7. bool check(ll g){
  8. 	ll t = g*k;
  9. 	ll i=1;
  10. 	while(i<=n){
  11. 		if(b[i] > g){
  12. 			t = t - g;
  13. 		}else{
  14. 			t = t - b[i];
  15. 		}
  16. 		i++;
  17. 	}
  18. 	if(t <= 0){
  19. 		return true;
  20. 	}
  21. 	return false;
  22.  
  23. }
  24.  
  25. int main() {
  26.  
  27. 	cin>>n;
  28.     cin>>k;
  29.     b.resize(n+5,0);
  30.  
  31. 	ll sum = 0;
  32. 	ll i =1 ;
  33. 	while(i<=n){
  34. 		cin >> b[i];
  35. 		sum += b[i];
  36. 		i++;
  37. 	}
  38.  
  39. 	ll ans = 0;
  40.  
  41. 	//apply binary search
  42. 	ll low = 1;
  43. 	ll high = 1e18;
  44. 	ll y=0;
  45. 	while (low <= high && y == 0) {
  46.     	ll mid = low + (high - low) / 2;
  47.  
  48.     	if (check(mid) && !check(mid + 1)) {
  49.     	 ans = mid;
  50.          y = 1;
  51.     	}
  52.     	else if (check(mid)) {
  53.         	low = mid + 1;
  54.     	}
  55.     	else {
  56.         	high = mid - 1;
  57.     	}
  58. 	}
  59.  
  60. 	cout <<ans<<endl;
  61. 	return 0;
  62. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin 
4 2
2 3 5 3
stdout 
6
https://ideone.com/eHegE1
language:
C++ (gcc 8.3)
created:
18 days ago
visibility:
secret

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!