This is working fine for many test cases that I tried, but giving wrong answer upon submitting on spoj.
I have used the fact that we will go to the fuel station with maximum capacity, till the point we can go to using the current fuel.
#include
#include
#include
#include
#include
#include<unordered_map>
#include<unordered_set>
#include
#include
using namespace std;
#define ll long long
#define pp pair<int,int>
#define ppl pair<ll,ll>
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin>>t;
while(t--)
{
ll n,p,l;
cin>>n;
vector<ppl> vec(n);
for(int i=0;i<n;i++)
cin>>vec[i].first>>vec[i].second;
cin>>p>>l;
for(int i=0;i<n;i++)
vec[i].first=p-vec[i].first;
sort(vec.begin(),vec.end());
ll ans=0,curr_pos=0,curr_fuel=l;
// for(int i=0;i<n;i++)
// cout<<vec[i].first<<" "<<vec[i].second<<'\n';
while(1)
{
ppl max_fuel{0,0};
if(curr_pos+curr_fuel>=p)
break;
for(int i=0;i<n;i++)
{
if(vec[i].first<=curr_pos+curr_fuel && vec[i].first>curr_pos)
{
if(vec[i].second>max_fuel.second)
max_fuel=make_pair(vec[i].first,vec[i].second);
}
else if(vec[i].first>curr_pos+curr_fuel)
break;
}
if(max_fuel.second==0)
{
ans=-1;
break;
}
else
{
ans++;
curr_fuel+=max_fuel.second;
curr_fuel-=max_fuel.first-curr_pos;
curr_pos=max_fuel.first;
//cout<<curr_pos<<" "<<curr_fuel<<endl;
}
}
cout<<ans<<'\n';
}
return 0;
}
