I've been stuck on this problem for a while (Lazy Cows USACO 2005 US Open Gold) . I was able to get the recurrence correct . But my naive approach ( ) TLEs .

First I compressed the positions by sorting them based on their column and breaking ties using the row number

Then I pre-processed 3 arrays

1. costH1[i][j] stores minimum area covered using a single horizontal rectangle , from i^th smallest position to j^th . If it's not possible (cows are not entirely up or entirely down) then its INF.

2. costH2[i][j] stores minimum area covered using 2 horizontal rectangles . If it can be covered with a single rectangle then its INF.

3. costV[i][j] stores minimum area covered using a single vertical rectangle . To be more precise , its a rectangle with top left coordinate at (1 , coordinate[i]) and bottom right at (2 , coordinate[j])

Using these 3 arrays

DP[i][j] stores the minimum area covered by i rectangles for a prefix area till j^th column.

Base Case

DP[0][j] = INF

DP[1][j] = min(costV[0][i], costH1[0][i])

DP[i][0] = 0

My Submission : Commented Code

Can someone help me in optimising this recurrence relation.