how to solve topcoder SRM 734 div 1 hard ?

could anyone explain how to solve topcoder SRM 734 div 1 hard ?
i have read the editorial but could not understand.
it has been mentioned in petr’s blog as very good dynamic programming problem.

what is the state of the dp ?
how to i move from one state to another ?

problem name: “TheRectangularcitydiv1”
problem link: TopCoder Statistics - Problem Statement
editorial link: Single Round Match 734 Editorials - Topcoder