Zoning Restrictions Again
Contest: Codeforces Round 557 (Div. 2) [based on Forethought Future Cup - Final Round]
Difficulty rating: 800
Tags: implementation

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 will gain $$$a^2$$$ dollars from it.

The city has $$$m$$$ zoning restrictions. The $$$i$$$-th restriction says that the tallest house from spots $$$l_i$$$ to $$$r_i$$$ (inclusive) must be at most $$$x_i$$$.

You would like to build houses to maximize your profit. Determine the maximum profit possible.

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

Each of the next $$$m$$$ lines contains three integers $$$l_i$$$, $$$r_i$$$, and $$$x_i$$$ ($$$1 \leq l_i \leq r_i \leq n$$$, $$$0 \leq x_i \leq h$$$) — left and right limits (inclusive) of the $$$i$$$-th restriction and the maximum possible height in that range.

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

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

Note:
In the first example, there are $$$3$$$ houses, the maximum height of a house is $$$3$$$, and there are $$$3$$$ restrictions. The first restriction says the tallest house between $$$1$$$ and $$$1$$$ must be at most $$$1$$$. The second restriction says the tallest house between $$$2$$$ and $$$2$$$ must be at most $$$3$$$. The third restriction says the tallest house between $$$3$$$ and $$$3$$$ must be at most $$$2$$$.

In this case, it is optimal to build houses with heights $$$[1, 3, 2]$$$. This fits within all the restrictions. The total profit in this case is $$$1^2 + 3^2 + 2^2 = 14$$$.

In the second example, there are $$$4$$$ houses, the maximum height of a house is $$$10$$$, and there are $$$2$$$ restrictions. The first restriction says the tallest house from $$$2$$$ to $$$3$$$ must be at most $$$8$$$. The second restriction says the tallest house from $$$3$$$ to $$$4$$$ must be at most $$$7$$$.

In this case, it's optimal to build houses with heights $$$[10, 8, 7, 7]$$$. We get a profit of $$$10^2+8^2+7^2+7^2 = 262$$$. Note that there are two restrictions on house $$$3$$$ and both of them must be satisfied. Also, note that even though there isn't any explicit restrictions on house $$$1$$$, we must still limit its height to be at most $$$10$$$ ($$$h=10$$$).

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

Example output:
14

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

Example output:
262

Editorial:
This problem can be done by processing the restrictions one by one. Let's keep an array $$$a$$$ of length $$$n$$$, where the $$$i$$$-th value in this array represents the maximum possible height for house $$$i$$$.
Initially, we have processed no restrictions, so we fill $$$a_i = h$$$ for all $$$i$$$.
For a restriction $$$k$$$, we can loop through the elements $$$j$$$ between $$$l_k$$$ and $$$r_k$$$ and update $$$a_j = \min(a_j, x_k)$$$. This is because the new house must be at most height $$$x_k$$$, and we know previously it had to be at most $$$a_j$$$, so we take the min of the two.
After processing all restrictions, we can greedily choose the height of the $$$i$$$-th house to be $$$a_i$$$. The answer is the sum of $$$a_i^2$$$ for all $$$i$$$.
The time complexity for processing one restriction is $$$O(n)$$$, so the total time complexity is $$$O(nm)$$$.