< Back to forum

SPOJ EKO WA

#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;
}
 

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


Enter your answer details below:


Preview

Enter your comment details below:

Preview




2 Answer(s)

avatar

You have assumed in your solution that there always exists a value of mid for which "sum" will eventually be equal to "m". This may not be always true. In other cases you need to output that value of height for which sum>m.

Also, the least value of low will be 0 as you may need to cut even the shortest tree to get the desired amount of wood.

RUCHI_SINGH1 last updated on April 7, 2019, 6:34 p.m. 0    Reply    Upvote   

avatar

"Help Mirko find the maximum integer height of the saw blade that still allows him to cut off at least M meters of wood."

I think u missed "at least".

check this case :)

10
46846
465 465 6659 55 3 455 45 45 1213 40000

 

rishup132 last updated on April 7, 2019, 6:34 p.m. 0    Reply    Upvote   

Instruction to write good question
  1. 1. Write a title that summarizes the specific problem
  2. 2. Pretend you're talking to a busy colleague
  3. 3. Spelling, grammar and punctuation are important!

Bad: C# Math Confusion
Good: Why does using float instead of int give me different results when all of my inputs are integers?
Bad: [php] session doubt
Good: How can I redirect users to different pages based on session data in PHP?
Bad: android if else problems
Good: Why does str == "value" evaluate to false when str is set to "value"?

Refer to Stack Overflow guide on asking a good question.