fork download 
  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. int steps;
  11.  
  12. void fun (const int position, const int orc1, const int orc2, const int orc3, const int current) {
  13. 	steps++;
  14. 	if (current > answer) {
  15. 		return;//useless branch
  16. 	}
  17. 	if (position == n) {
  18. 		answer = min(answer, current);
  19. 		return;//final state
  20. 	}
  21. 	//fight
  22. 	if (orc1 + orc2 + orc3 >= k[position]) {
  23.         int n1 = orc1, n2 = orc2, n3 = orc3;
  24. 		int enemy = k[position];
  25. 		int toFight = min(enemy, n3);
  26. 		n3 -= toFight;
  27. 		enemy -= toFight;
  28. 		toFight = min(enemy, n2);
  29. 		n2 -= toFight;
  30. 		enemy -= toFight;
  31. 		toFight = min(enemy, n1);
  32. 		n1 -= toFight;
  33. 		enemy -= toFight;
  34. 		fun(position + 1, 0, n1, n2, current);
  35. 	}
  36. 	//pay
  37. 	fun(position + 1, orc1, orc2, orc3, current + c[position]);
  38. 	//hire
  39. 	fun(position + 1, orc1 + k[position], orc2, orc3, current + c[position] + c[position]);
  40. }
  41.  
  42. const bool DEBUG = true;
  43.  
  44. int main () {
  45. 	int tests;
  46. 	cin >> tests;
  47. 	for (int t = 1; t <= tests; t++) {
  48.         steps = 0;
  49. 		cin >> n;
  50. 		for (int i = 0; i < n; i++) {
  51. 			cin >> k[i] >> c[i];
  52. 		}
  53. 		answer = 100000000;
  54.         auto s = clock();
  55. 		fun(0, 0, 0, 0, 0);
  56. 		cout << "#" << t << " " << answer;
  57.         if (DEBUG) {
  58.             cout << " steps = " << steps;
  59.             cout << " time = " << fixed << setprecision(3) << (clock() - s) * 1.0 / CLOCKS_PER_SEC;
  60.         }
  61.         cout << endl;
  62. 	}
  63.  
  64. 	return 0;
  65. }
Success #stdin #stdout 3.46s 4284KB
comments (?)
stdin 
1
20
512 1
256 1
126 1
64 1
32 1
16 1
8 1
4 1
2 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1000 1000
stdout 
#1 23 steps = 1327729094 time = 3.456
https://ideone.com/jKEONy
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!