Hello all,
I made the below solution for this question. It also passed all test cases given in the editorial.
But, Codechef is throwing WA when submitted. What could be the reason?
#include<iostream>
#include<vector>
typedef long long int ll;
using namespace std;
// RECURSIVE CODE
ll total(ll N, ll *A, ll *B, ll X, ll Y)
{
if(N==0)
return 0;
return max(X>0?(A[N-1]+total(N-1, A, B, X-1, Y)):0, Y>0?(B[N-1]+total(N-1, A, B, X, Y-1)):0);
}
// MEMOIZED CODE
ll mem_total(ll N, ll *A, ll *B, ll X, ll Y, ll **mem)
{
if(N==0)
return 0;
if((X>0 && mem[X-1][Y] != 0) && (Y>0 && mem[X][Y-1] != 0))
mem[X][Y] = max(A[N-1] + mem[X-1][Y], B[N-1] + mem[X][Y-1]);
else
mem[X][Y] = max(X>0?(A[N-1]+mem_total(N-1, A, B, X-1, Y, mem)):0,
Y>0?(B[N-1]+mem_total(N-1, A, B, X, Y-1, mem)):0);
}
main()
{
ll N, X, Y;
cin>>N>>X>>Y;
ll **mem;
mem = new ll*[X+1];
for(int i=0; i<=X; i++)
mem[i] = new ll[Y+1];
ll A[N], B[N];
for(ll i=0; i<N; i++)
cin>>A[i];
for(ll i=0; i<N; i++)
cin>>B[i];
mem_total(N, A, B, X, Y, mem);
cout<<mem[X][Y]<<endl;
}