# one test case not passing in problem FORESTGA

enter code here
[1]: https://www.codechef.com/viewsolution/13370771

``````#include<bits/stdc++.h>
#include<stdio.h>
using namespace std;
#define ll long long int
void MergeSort(ll *p,ll *q,ll low,ll high,ll min);
void Merge(ll *p,ll *q,ll low,ll mid,ll high,ll min);
ll ciel(long double n);
int main(){
ll n,in[1000000],rt[1000000],req,min,re=9223372036854775807,count=0,sum1=0,sum=0,count1,diff,sum3=0,flag=0,i;
long double x=1.0000000000000000000;
scanf("%lld%lld%lld",&n,&req,&min);
for(i=0;i<n;i++){
scanf("%lld%lld",&in[i],&rt[i]);
}
MergeSort(in,rt,0,n-1,min);
for(i=n-1;i>=0;i--){
count1=ciel((long double)(min-in[i])/(rt[i]*x));
// printf("%lld re\n",re);
diff=count1-count;
if(count1>=re){
printf("%lld\n",re);
flag=1;
break;
}
sum=(count1*rt[i]+in[i])+sum1*diff+sum;
sum1=sum1+rt[i];
sum3=sum3+in[i];
if(sum>=req){
printf("%lld\n",count1);
flag=1;
break;
}
else{
re=ciel((long double)(req-sum3)/(sum1*x));
count=count1;
}

}
if(!flag)
printf("%lld\n",re);

return 0;

}
ll ciel(long double n){
ll n1;
long double x=0.00000000000000000000;
n1=n;
n=n-n1;
if(n==x)
return n1;
else return (n1+1);

}

void MergeSort(ll *p,ll *q,ll low,ll high,ll min){
ll mid;
if(low<high){
mid=(low+high)/2;
MergeSort(p,q,low,mid,min);
MergeSort(p,q,mid+1,high, min);
Merge(p,q,low,mid,high,min);
}

}
void Merge(ll *p,ll *q,ll low,ll mid,ll high,ll min){
ll k,i,j,b[1000000],c[1000000];
long double x,y,z=1.000000000000000;
i=low,j=mid+1,k=0;
while(i<=mid&&j<=high){
x=(*(p+i)-min)/( *(q+i)*z);
y=(*(p+j)-min)/( *(q+j)*z);
if(x<y){
b[k]=*(p+i);
c[k]=*(q+i);
i++,k++; }
else{
b[k]=*(p+j);
c[k]=*(q+j);
j++,k++;
}
}
while(i<=mid){
b[k]=*(p+i);
c[k]=*(q+i);
i++,k++;
}
while(j<=high){
b[k]=*(p+j);
c[k]=*(q+j);
j++,k++;
}
for(i=low,j=0;i<=high;i++,j++){
*(p+i)=b[j];
*(q+i)=c[j];

}

}``````
1 Like

what are you trying to do , can you please explain â€¦ as far as my instincts say i have to do binary search or may be i can use priority queue

I have sorted the array in the decreasing number of months required by each tree. FUNCTION (MergeSort())

Then checking Linearly for required wood in â€śfor loopâ€ť of main.

1 Like

Upvote me i need karma to upload image

2 Likes

http://ideone.com/jeNTkA refer this link for seeing above code

https://www.codechef.com/viewsolution/13370771 is the link for solution not passing one test case