fork download
  1. #include <iostream>
  2. #include<bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6.  
  7. bool check(vector<int> &arr,int mid){
  8. int n = arr.size()-1;
  9. int i=n;
  10. int left=0;
  11.  
  12. while(i>1){
  13.  
  14. if(arr[i]+left>mid){
  15. left = left + arr[i]-mid;
  16.  
  17. }
  18. else{
  19. left=0;
  20.  
  21. }
  22. i--;
  23.  
  24. }
  25.  
  26. return arr[1]+left<=mid;
  27.  
  28. }
  29. int main() {
  30. // your code goes here
  31. int n;
  32. cin>>n;
  33. vector<int> arr(n+1,0);
  34.  
  35. int low = INT_MAX;
  36. int high = INT_MIN;
  37.  
  38. for(int i=1;i<=n;i++){
  39. cin>>arr[i];
  40. low = min(low,arr[i]);
  41. high = max(high,arr[i]);
  42.  
  43. }
  44. int ans=0;
  45.  
  46. while(low<=high){
  47. int mid = (low+high)/2;
  48.  
  49. if(check(arr,mid)==true){
  50. ans=mid;
  51. high=mid-1;
  52.  
  53. }
  54. else{
  55. low = mid+1;
  56.  
  57. }
  58. }
  59.  
  60. cout<<ans<<endl;
  61.  
  62.  
  63.  
  64. return 0;
  65. }
Success #stdin #stdout 0s 544KB
stdin
4 
1 5 7 6
stdout
5