fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. vector<string> ans(1000000);
  5. int dp[100][100][100];
  6.  
  7. int lowest_cost_helper(vector<int> blueCosts, vector<int> greenCosts, vector<int> redCosts, int index, int total, int pos) {
  8. 	if(index == blueCosts.size())
  9. 		return pos + abs(total);
  10. 	if(dp[index][total][pos] != -1)
  11. 		return dp[index][total][pos];
  12. 	int r1, r2, r3;
  13. 	if(blueCosts[index]>0 and index>0 and ans[index]!="b")
  14. 		r1 = lowest_cost_helper(blueCosts, greenCosts, redCosts, index+1, total+blueCosts[index], pos+blueCosts[index]);
  15. 	else
  16. 		r1 = lowest_cost_helper(blueCosts, greenCosts, redCosts, index+1, total+blueCosts[index], pos);
  17. 	if(greenCosts[index]>0 and index>0 and ans[index]!="g")
  18. 		r2 = lowest_cost_helper(blueCosts, greenCosts, redCosts, index+1, total+greenCosts[index], pos+greenCosts[index]);
  19. 	else
  20. 		r2 = lowest_cost_helper(blueCosts, greenCosts, redCosts, index+1, total+greenCosts[index], pos);
  21. 	if(redCosts[index]>0 and index>0 and ans[index]!="r")
  22. 		r3 = lowest_cost_helper(blueCosts, greenCosts, redCosts, index+1, total+redCosts[index], pos+redCosts[index]);
  23. 	else
  24. 		r3 = lowest_cost_helper(blueCosts, greenCosts, redCosts, index+1, total+redCosts[index], pos);
  25. 	if(r1<r2 and r1<r3)
  26. 		ans[index]="b";
  27. 	else if(r2<r3 and r2<r1)
  28. 		ans[index]="g";
  29. 	else
  30. 		ans[index]="r";
  31. 	return dp[index][total][pos] = min(r1, min(r2, r3));
  32. }
  33.  
  34. vector<string> lowest_cost(vector<int> blueCosts, vector<int> greenCosts, vector<int> redCosts) {
  35. 	memset(dp, -1, sizeof(dp));
  36.  	int sum = lowest_cost_helper(blueCosts, greenCosts, redCosts, 0, 0, 0);
  37. 	vector<string> color;
  38. 	int i=0;
  39. 	while(i<blueCosts.size()) {
  40. 		color.push_back(ans[i++]);
  41. 	}
  42. 	return color;
  43. }
  44.  
  45. int main() {
  46. 	int n;cin>>n;
  47. 	vector<int> blueCosts(n), redCosts(n), greenCosts(n);
  48. 	for(int i=0;i<n;i++) cin>>blueCosts[i];
  49. 	for(int i=0;i<n;i++) cin>>greenCosts[i];
  50. 	for(int i=0;i<n;i++) cin>>redCosts[i];
  51. 	vector<string> res = lowest_cost(blueCosts, greenCosts, redCosts);
  52. 	for(auto x : res) cout<<x<<" ";
  53. 	return 0;
  54. }
Success #stdin #stdout 0.01s 38360KB
comments (?)
stdin
copy 
3
1 1 1
3 5 7
4 6 4
stdout
copy 
r b b
https://ideone.com/VC3qTI
language:
C++14 (gcc 8.3)
created:
1 year 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!