fork download
copy 
  1.  
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define ll long long 
  5. #define pb push_back
  6. #define lcm(a,b) ll lcm_function(ll a , ll b) return (a*b)/__gcd(a,b);
  7.  
  8. void solve ()
  9. {
  10.   int n;cin >> n;
  11.   map<int,multiset<int>> mp;
  12.  
  13.   // maximum possible jobs that can be done------
  14.  int max_val = INT_MIN;
  15.  
  16.   for(int i = 0 ;i<n;i++)
  17.   {
  18.      int a,b,c;
  19.  
  20.      cin >> a >> b >> c; //ignore 'a' its just job id, I don't care about it------
  21.  
  22.      mp[b].insert(c); // storing jobs deadline as key in map and storing profit for a particular dealine in sorted order---
  23.  
  24.      max_val = max(max_val,b); //calculating maximum possibel jobs-----
  25.   }
  26.  
  27.  
  28.  
  29.  multiset<int> final_jobs; // multiset for maximum possible job's profit for every deadline--- 
  30.  
  31.   for(auto &x:mp)
  32.   {
  33.     auto it = x.second.end(); // traversing profit in decreasing order for a particular deadline----
  34.     it--;
  35.     for(int i=0;i<min(x.first,(int)x.second.size());i++) {final_jobs.insert(*it);it--;} 
  36.     // for a particular deadline, traversing it for min(maximum possilbe jobs for that deadline,given jobs of that deadline)---
  37.   }
  38.  
  39.   auto it = final_jobs.end();
  40.   it--;
  41.   int terms=0,total=0;
  42.   for(int i=0;i<min(max_val,(int)final_jobs.size());i++) {terms++;total+=(*it);it--;}
  43.   // traversing maximum jobs possible for min(maximum deadline among all, size of final jobs)--
  44.   cout<<terms<<" "<<total<<"\n";
  45.  
  46. }
  47.  
  48. int main()
  49. {
  50. ios_base::sync_with_stdio(false);
  51. cin.tie(NULL);
  52. cout.tie(NULL);
  53.  
  54.   solve();
  55.  
  56. }
  57.  
Success #stdin #stdout 0.01s 5568KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 0
https://ideone.com/nzJ8Df
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!