In this problem I am having trouble understanding why we use concept like sliding window instead of trying all combinations+DP ? Especially the bold line in below paragraph which is from the Editorial.

However, the second sample test case shows that when n>m there is a possibility that purchasing items from the first m shops will take more time than skipping one or more shops. We'll need to calculate the amount of time for each possible combination of shops and choose the combination that takes the least amount of time. It's important that we can calculate all of these times optimally. If we were to create an array of each of the combinations and then use the loop above for each combination, we'd be forgetting that each combination is only different from the next by one shop.

Can you please explain proof for the statement ?

Pseudo codes from editorial here.

Thanks.

Hi, this is my first blog here. I've been trying to solve this question for a day.

Any idea or help greatly appreciated.

My solutions ->

DP soln, TLE

DP+Bitmask, WA

TC Input (To check if TLE)

TC Output

Actual time limit for this question is 1 second.

Thanks.