I am getting WA for my code in the question - http://www.spoj.com/problems/FRSCR/
My solution -
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll fun2(ll x,ll a[],ll b[],ll n,ll m,ll p)
{
ll count=0,r=0;
for(ll i=0;i<n;i++)
{
ll pos=a[i],val=0,c=1;
while(val<=x)
{
val+=(pos*c);
if(val>x)
break;
r=max(r,val);
count++;
c++;
}
}
return r;
}
ll fun1(ll x,ll a[],ll b[],ll n,ll m,ll p)
{
ll count=0,r=0;
for(ll i=0;i<n;i++)
{
ll pos=a[i],val=0,c=1;
while(val<=x)
{
val+=(pos*c);
if(val>x)
break;
r=max(r,val);
count++;
c++;
}
}
ll reqd1=count;
//return reqd1;
ll reqd2=0;
for(ll i=0;i<m;i++)
{
ll pos=b[i],val=r,c=1;
while(val<=p)
{
val+=(pos*c);
if(val>p)
break;
reqd2++;
c++;
}
}
//return reqd2;
//cout<<reqd1<<" "<<reqd2<<" here"<<endl;
return min(reqd1,reqd2);
}
ll fun(ll x,ll a[],ll b[],ll n,ll m,ll p)
{
ll count=0,r=0;
for(ll i=0;i<n;i++)
{
ll pos=a[i],val=0,c=1;
while(val<=x)
{
val+=(pos*c);
if(val>x)
break;
r=max(r,val);
count++;
c++;
}
}
ll reqd1=count;
//return reqd1;
ll reqd2=0;
for(ll i=0;i<m;i++)
{
ll pos=b[i],val=r,c=1;
while(val<=p)
{
val+=(pos*c);
if(val>p)
break;
reqd2++;
c++;
}
}
//return reqd2;
//cout<<reqd1<<" "<<reqd2<<" here"<<endl;
return (reqd1-reqd2);
}
void binarysearch(ll p,ll n,ll m,ll a[],ll b[])
{
ll low=0,high=p,mid=0,maxi=0,times=0;
for(ll i=0;i<n;i++)
{
ll pos=a[i],val=0,c=1;
while(val<=p)
{
val+=(pos*c);
if(val>p)
break;
maxi++;
c++;
}
}
while(low<high)
{
mid=low+(high-low)/2;
ll value=fun(mid,a,b,n,m,p);
//cout<<low<<" "<<high<<" "<<mid<<" "<<value<<" "<<maxi<<endl;
if(value>=0)
{
if(value<=maxi)
{
maxi=value;
times=fun2(mid,a,b,n,m,p);
high=mid;
}
else
low=mid;
}
else
{
if(((high-low)==1))
break;
else
low=mid;
}
}
cout<<fun1(times,a,b,n,m,p)<<endl;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
ll p,n,m;
scanf("%lld",&p);
scanf("%lld %lld",&n,&m);
ll a[n];
ll b[m];
for(ll i=0;i<n;i++)
scanf("%lld",&a[i]);
for(ll i=0;i<m;i++)
scanf("%lld",&b[i]);
binarysearch(p,n,m,a,b);
}
return 0;
}