➤ Problem Link : 580B. Kefa and Company
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
bool func(ll val,pair<ll,ll> arr[],int n,int d)
{
ll sum=0;
queue<pair<ll,ll> > q;
pair<ll,ll> fr;
for(ll i=0;i<n;i++)
{
fr=q.front();
if(arr[i].first<d+fr.first)
{
q.push(arr[i]);
sum+=arr[i].second;
if(sum>=val)
return 1;
}
else
{
while(!q.empty() && arr[i].first>=d+q.front().first)
{
sum-=q.front().second;
q.pop();
}
q.push(arr[i]);
sum+=arr[i].second;
if(sum>=val)
return 1;
}
}
return 0;
}
int main()
{
ll n,d,m,s;
cin>>n>>d;
pair<ll,ll> arr[n];
for(int i=0;i<n;i++)
{
cin>>m>>s;
arr[i]=make_pair(m,s);
}
sort(arr,arr+n);
ll low=0;
ll high=pow(10,15);
ll mid;
while(low<high)
{
mid=low+(high-low+1)/2;
if(func(mid,arr,n,d))
low=mid;
else
high=mid-1;
}
cout<<high;
}
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!
I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.