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[3003][103][103][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. 	rt = 0;
  21. 	if (skip) {
  22. 		if (a < N) rt = snack(a + 1, b1, b2, 0);
  23. 		if (b1 <= b2) {
  24. 			rt = MAX(rt, snack(a, b1 + 1, b2, 0));
  25. 			rt = MAX(rt, snack(a, b1, b2 - 1, 0));
  26. 		}
  27. 	}
  28.  
  29. 	else {
  30. 		if (a < N) rt = snack(a + 1, b1, b2, 1) + A[a];
  31. 		if (b1 <= b2) {
  32. 			rt = MAX(rt, snack(a, b1 + 1, b2, 1)) + B[b1];
  33. 			rt = MAX(rt, snack(a, b1, b2 - 1, 1)) + B[b2];
  34. 		}
  35. 	}
  36. 	return rt;
  37. }
  38.  
  39. int main(int argc, char** argv) {
  40.  
  41. 	cin.tie(NULL);
  42. 	cout.tie(NULL);
  43. 	ios_base::sync_with_stdio(false);
  44.  
  45. 	int test_case;
  46. 	int T;
  47.  
  48. 	cin >> T;
  49.  
  50. 	for (test_case = 1; test_case <= T; ++test_case) {
  51.  
  52. 		A[0] = B[0] = 0;
  53.  
  54. 		cin >> N;
  55. 		for (int i = 1; i <= N; ++i)
  56. 			cin >> A[i];
  57.  
  58. 		cin >> M;
  59. 		for (int i = 1; i <= M; ++i)
  60. 			cin >> B[i];
  61.  
  62. 		sort(&B[1], &B[M]);
  63.  
  64. 		memset(cache, -1, sizeof(cache));
  65.  
  66. 		int a = MAX(snack(1, 1, M, 0), snack(1, 1, M, 1));
  67.  
  68. 		cout << '#' << test_case << ' ' << a << '\n';
  69. 	}
  70.  
  71. 	return 0;
  72. }
Success #stdin #stdout 0.09s 252604KB
comments (?)
stdin
copy 
1
5
10
12
6
14
7
3
8
1
2
stdout
copy 
#1 44
https://ideone.com/DwF2dk
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!