I've been stuck on this problem for a while [(Lazy Cows USACO 2005 US Open Gold)](http://poj.org/problem?id=2430) . I was able to get the recurrence correct . But my naive approach ($\mathcal{O}(N^2 K)$) 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][j] , costH1[0][j])$↵
↵
$DP[i][0] = 0$↵
↵
My Submission : [Commented Code](https://gist.github.com/bhi5hmaraj/9e71d061325df12ca1087be0ee52325c)↵
↵
Can someone help me in optimising this recurrence relation. ↵
↵
### Update↵
↵
I would like to thank [user:send_nodes,2017-07-26] for helping me in [solving](http://mirror.codeforces.com/blog/entry/53438?#comment-375091) this problem .↵
↵
[AC CODE](https://gist.github.com/bhi5hmaraj/f66bd6dadf683b1dc7dfd4c83091f846)
↵
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][j] , costH1[0][j])$↵
↵
$DP[i][0] = 0$↵
↵
My Submission : [Commented Code](https://gist.github.com/bhi5hmaraj/9e71d061325df12ca1087be0ee52325c)↵
↵
Can someone help me in optimising this recurrence relation. ↵
↵
### Update↵
↵
I would like to thank [user:send_nodes,2017-07-26] for helping me in [solving](http://mirror.codeforces.com/blog/entry/53438?#comment-375091) this problem .↵
↵
[AC CODE](https://gist.github.com/bhi5hmaraj/f66bd6dadf683b1dc7dfd4c83091f846)
