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

*costH*1[*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*.*costH*2[*i*][*j*] stores minimum area covered using 2 horizontal rectangles . If it can be covered with a single rectangle then its*INF*.*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][*j*], *costH*1[0][*j*])

*DP*[*i*][0] = 0

My Submission : Commented Code

Can someone help me in optimising this recurrence relation.

### Update

I would like to thank send_nodes for helping me in solving this problem .