fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct Data {
  6. 	int i, j, c;
  7. 	Data() {};
  8. 	Data(int i_, int j_, int c_) : i(i_), j(j_), c(c_) {};
  9. };
  10. bool operator <(Data a, Data b) {
  11. 	return a.c < b.c;
  12. }
  13.  
  14. priority_queue<Data> q;
  15.  
  16. vector<int> findHighestSums(vector< vector<int> > lists, int n) {
  17. 	int L = (int) lists.size();
  18. 	vector<int> ans;
  19. 	for (int i = 1; i < L; ++i) {
  20. 		while (! q.empty()) q.pop();
  21. 		for (int j = 0; j < lists[i].size(); ++j) {
  22. 			q.push(Data(0, j, lists[0][0] + lists[i][j]));
  23. 		}
  24. 		for (int j = 0; j < n && ! q.empty(); ++j) {
  25. 			Data k = q.top(); q.pop();
  26. 			ans.push_back(k.c);
  27. 			if (k.i + 1 < lists[0].size()) {
  28. 				q.push(Data(k.i + 1, k.j, lists[0][k.i + 1] + lists[i][k.j]));
  29. 			}
  30. 		}
  31. 		lists[0] = ans;
  32. 		ans.clear();
  33. 	}
  34. 	return lists[0];
  35. }
  36.  
  37. int main() {
  38. 	int n = 5;
  39.  
  40. 	vector< vector<int> > a(5);
  41. 	a[0] = {5,4,3,2,1};
  42. 	a[1] = {4,1};
  43. 	a[2] = {5,0,0};
  44. 	a[3] = {6,4,2};
  45. 	a[4] = {1};
  46. 	vector<int> ans = findHighestSums(a, n);
  47. 	for (int i = 0; i < ans.size(); ++i)
  48. 		cout << ans[i] << ' ';
  49. 	cout << '\n';
  50. 	return 0;
  51. }
  52.  
Success #stdin #stdout 0s 4388KB
comments (?)
stdin 
Standard input is empty
stdout 
21 20 19 19 18
https://ideone.com/SJ7Zl4
language:
C++ (gcc 8.3)
created:
4 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!