直方图 - المسألة

考虑一个直方图，它由 $N$ 个底边平行于地面且连续排列的矩形组成。每个矩形的宽度均为 1，从左往右第 $i$ ($1 \le i \le N$) 个矩形的高度为整数 $H_i$。

下图展示了一个直方图的示例。

我们希望在这个直方图内部选取至多 $K$ 个矩形，使得这些矩形的底边平行于地面，且它们互不重叠（不共享顶点或边），同时每个矩形的边长均为整数。我们的目标是使这些矩形的面积之和最大。将该最大值记为 $f(K)$。

请编写一个程序来计算 $f(1), f(2), f(3)$。

你需要实现以下函数：

vector<long long> max_area(vector<int> H)

该函数仅会被调用一次。
作为参数传入的整数数组 $H$ 的大小为 $N$。数组的每个元素 $H[i]$ 表示从左往右第 $i+1$ 个矩形的高度 $H_{i+1}$ ($0 \le i \le N-1$)。
该函数必须返回一个大小在 1 到 3 之间的数组 $A$。$A[i]$ 应存储 $f(i+1)$ 的值 ($0 \le i < |A|$)。请注意，评分标准会根据数组 $A$ 的大小而有所不同。

提交的源代码中不得包含任何输入输出函数。

(10分)
- $H_i \le H_{i+1}$ ($1 \le i \le N-1$)
- 若 $|A| = 3$ 且 $f(1), f(2), f(3)$ 均正确，则获得 10 分。
(3分)
- $N \le 500$
- 若 $|A| = 3$ 且 $f(1), f(2), f(3)$ 均正确，则获得 3 分。
(15分)
- $N \le 5\,000$
- 若 $|A| = 2$ 且 $f(1), f(2)$ 均正确，则获得 3 分。
- 若 $|A| = 3$ 且 $f(1), f(2), f(3)$ 均正确，则获得 15 分。
(27分)
- $N \le 200\,000$
- 若 $|A| = 2$ 且 $f(1), f(2)$ 均正确，则获得 7 分。
- 若 $|A| = 3$ 且 $f(1), f(2), f(3)$ 均正确，则获得 27 分。
(45分)
- 无额外限制。
- 若 $|A| = 1$ 且 $f(1)$ 正确，则获得 1 分。
- 若 $|A| = 2$ 且 $f(1), f(2)$ 均正确，则获得 15 分。
- 若 $|A| = 3$ 且 $f(1), f(2), f(3)$ 均正确，则获得 45 分。

设 max_area 函数返回的数组为 $A$。

如果 $A$ 的大小不在 1 到 3 之间，则得 0 分。

根据子任务的评分标准，请注意，如果 $f(1), \dots, f(|A|)$ 中有任何一个值不正确，则得 0 分。

只有当 $f(1), \dots, f(|A|)$ 的值全部正确时，才能根据各子任务的评分标准获得相应分数。

上述标准中，“$f(i)$ 正确”是指 $A$ 的大小至少为 $i$，且 $A[i-1]$ 的值等于 $f(i)$。

请注意，每个子任务的得分是该子任务所有测试数据得分中的最小值。

考虑 $N = 7, H = [3, 2, 1, 2, 1, 4, 3]$ 的情况。评测程序调用：
```
max_area([3, 2, 1, 2, 1, 4, 3]) = [7, 11, 13]
```
下图展示了对于 $K=1, 2, 3$ 时面积之和最大的情况之一。

如果 max_area 函数返回 [7, 11]，则 $f(1)$ 和 $f(2)$ 正确，可以获得相应子任务的得分。如果 max_area 函数返回 [7, 12, 13]，请注意，尽管 $f(1)$ 和 $f(3)$ 正确，但由于 $f(2)$ 错误，得 0 分。如果 max_area 函数返回 [7, 11, 14]，请注意，尽管 $f(1)$ 和 $f(2)$ 正确，但由于 $f(3)$ 错误，得 0 分。该示例满足子任务 2, 3, 4, 5 的条件。
考虑 $N = 7, H = [1, 2, 3, 4, 5, 6, 7]$ 的情况。评测程序调用：
```
max_area([1, 2, 3, 4, 5, 6, 7]) = [16, 21, 24]
```
该示例满足所有子任务的条件。
考虑 $N = 5, H = [1, 3, 4, 3, 1]$ 的情况。评测程序调用：
```
max_area([1, 3, 4, 3, 1]) = [9, 11, 12]
```
该示例满足子任务 2, 3, 4, 5 的条件。

N
H_1 H_2 ... H_N

A[0]
A[1]
...
A[|A|-1]

请注意，样例评测程序可能与实际评测时使用的评测程序不同。

QOJ.ac