fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int arr[100000],n,l,r,mid,maxx,ans;
  4. bool check(int x){
  5.     for(int i=2;i<=n;i++){
  6.         if(arr[i]>arr[i-1]){
  7.             if(x>=arr[i]-arr[i-1] && x>=0){
  8.                 x-=(arr[i]-arr[i-1]);
  9.                 arr[i]=arr[i-1];
  10.             }else{
  11.                 return false;
  12.             }
  13.         }
  14.     }
  15.     return true;
  16. }
  17. int main(){
  18.     cin>>n;
  19.     for(int i=1;i<=n;i++){
  20.         cin>>arr[i];
  21.         maxx=max(maxx,arr[i]);
  22.     }
  23.  
  24.     int r=maxx*4,l=0;
  25.     while(l<=r){
  26.         mid=(l+r)/2;
  27.         if(check(mid)){
  28.             ans=mid;
  29.             r=mid-1;
  30.         }else{
  31.             l=mid+1;
  32.         }
  33.     }
  34.     cout<<ans;
  35. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
3
5 7 3
stdout
copy 
Standard output is empty
https://ideone.com/FOTiMz
language:
C++ (gcc 8.3)
created:
6 hours 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!