I am trying to solve this dp problem It looked similar to knapsack problem. so I tried to solve is that way. but the recursive version is giving tle so I tried to memoize it. it is giving correct answer on my local machine but it gives different answer when i submit it.
on the first test case it gives 90 on my local machine but when i submit it it gives wrong answer as 80.
5
2 4 5 4 10
40 30 20 10 40
I think you can do a brute force on this problem but be careful not to just loop over all triples of displays in $$$O(n^3)$$$ time, instead loop over the middle display and for each middle display, find the smallest cost of a display that is smaller to the left, and a display that is bigger to the right in $$$O(n^2)$$$ time.