This problem can be solved with Dynamic Programming. Let's define DP[i][j] is the maximum points we can collect from row 1 to i, if we select the cells from jth to (j + k - 1)th for ith row. Now, as we can't make any jump of length more than l, so if we want to take these cells, we have to make a jump from a cell of (i - 1)th row, where the distance is less or equal to l. So we can see that,

DP[i][j] = max(DP[i - 1][x]) (here, j - l - k + 1 ≤ x ≤ j + k + l - 1) + sum(points[i][j] + . . . + points[i][j + k - 1]).

So, the final answer will be the maximum among all the DP[i] array. Time complexity O(nm2).

We can pass the time limit of easy version by this solution. But, if we want to solve this problem with O(nm) complexity, we have to use any data structure to maintain the maximum of DP[i - 1][x] efficiently. We can use a deque here. To maintain the maximum with deque, we will use the sliding window technique. You can find a good tutorial about this technique here and here.

Statistics

57% Solution Ratio
Riaz_BSMRSTUEarliest, Aug '20
EgorKulikovFastest, 0.1s
serotoninLightest, 8.3 MB
serotoninShortest, 984B
Toph uses cookies. By continuing you agree to our Cookie Policy.