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