#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() 
{
    ll n,m,l=0,s=0;
    scanf("%lld %lld",&n,&m);
    ll a[n];
    for(ll i=0;i<n;i++)
    {
        scanf("%lld",&a[i]);
        if(a[i]>l)
         l=a[i];
        if(i==0) 
         s=a[i];
        else
        {
            if(a[i]<s)
             s=a[i];
        }
    }
    if(n>1)
    {
    sort(a,a+n);
    ll low=s,high=l,mid=0;
    ll sum=0;
    while(low<=high)
    {
        mid=(low+high)/2;
        ll pos=lower_bound(a,a+n,mid)-a;
        //cout<<mid<<" "<<pos<<endl;
        for(ll j=pos;j<n;j++)
        {
            sum+=(a[j]-mid);
        }
        if(sum>m)
         low=mid+1;
        else if(sum<m)
         high=mid-1;
        else
        {
            printf("%lld\n",mid);
            break;
        }
        sum=0;
    }
    }
    else
     printf("%lld\n",(a[0]-m));
    return 0;
}
 

spoj binary search

Asked by: Shivam_Singhal on April 7, 2019, 6:34 p.m. Last updated on April 7, 2019, 6:34 p.m.