Hello,

I'm confused how to come up with a solution for 738B - Прожекторы. A naive approach should take nearly O(N^4), but the correct approach is only O(N^2).

How to formulate the correct algorith?

Please help me fill the gaps in this approach:

1 — Read all inputs, and in the same time fill values for "UP" & "LEFT". O(N^2) 2 — After reading, run a nested loop over the grid, and sum values for "Down" & "RIGHT". O(N^2)

What is the formula to sum the values?

I can only imagine counting the empty cells with '0' in each row and column, and then when one encounters an occupied cell with "1" is to subtract somehow depending on the position of this one.

I just can't put it all together into a working solution.

Thanks in advance~