1140C. Playlist - Codeforces Solution C++

  Problem Link : 1140C. Playlist 


✅ C++ Solution :

 
#include<bits/stdc++.h>
using namespace std;

#define ll long long int
vector<pair<ll,ll> > v;
struct comp{
	bool operator()(ll x,ll y)
	{
		return v[x].second < v[y].second;
	}
};


int main()
{
	ll n,k,l,b,ind;
	cin>>n>>k;
	v.clear();
	for(ll i=0;i<n;i++)
	{
		cin>>l>>b;
		v.push_back(make_pair(b,l));
	}
	if(k==1)
	{
	    ll ans=0;
	    for(ll i=0;i<n;i++)
	        ans=max(ans,v[i].second*v[i].first);
	    cout<<ans;
	    exit(0);
	}
	sort(v.begin(),v.end());
	multiset<ll,comp> s;
	ll cnt=0;
	ll ans=0;
	ll small=0;
	for(ll i= n-1;i>=0;i--)
	{
		ans=max(ans,((cnt+v[i].second)*v[i].first));
		if(s.size() < k-1)
		{
			s.insert(i);
			cnt+=v[i].second;

		}
		else
		{
			ind=*(s.begin());
			if(v[i].second <= v[ind].second)
			{
			//	s.insert(i);
			}
			else
			{
				/*auto it = s.find(ind);
				cnt-=v[(*(it))].second;
				it++;
				small=*(it);
				s.insert(i);
				cnt+=v[i].second;*/

				s.erase(s.begin());
				cnt-=v[ind].second;
				s.insert(i);
				cnt+=v[i].second;

			}
		}
		
	}
	cout<<ans<<"\n";
}

 

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!!