题目背景

请使用 C++17 或 C++20 提交本题

你需要在程序开头加入如下代码：

#include <vector>
std::vector<long long> max_area(std::vector<int> H);

题目译自 2022년도 국제정보올림피아드 대표학생 선발고사 - 1차 선발고사 T3「 히스토그램」

题目描述

有一个由 $N$ 个底边平行于地面的矩形连续排列而成的直方图。每个矩形的宽度都是 $1$，并且从左到右第 $i (1 \leq i \leq N)$ 个矩形的高度为整数 $H_{i}$。

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

在这个直方图中，我们希望找到不超过 $K$ 个矩形，这些矩形的底边平行于地面，且除了顶点和边之外的区域不重叠，并且每个边的长度都是整数，使得这些矩形的面积之和最大。这个值记为 $f(K)$。 请编写一个程序来计算 $f(1), f(2), f(3)$。

你需要实现以下函数：

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

• 该函数只会被调用一次。
• 参数中给定的整数数组 $\texttt{H}$ 的大小为 $N$。数组的每个元素 $\texttt{H[i]} (0 \leq i \leq N-1)$ 表示从左到右第 $i+1$ 个矩形的高度 $H_{i+1}$。
• 该函数返回一个大小为 $1 \sim 3$ 的数组 $\texttt{A}$。$\texttt{A[i]} (0 \leq i<|\texttt{A}|)$ 中应存储 $f(i+1)$ 的值。请注意，数组 $\texttt{A}$ 的大小会影响评分标准。

注意，提交的代码中不应包含任何输入输出操作。

输入格式

示例评测程序按以下格式读取输入：

• 第 $1$ 行：$N$
• 第 $2$ 行：$H_{1}\,H_{2}\,\cdots H_{N}$

输出格式

示例评测程序按以下格式输出：

• 第 $1+i (0 \leq i<|\texttt{A}|)$ 行：max_area 函数返回的数组 $\texttt{A}$ 中 $\texttt{A}[i]$ 的值。

7
3 2 1 2 1 4 3

7
11
13

7
1 2 3 4 5 6 7

16
21
24

5
1 3 4 3 1

9
11
12

提示

评分标准

假设 max_area 函数返回的数组为 $\texttt{A}$。

如果 $\texttt{A}$ 的大小不是 $1$ 到 $3$ 之间，则得 $0$ 分。

根据子任务的标准，如果 $f(1), \cdots, f(|\texttt{A}|)$ 中有任何一个值不正确，则得 $0$ 分。

如果 $f(1), \cdots, f(|\texttt{A}|)$ 的值都正确，则根据子任务的评分标准得分。

在上述标准中，$f(i)$ 正确意味着 $\texttt{A}$ 的大小至少为 $i$ 并且 $\texttt{A}[i-1]$ 的值等于 $f(i)$。

每个子任务的分数是子任务所有数据的最小分数。

样例解释 #1

考虑 $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$ 的条件。

样例解释 #2

考虑 $N=7, H=[1,2,3,4,5,6,7]$ 的情况。

评测程序将调用如下函数：

max_area([1,2,3,4,5,6,7])=[16,21,24]

这个样例满足所有子任务的条件。

样例解释 #3

考虑 $N=5, H=[1,3,4,3,1]$ 的情况。

评测程序将调用如下函数：

max_area([1,3,4,3,1])=[9,11,12]

这个样例满足子任务 $2,3,4,5$ 的条件。

数据范围

对于所有输入数据，满足：

• $1 \leq N \leq 5\cdot 10^5$
• $1 \leq H_{i} \leq 5\cdot 10^5 (1 \leq i \leq N)$

详细子任务附加限制及分值如下表所示。

子任务	分值	约束
$1$	$10$	$H_{i} \leq H_{i+1} (1 \leq i \leq N-1)$
$2$	$3$	$N \leq 500$
$3$	$15$	$N \leq 5000$
$4$	$27$	$N \leq 2\cdot 10^5$
$5$	$45$	无附加限制