B. Red and Blue | DP | Codeforces

 pRoBleM  Link :https://codeforces.com/contest/1469/problem/B

Solution :

1.  
2. #include<bits/stdc++.h>
3. using namespace std;
4.  
5. #define int long long
6. #define pII pair<int,int>
7. #define mem(a,b) memset(a,b,sizeof(a))
8.  
9. #define do(i, a, b) for (int i=(a); i<(b); i++)
10. #define dor(i,a,b) for (int i = (b)-1; i >= (a); i--)
11.  
12. #define com(s) (s).begin(),(s).end()
13. #define F first
14. #define S second
15. #define pb push_back
16. #define CASES int tc;cin>>tc;while(tc--)
17. #define UNIQUE(X) (X).erase(unique(S(X)),(X).end())
18. #define IOS ios_base::sync_with_stdio(false); cin.tie(NULL);
19. #define TD(R, C) vector< vector<int>> TD((R), vector<int> (C));
20. #define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
21. #define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
22. #define endl '\n'
23.  
24. const int M = 1e9 + 7;
25. const int MAXN = 10000001;
26. const int INF = 1e18;
27.  
28. //DEBUGGING-TOOL
29. #define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
30. void err(istream_iterator<string> it) {}
31. template<typename T, typename... Args>
32. void err(istream_iterator<string> it, T a, Args... args)
33. {
34. cerr << *it << " = " << a << endl;
35. err(++it, args...);
36. }
37.  
38. //CODE
39. int DP[200][200];
40. int32_t main()
41. {
42. IOS
43. CASES
44. {
45. int n;
46. cin >> n;
47. n++;
48. vector < int > a(n);
49. do(i, 1, n) cin >> a[i];
50. int m;
51. cin >> m;
52. m++;
53. vector <int > b(m);
54. do(i, 1, m) cin >> b[i];
55. do(i, 0, n) do(ii, 0, m) DP[i][ii] = -INF;
56. DP[0][0] = 0;
57. int ans = 0;
58. do(i, 0, n) do(ii, 0, m){
59. if(i) DP[i][ii] = max(DP[i][ii], DP[i - 1][ii] + a[i]);
60. if(ii) DP[i][ii] = max(DP[i][ii], DP[i][ii - 1] + b[ii]);
61. ans = max(ans, DP[i][ii]);
62. }
63. cout << ans << '\n';
67. }
68. }