This gives WA on the last test case of the first subtask alone resulting in 70 points.

Have I missed out a corner case? Or is there a flaw in my logic?

I can clearly point out the flaw.
Try this case :


3 1 8 2 6 4

0 1 0 1 0 1 //The ones represent the optimal solution

Your code gives 10… I believe it should be 7.

1 Like

Just because (cost[n-1]<cost[0]) does not mean you must take the n-1 th person instead of the 0 th person.

Actually, you should check both cases.

Here is some code that works.

Hey 4 and 6 are adjacent. So one of them has to get a dessert. Hence, the answer has to be 10.

About the base cases, definitely either the last element or first element must be chosen (or both, which comes under the 2nd case).
So if the second element is chosen, it still comes under the above cases. I calculate the optimal solution for each possibility for each knight, dessert given and dessert not given.

Umm okay then I made a mistake… but still the answer has to be 7 (if not 6).
Take the 1 2 and 4. That should fit in. I’ll just re-edit

Yeah you are right. It’s the base cases causing the problem. Thanks!

Yeah, I realized that and corrected it. Thanks anyway :slight_smile: