Official Analysis (Java)

Explanation

We solve this problem by brute forcing over all possible placements of the two fences. Note that we only need to consider fence positions at $x + 1$ and $y + 1$ for each cow's at $(x, y)$ because these are the only positions that affect the regions without passing through a cow. For each pair of fences, we count the number of cows in each of the four regions and update our maximum accordingly.

Implementation

Time Complexity: $\mathcal{O}(N^3)$

Copy
with open("balancing.in") as read:
	# max_pos won't be used
	cow_num, max_pos = [int(i) for i in read.readline().split()]

	x_vals = []
	y_vals = []
	v_fence = set()
	h_fence = set()
	for _ in range(cow_num):
		x, y = [int(i) for i in read.readline().split()]