Zoning Restrictions
Contest: Forethought Future Cup - Elimination Round
Difficulty rating: 2700
Tags: dp, flows, graphs

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.

Input format:
The first line contains three integers $$$n,h,m$$$ ($$$1 \leq n,h,m \leq 50$$$) — the number of spots, the maximum height, and the number of restrictions, respectively.

Each of the next $$$m$$$ lines contains four integers $$$l_i, r_i, x_i, c_i$$$ ($$$1 \leq l_i \leq r_i \leq n$$$, $$$0 \leq x_i \leq h$$$, $$$1 \leq c_i \leq 5\,000$$$).

Output format:
Print a single integer denoting the maximum profit you can make.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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$$$.

Example input:
3 3 3
1 1 1 1000
2 2 3 1000
3 3 2 1000

Example output:
14

Example input:
4 10 2
2 3 8 76
3 4 7 39

Example output:
289

Editorial:
There are two different solutions. The first is min cut. Let's build the graph as follows:
• There is a source and sink. The source side represents things that are "true", and sink side represents things that are "false"
• There are $$$O(n*h)$$$ nodes $$$(i,j)$$$ for ($$$1 \leq i \leq n, 0 \leq j \leq h$$$) where $$$i$$$ is a spot and $$$j$$$ is the height. Node $$$(i,j)$$$ represents the condition "the height at spot $$$i$$$ is at least $$$j$$$". We can connect $$$(i,j) -> (i,j-1)$$$ with infinite capacity (since "spot $$$i \geq j$$$" implies "spot $$$i \geq j-1$$$"). This is needed to make sure that for every $$$i$$$, $$$(i,j) -> (i,j+1)$$$ is cut exactly once for some j (though it might not be needed in practice). We draw an edge from $$$(i,j) -> (i,j+1)$$$ with capacity $$$(h^2-j^2)$$$, meaning if $$$(i,j)$$$ is on true and $$$(i,j+1)$$$ is false, then we incur that cost.
• There are $$$m$$$ nodes for each restriction, representing true if this restriction is violated and false otherwise. Call the k-th such node $$$k$$$. We connect $$$k$$$ to the sink with cost $$$c_k$$$. We connect $$$(a, x_k)$$$ for ($$$l_k \leq a \leq r_k$$$) to $$$k$$$ with infinite capacity (since house has height $$$\geq x_k$$$ in range implies restriction is violated).
To get the answer, run max flow, and then subtract answer from $$$h^2n$$$.
The max flow is bounded above by $$$h^2n$$$ and the number of nodes is $$$hn$$$ and edges is $$$hn+mn$$$, so by ford fulkerson, the worstcase running time is $$$O(h^2n(hn+mn))$$$, which is about $$$50^5$$$.
We can speed it up slightly by using some rmq structure to have $$$hn+m$$$ edges rather than $$$hn+mn$$$ edges, but this optimization isn't necessary.
The second approach is dp. Let $$$dp[i][j][k]$$$ be the max profit given we are only considering buildings $$$i..j$$$ and the heights are at most $$$k$$$. To compute this, let's iterate through some middle point $$$f$$$ between $$$i$$$ and $$$j$$$ as the tallest building and fix its height as $$$x$$$. We can compute which restrictions lie entirely in the interval that we violate and add the profit to our sum. Now, this splits into two problems $$$dp[i][f-1][x]$$$ and $$$dp[f+1][j][x]$$$, and the main observation is that these problems are now independent.