Editorial for COCI '21 Contest 6 #2 Zemljište
Submitting an official solution before solving the problem yourself is a bannable offence.
Without loss of generality, assume that
Let's fix the first and last row of the plot of land to be chosen. Now the goal is to determine the best left and right end columns of the plot of land. Since the rows are already fixed, when choosing columns we'll take only the cells between the two end rows. Therefore, using prefix sums we can calculate for each column the sum of all cells in that column which are between the two rows. Then the problem becomes the following: given a sequence of numbers determine which interval has sum closest to the numbers
This problem can be solved using the two pointers method. We'll keep track of two pointers (indices in the array)
Comments