For every "block" (rows between two horizontal cuts), maintain count of 1's for each column.

So if you had something like:

1 1 1 1
1 0 1 0
0 0 1 0
0 1 1 1

Let's say currently you're making cuts under rows 1 and 3 (1-based), so it'd be something like:

1 1 1 1    first block
--------------
1 0 1 0
0 0 1 0    second block
--------------
0 1 1 1    third block

Now maintain count of 1's for each block at each column:

1 1 1 1
--------------
1 0 2 0
--------------
0 1 1 1

You know that if in any block, any count is bigger than k, than this horizontal cut setup is impossible, so you can just try the next mask.

But in this case, let's say $$$k=2$$$. Now iterate through each column and each block and maintain one horizontal sum for each block, if at any index $$$i$$$ $$$\text{horizontal sum of some block} > k$$$, than you have to make a cut, and sum in each block becomes the i-th element in that block.

So in the first block and second block, sum of the first three elements will exceed k, so you will make a cut there and sum will reset ($$$sum[1] = 1, sum[2] = 2, sum[3] = 1)$$$.

1 1 | 1 1
----|----------
1 0 | 2 0
----|----------
0 1 | 1 1

Welp, hope that explanation wasn't terrible haha.

Go through the array column by column. If the group size exceeds k for any of the groups in a column, we draw a line before the column and update the size of each group.

Another way to understand greedy is to solve the 1-D problem; A = [1 1 0 0 1 ... etc]. In this case you will obviously keep going as far as possible until you need to make a cut. "As far as possible" means until your current sum exceeds K. Then extending this idea to the columns is easy.

Hey makes sense to me thank you for the reply :) care to explain what to do in each and every combination.

I don't understand a word of what you just said, but I'll try to elaborate a bit. If we have a subsequence with sum $$$S$$$ that starts at $$$l$$$ and ends at $$$r$$$, its contribution to the answer is $$$l (n - r + 1)$$$. That's because it is contained in $$$f(L, R)$$$ exactly if $$$L \le l$$$ and $$$r \le R$$$.

We can think of it like this. There are many different subsequences with left endpoint $$$l$$$ and right endpoint $$$r$$$, suppose the $$$i$$$-th of them has left endpoint $$$l_i$$$ and right endpoint $$$r_i$$$. Then the answer to the problem looks like

(Obviously, this sum is too large to calculate directly, it is just to help with thinking.)

Let's look at one particular $r$ and all the summands of the form $$$l_i (n - r + 1)$$$. That part of the sum above looks like

So, we are interested in the sum of left endpoints of all subsequences with weight $S$ that end at $$$r$$$.

This can be calculated through dynamic programming. As I stated above, define $$$\mathrm{dp}[i][j]$$$ as the sum of left endpoints of all subsequences with weight $$$j$$$ that end at $$$i$$$. Then we can calculate it for all $$$i$$$ like:

Thank you:)