fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int const nMax = 20;
  6.  
  7. int n, k[nMax], c[nMax];
  8.  
  9. int answer;
  10.  
  11. void fun (int position, int orc1, int orc2, int orc3, int current) {
  12. 	if (current > answer) {
  13. 		return;//useless branch
  14. 	}
  15. 	if (position == n) {
  16. 		answer = min(answer, current);
  17. 		return;//final state
  18. 	}
  19. 	//pay
  20. 	fun(position + 1, orc1, orc2, orc3, current + c[position]);
  21. 	//hire
  22. 	fun(position + 1, orc1 + k[position], orc2, orc3, current + c[position] + c[position]);
  23. 	//fight
  24. 	if (orc1 + orc2 + orc3 >= c[position]) {
  25. 		int enemy = k[position];
  26. 		int toFight = min(enemy, orc3);
  27. 		orc3 -= toFight;
  28. 		enemy -= toFight;
  29. 		toFight = min(enemy, orc2);
  30. 		orc2 -= toFight;
  31. 		enemy -= toFight;
  32. 		toFight = min(enemy, orc1);
  33. 		orc1 -= toFight;
  34. 		enemy -= toFight;
  35. 		fun(position + 1, 0, orc1, orc2, current);
  36. 	}
  37. }
  38.  
  39. int main () {
  40. 	int tests;
  41. 	cin >> tests;
  42. 	for (int t = 1; t <= tests; t++) {
  43. 		cin >> n;
  44. 		for (int i = 0; i < n; i++) {
  45. 			cin >> k[i] >> c[i];
  46. 		}
  47. 		answer = 100000000;
  48. 		fun(0, 0, 0, 0, 0);
  49. 		cout << "#" << t << " " << answer << endl;
  50. 	}
  51.  
  52. 	return 0;
  53. }
Success #stdin #stdout 3.5s 4296KB
comments (?)
stdin
copy 
5
20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
20 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
20 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
20 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
20 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
stdout
copy 
#1 20
#2 40
#3 60
#4 80
#5 100
https://ideone.com/yZQbEO
language:
C++14 (gcc 8.3)
created:
6 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!