fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. long long findMaximumProfit(vector<int>& category, vector<int>& price) {
  5.     int n = category.size();
  6. 	unordered_map<int,vector<int>>items;
  7. 	for (int i = 0 ; i < n; i++){
  8. 		items[category[i]].push_back(price[i]);
  9. 	}
  10. 	vector<int>lowest_item;
  11. 	vector<int>rest_items;
  12. 	// for each cat lets take the min value then re assign the rest
  13.  
  14. 	for (auto &it :items){
  15. 		auto &vp = it.second;
  16. 		sort(vp.begin(),vp.end()); // sort the prices 
  17. 		lowest_item.push_back(vp[0]);
  18. 		// skip the first index
  19. 		for (int i = 1 ; i<vp.size() ;i++){
  20. 			rest_items.push_back(vp[i]);
  21. 		}
  22.  
  23. 	}
  24. 	sort(lowest_item.begin(),lowest_item.end());
  25. 	sort(rest_items.rbegin(),rest_items.rend());
  26.  
  27. 	long long total = 0;
  28. 	int unique= 0; 
  29.  
  30. 	for (int i = 0 ; i < lowest_item.size();i++){
  31. 		unique++;
  32. 		total+=(unique * lowest_item[i]);
  33. 	}
  34. 	// after opening all the cat we can take the rest
  35. 	for (int i = 0 ; i < rest_items.size();i++){
  36. 		total+=(unique * rest_items[i]);
  37. 	}
  38. 	return total;
  39.  
  40. }
  41.  
  42. int main() {
  43.     vector<int> category = {3, 1, 2, 3};
  44.     vector<int> price    = {2, 1, 4, 4};
  45.  
  46.     cout << findMaximumProfit(category, price) << endl; 
  47. }
  48.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
29
https://ideone.com/p3Ng7u
language:
C++14 (gcc 8.3)
created:
1 day 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!