can anyone explain me why greedy technique is giving optimal solution. I am not able to convince myself why greedy is giving optimal solution. I have read the exchange argument, but not able to relate it.

Thanks

can anyone explain me why greedy technique is giving optimal solution. I am not able to convince myself why greedy is giving optimal solution. I have read the exchange argument, but not able to relate it.

Thanks

We donāt need below condition at line number 6 in **backward dp** as It has already been taken care in for loop at line number 4

if (j <= X) {

}

Guys can someone explain me in the test case given in the program andy and bob have 3 orders each

5 3 3

1 2 3 4 5

5 4 3 2 1

Andy can be assigned the last 3 orders of the first row and bob can be assigned the first three orders of the second row.Hence the total comes up to 24 yet we get an o/p of 21 why is that.

I got all the above cases correct but Codechef still shows WA. What could be the reason?

This is the code:

```
#include<iostream>
#include<vector>
typedef long long int ll;
using namespace std;
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* = new ll[Y+1];
ll A[N], B[N];
for(ll i=0; i<N; i++)
cin>>A*;
for(ll i=0; i<N; i++)
cin>>B*;
mem_total(N, A, B, X, Y, mem);
cout<<mem[X][Y]<<endl;
}
```

a great question ,

make me realize that my DP approach was cyclic and was getting wrong ans.

took me over an hour to figure it our

good question, enjoyed solving it. I couldnāt score but I knew it was dp @dpraveen

@brobear1995: it failed on last test case, your code returns 13, test properly - http://ideone.com/OeLs9e

which one ? but I know they are wrong.

I was checking for different greedy approaches.

So when SUB* equals SUB[i-1] you will check the two arrays (take the maximum). Nice approach, will check it.

@abcdexter24: I added one more test case (last one), you code returns 14 for this oneā¦

@abcdexter24: Actually if one solves this problem completely after the contest, he can practice bitmask, dp, recursion and greedy all in one