1082C. Multi - Codeforces Solution C++ ~ CodingWithArt

➤ Problem Link : 1082C. Multi

✅ C++ Solution :

 
#include<bits/stdc++.h>
using namespace std;
 
#define ll long long int
 
bool comp(vector<int> x,vector<int> y)
{
  return x.size()<y.size();
}
 
int main()
{
  int n,m,s,k;
  cin>>n>>m;
  vector<int> subj[m+1];
  for(int i=1;i<=n;i++)
  {
    cin>>s>>k;
    subj[s].push_back(k);
  }
 
  sort(subj,subj+m+1,comp);
 
  for(int i=1;i<=m;i++)
    sort(subj[i].begin(),subj[i].end(),greater<int>());
 
  for(int i=1;i<=m;i++)
  {
    for(int j=1;j<subj[i].size();j++)
      subj[i][j]+=subj[i][j-1];
  }
  int ans=-1;
  vector<int> mp[m+1];
  for(int i=m;i>=1;i--)
  {
    for(int j=0;j<subj[i].size();j++)
    {
      if(i!=m)
        mp[i].push_back(max(subj[i][j],max(subj[i][j]+mp[i+1][j],mp[i+1][j])));
      else
        mp[i].push_back(subj[i][j]);
      ans=max(ans,mp[i][j]);
    }
  }
 
  if(ans>0)
    cout<<ans;
  else
    cout<<"0";
 
}

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

About Utkarsh Gupta

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.