AdditionalFile4274.zip

#4274. 「KTSC 2022 R1」直方图

标签: 传统 | 时间限制: 4000 ms | 内存限制: 1024 MiB |

注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 17 及以上）

请在提交源代码前添加 #include "histogram.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$ 到 $3$ 的数组 $\texttt{A}$。$\texttt{A[i]}$ $(0 \leq i<|\texttt{A}|)$ 中应存储 $f(i+1)$ 的值。请注意，数组 $\texttt{A}$ 的大小会影响评分标准。

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

样例 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$	无附加限制

评分标准

在 LibreOJ 上，我们只会对 $f(1),f(2),f(3)$ 均正确的解决方案评分

假设 max_area 函数返回的数组为 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$
• 第 $2$ 行：$H_{1}\,H_{2}\,\cdots H_{N}$

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

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

示例评测程序可能与实际评测程序不同。