Problem Link:
Practice
Contest
Author: Pratik Suryawanshi
Editorialist: Pratik Suryawanshi
DIFFICULTY:
Moderate
PREREQUISITES:
Binary Search
PROBLEM:
Luffy needs to reach grandline ASAP. Lufi’s ship is K kilometer far from grandline .
But luffy consumes 1 unit of food for every kilometer the ship covers and luffy can
never be hungry until he reaches grandline. There are N islands between ship’s current
position and grandline . ith Island is Di appart from grandline and has Ai amount of food.
Luffy currently has F amount of food. You need to tell minimum number of islands
luffy needs to stop at so that he never is hungry before reaching grandline.
If its not possible to reach grandline without luffy being hungry, then print “-1”.
QUICK EXPLANATION:
print minimum number of islands do luffy will need to stop to take food
if not possible, print -1.
SOLUTIONS:
Setter's Solution
#pragma GCC optimize(“Ofast”)
#pragma GCC target(“avx,avx2,fma”)
#pragma GCC optimization(“unroll-loops”)
#include <bits/stdc++.h>
using namespace std;
#define tc ll t sc cin >> t sc while (t–)
#define ff first
#define vp vector<pair<ll,ll>>
#define sc ;
#define ss second
#define srt sort
#define endl ‘\n’
#define pb push_back
#define pp pop_back
#define mp make_pair
#define modulo 1e9+7
#define ll long long int
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define INF 1001001001
const long double pi = 3.141592653;
typedef unsigned int ui;
typedef unsigned long long int ul;
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("errorf.txt" , "w" , stderr) ;
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
tc
{
// code here
ll n,k,f;
cin >> n>>k>>f;
vp prs;
for(ll i=0;i<n;i++)
{
ll dist,food;
cin >> dist >> food;
prs.pb({k-dist, food});
}
ll ans=0;
multiset<ll> food_avl;
srt(prs.begin(), prs.end());
bool can_reach = true;
ll cur = 0;
for(ll i=1;i<k;i++)
{
f--;
if(prs[cur].ff == i)
{
food_avl.insert(prs[cur].ss);
cur++;
}
if( f == 0)
{
if(food_avl.size() == 0)
{
can_reach = false;
break;
}
else
{
auto it= --food_avl.end();
f+= (*it);
food_avl.erase(it);
ans++;
}
}
}
if(can_reach)
{
cout << ans << endl;
}
else
{
cout << -1 << endl;
}
}
return 0;
}