CF1146G Zoning Restrictions

You are planning to build housing on a street. There are $ n $ spots available on the street on which you can build a house. The spots are labeled from $ 1 $ to $ n $ from left to right. In each spot, you can build a house with an integer height between $ 0 $ and $ h $ . In each spot, if a house has height $ a $ , you can gain $ a^2 $ dollars from it. The city has $ m $ zoning restrictions though. The $ i $ -th restriction says that if the tallest house from spots $ l_i $ to $ r_i $ is strictly more than $ x_i $ , you must pay a fine of $ c_i $ . You would like to build houses to maximize your profit (sum of dollars gained minus fines). Determine the maximum profit possible.

N/A

N/A

In the first example, it's optimal to build houses with heights $ [1, 3, 2] $ . We get a gain of $ 1^2+3^2+2^2 = 14 $ . We don't violate any restrictions, so there are no fees, so the total profit is $ 14 - 0 = 14 $ . In the second example, it's optimal to build houses with heights $ [10, 8, 8, 10] $ . We get a gain of $ 10^2+8^2+8^2+10^2 = 328 $ , and we violate the second restriction for a fee of $ 39 $ , thus the total profit is $ 328-39 = 289 $ . Note that even though there isn't a restriction on building $ 1 $ , we must still limit its height to be at most $ 10 $ .