← 返回题目列表

Codeforces · 1162/A

A. 再次分区限制

中文机器翻译题面 查看原题

您计划在街道上建造住房。街道上有 $$$n$$$ 地点可供您建造房屋。这些点从左到右标记为 $$$1$$$ 到 $$$n$$$。在每个地点,您都可以建造一座高度介于 $$$0$$$ 和 $$$h$$$ 之间的整数房屋。

在每个地点,如果房子的高度为 $$$a$$$,您将从中获得 $$$a^2$$$ 美元。

该城市有 $$$m$$$ 分区限制。第 $$$i$$$ 限制表示从 $$$l_i$$$ 点到 $$$r_i$$$(含)之间最高的房子必须最多为 $$$x_i$$$。

您想建造房屋来最大化您的利润。确定可能的最大利润。

输入

第一行包含三个整数 $$$n$$$、$$$h$$$ 和 $$$m$$$ ($$$1 \leq n,h,m \leq 50$$$) — 点的数量、最大高度和限制数量。

接下来的 $$$m$$$ 行包含三个整数 $$$l_i$$$、$$$r_i$$$ 和 $$$x_i$$$ ($$$1 \leq l_i \leq r_i \leq n$$$, $$$0 \leq x_i \leq h$$$) — $$$i$$$-th 限制以及该范围内的最大可能高度。

输出

打印一个整数,即您可以获得的最大利润。

示例

输入 #1

3 3 3
1 1 1
2 2 3
3 3 2

输出 #1

14

输入 #2

4 10 2
2 3 8
3 4 7

输出 #2

262

注意

在第一个示例中,有 $$$3$$$ 房屋,房屋的最大高度为 $$$3$$$,并且有 $$$3$$$ 限制。第一个限制是 $$$1$$$ 和 $$$1$$$ 之间最高的房子最多只能是 $$$1$$$。第二个限制是 $$$2$$$ 和 $$$2$$$ 之间最高的房子最多只能是 $$$3$$$。第三个限制是 $$$3$$$ 和 $$$3$$$ 之间最高的房子最多只能是 $$$2$$$。

在这种情况下,建造高度为 $$$[1, 3, 2]$$$ 的房屋是最佳的。这符合所有限制。本例中的总利润为 $$$1^2 + 3^2 + 2^2 = 14$$$。

在第二个示例中,有 $$$4$$$ 房屋,房屋的最大高度为 $$$10$$$,并且有 $$$2$$$ 限制。第一个限制是从 $$$2$$$ 到 $$$3$$$ 最高的房子必须最多为 $$$8$$$。第二个限制是从 $$$3$$$ 到 $$$4$$$ 最高的房子必须最多为 $$$7$$$。

在这种情况下,最好建造高度为 $$$[10, 8, 7, 7]$$$ 的房屋。我们获得的利润为 $$$10^2+8^2+7^2+7^2 = 262$$$。请注意,房屋 $$$3$$$ 有两个限制,并且必须满足这两个限制。另外,请注意,即使对房屋 $$$1$$$ 没有任何明确的限制,我们仍然必须将其高度限制为最多 $$$10$$$ ($$$h=10$$$)。