fork download
copy 
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #define MAX(A, B) A > B ? A : B
  3.  
  4. #include <iostream>
  5. #include <memory.h>
  6. #include <algorithm>
  7.  
  8. using namespace std;
  9.  
  10. int N, M;
  11. int A[3001];
  12. int B[101];
  13. int cache[6][4][4][2];
  14.  
  15. int snack(int a, int b1, int b2, bool skip) {
  16.  
  17. 	int& rt = cache[a][b1][b2][skip];
  18. 	if (rt != -1) return rt;
  19.  
  20. 	cout << a << ' ' << b1 << ' ' << b2 << ' ' << skip << '\n';
  21.  
  22. 	rt = 0;
  23. 	if (skip) {
  24. 		if (a < N) rt = snack(a + 1, b1, b2, 0);
  25. 		if (b1 <= b2) {
  26. 			rt = MAX(rt, snack(a, b1 + 1, b2, 0));
  27. 			rt = MAX(rt, snack(a, b1, b2 - 1, 0));
  28. 		}
  29. 	}
  30.  
  31. 	else {
  32. 		if (a < N) rt = snack(a + 1, b1, b2, 1) + A[a];
  33. 		if (b1 <= b2) {
  34. 			rt = MAX(rt, snack(a, b1 + 1, b2, 1)) + B[b1];
  35. 			rt = MAX(rt, snack(a, b1, b2 - 1, 1)) + B[b2];
  36. 		}
  37. 	}
  38. 	return rt;
  39. }
  40.  
  41. /*
  42. int snack(int a, int b1, int b2, char c) {//c가 0이면 A 선택, 1이면 B1 선택 2이면, B2 선택
  43.  
  44. 	if (a > N) return 0;
  45. 	if (b1 > b2) return -987654321;
  46.  
  47. 	int& rt = cache[a][b1][b2];
  48. 	if (rt != -1) return rt;
  49.  
  50. 	if (c == 0) {
  51. 		// 고르는 경우
  52. 		rt = snack(a + 2, b1, b2, 0); //다음것이 a
  53. 		rt = MAX(rt, snack(a + 1, b1 + 1, b2, 1)); // 다음것이 b1
  54. 		rt = MAX(rt, snack(a + 1, b1, b2 - 1, 2)); // 다음것이 b2
  55. 		rt += A[a];
  56.  
  57. 		// 안고르는 경우
  58. 		rt = MAX(rt, snack(a + 1, b1, b2, 0)); // 다음것이 a
  59. 		rt = MAX(rt, snack(a + 1, b1, b2, 1)); // 다음것이 b1
  60. 		rt = MAX(rt, snack(a + 1, b1, b2, 2)); // 다음것이 b2
  61. 	}
  62.  
  63. 	else if (c == 1){
  64. 		// 고르는 경우
  65. 		rt = snack(a + 1, b1 + 1, b2, 0); // 다음것이 a
  66. 		rt = MAX(rt, snack(a, b1 + 2, b2, 1)); // 다음것이 b1
  67. 		rt = MAX(rt, snack(a, b1 + 1, b2 - 1, 2)); // 다음것이 b2
  68. 		rt += B[b1];
  69.  
  70. 		// 안고르는 경우
  71. 		rt = MAX(rt, snack(a, b1 + 1, b2, 0)); // 다음것이 a
  72. 		rt = MAX(rt, snack(a, b1 + 1, b2, 1)); // 다음것이 b1
  73. 		rt = MAX(rt, snack(a, b1 + 1, b2, 2)); // 다음것이 b2
  74. 	}
  75.  
  76. 	else {
  77. 		// 고르는 경우
  78. 		rt = snack(a + 1, b1, b2 - 1, 0); // 다음것이 a
  79. 		rt = MAX(rt, snack(a, b1 + 1, b2 - 1, 1)); // 다음것이 b1
  80. 		rt = MAX(rt, snack(a, b1, b2 - 2, 2)); // 다음것이 b2
  81. 		rt += B[b2];
  82.  
  83. 		// 안고르는 경우
  84. 		rt = MAX(rt, snack(a, b1, b2 - 1, 0)); // 다음것이 a
  85. 		rt = MAX(rt, snack(a, b1, b2 - 1, 1)); // 다음것이 b1
  86. 		rt = MAX(rt, snack(a, b1, b2 - 1, 2)); // 다음것이 b2
  87. 	}
  88.  
  89. 	//cout << a << ' ' << b << ' ' << c << "   " << rt << '\n';
  90.  
  91. 	return rt;
  92. }
  93. */
  94. int main(int argc, char** argv) {
  95.  
  96. 	cin.tie(NULL);
  97. 	cout.tie(NULL);
  98. 	ios_base::sync_with_stdio(false);
  99.  
  100. 	int test_case;
  101. 	int T;
  102.  
  103. 	cin >> T;
  104.  
  105. 	for (test_case = 1; test_case <= T; ++test_case) {
  106.  
  107. 		A[0] = B[0] = 0;
  108.  
  109. 		cin >> N;
  110. 		for (int i = 1; i <= N; ++i)
  111. 			cin >> A[i];
  112.  
  113. 		cin >> M;
  114. 		for (int i = 1; i <= M; ++i)
  115. 			cin >> B[i];
  116.  
  117. 		sort(&B[1], &B[M]);
  118.  
  119. 		memset(cache, -1, sizeof(cache));
  120.  
  121. 		int a = MAX(snack(1, 1, M, 0), snack(1, 1, M, 1));
  122.  
  123. 		cout << '#' << test_case << ' ' << a << '\n';
  124. 	}
  125.  
  126. 	return 0;
  127. }
