Submission #76475750

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define int long long

const int inf = 1e9+7;	 


void solve() {
	int n,k,m; 
	cin >> n >> k >> m;
	vector<pair<int,int>> values(n+1);
	for(int i=1; i<n+1; i++) {
		int temp_c, temp_v;
		cin >> temp_c >> temp_v;
		values[i]={temp_c, temp_v};
	}
	sort(values.begin()+1, values.end(), [&](pair<int,int> a, pair<int,int> b) {
		if(a.second!=b.second) {
			return a.second > b.second;   //just sort according to values first.
		}
		return a.first > b.first;    //prevents same color, same values -> gives variety.
	});
	int max_v=0;
	int total_picked=0;
	//first ensure variety - take max values from each color:
	int unique_color_cnt=0;
	vector<bool> colors_included(n+1,false);
	vector<bool> valid(n+1,true);   //a valid index from the sorted array values will be included for max_v calc once the bare minimum variety is confirmed.
	for(int i=1; i<n+1; i++) {
		if(!colors_included[values[i].first] && unique_color_cnt<m)  {
			max_v+=values[i].second;
			colors_included[values[i].first] = true;
			valid[i]=false;
			unique_color_cnt++;
			total_picked++;
			// cout << "new color chosen: " << values[i].first << "value chosen: " << values[i].second <<  endl;
		}
	}
	// cout << total_picked << endl;
	//now add the remaining overall max values until k gems are there - from the valid indices ofc:
	for(int i=1; i<n+1; i++) {
		if(valid[i] && total_picked<k) {
			// cout << "total picked: " << total_picked << endl;
			max_v+=values[i].second;
			total_picked++;
		}	
	}
	cout << max_v; 
}


signed main() {

	#ifdef local
	auto _clock_start = chrono::high_resolution_clock::now();
	#endif

	ios::sync_with_stdio(false);
	cin.tie(0); 
	int tc = 1;
	// cin >> tc;
	while(tc--) {
		solve();
		cout << nl;
	}

	#ifdef local
	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - _clock_start).count() << "ms." << nl;
	#endif

	return 0;
}

Submission Info

Judge Result