Success #stdin #stdout 0.01s 5396KB
comments (?)
stdin
copy 
1
5
10
12
6
14
7
3
8
1
2
stdout
copy 
1 1 3 0
2 1 3 1
3 1 3 0
4 1 3 1
5 1 3 0
5 2 3 1
5 3 3 0
5 3 2 1
5 2 2 0
5 2 1 1
5 1 2 1
5 1 1 0
5 1 0 1
4 2 3 0
4 3 3 1
4 4 3 0
4 3 2 0
4 2 2 1
4 2 1 0
4 1 2 0
4 1 1 1
4 1 0 0
3 2 3 1
3 3 3 0
3 4 3 1
3 3 2 1
3 2 2 0
3 2 1 1
3 1 2 1
3 1 1 0
3 1 0 1
2 2 3 0
2 3 3 1
2 4 3 0
2 3 2 0
2 2 2 1
2 2 1 0
2 1 2 0
2 1 1 1
2 1 0 0
1 2 3 1
1 3 3 0
1 4 3 1
1 3 2 1
1 2 2 0
1 2 1 1
1 1 2 1
1 1 1 0
1 1 0 1
1 1 3 1
2 1 3 0
3 1 3 1
4 1 3 0
5 1 3 1
5 2 3 0
5 3 3 1
5 3 2 0
5 2 2 1
5 2 1 0
5 1 2 0
5 1 1 1
5 1 0 0
4 2 3 1
4 3 3 0
4 4 3 1
4 3 2 1
4 2 2 0
4 2 1 1
4 1 2 1
4 1 1 0
4 1 0 1
3 2 3 0
3 3 3 1
3 4 3 0
3 3 2 0
3 2 2 1
3 2 1 0
3 1 2 0
3 1 1 1
3 1 0 0
2 2 3 1
2 3 3 0
2 4 3 1
2 3 2 1
2 2 2 0
2 2 1 1
2 1 2 1
2 1 1 0
2 1 0 1
1 2 3 0
1 3 3 1
1 4 3 0
1 3 2 0
1 2 2 1
1 2 1 0
1 1 2 0
1 1 1 1
1 1 0 0
#1 44
https://ideone.com/0un5l9
language:
C++14 (gcc 8.3)
created:
2 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!