AdditionalFile5574.zip

#5574. 「RMI 2025」Squirrel

标签: 传统 | 时间限制: 350 ms | 内存限制: 512 MiB |

注意事项

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

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

请在提交源代码前添加 #include "squirrel.h"。

题目描述

题目译自 Romanian Master of Informatics 2025 Day1 T3 「Squirrel」

一只松鼠发现了一个坚果仓库。仓库包含 $N$ 行房间，编号从 $0$ 到 $N-1$。索引为 $i$ 的行包含 $i+1$ 个房间，编号从 $0$ 到 $i$。位于第 $i$ 行第 $j$ 列的房间包含 $A_{i j}$ 个坚果。

在这 $\frac{N \times(N+1)}{2}$ 个房间中，数字 $A_{i j}$ 都是互不相同的，且取值在 $1$ 到 $\frac{N \times(N+1)}{2}$ 之间。形式上，仓库的形状是一个下三角矩阵（包含主对角线），其中每个元素代表坚果的数量。这个半矩阵中的数字是 $1$ 到 $\frac{N \times(N+1)}{2}$ 的排列，每个数字恰好出现一次。

例如，对于 $N=5$，仓库将有 $15$ 个房间，包含从 $1$ 到 $15$ 的数字。这样一个仓库的样例如下方的半矩阵所示：

松鼠沿着主对角线行走，在位于位置 $(i, i)$ 的每个房间，它会在以位置 $(i, i)$ 为右上角、位置 $(N-1, 0)$ 为左下角的矩形区域内选择一个房间，并吃掉那个房间里的坚果。在上面的例子中，当松鼠位于位置 $(1,1)$ 时，它可以选择吃掉 $8$ 个红色房间中任意一个房间里的坚果。在它走过主对角线上的所有房间并吃掉恰好 $N$ 个不同房间的坚果后，松鼠心满意足地离开了。

给定 $N$ 以及满足 $0 \leq i < N$ 和 $0 \leq j \leq i$ 的任意 $A_{i j}$，找出松鼠能吃到的最大坚果数量。

此外，对于访问的 $N$ 个房间中的每一个，找出松鼠在对应步骤吃掉的坚果数量。

实现细节

你必须实现以下函数：

void solve(int N, vector<vector<int>> A, long long& answer, vector<int>& solution)

• int N：仓库大小 / 行数
• vector<vector<int>> A：每个房间里的坚果数量（更准确地说，在满足 $0 \leq i < N$ 和 $0 \leq j \leq i$ 的 $A_{i, j}$ 中，你会找到位于第 $i$ 行第 $j$ 列的房间里的坚果数量）
• long long &answer：将包含松鼠走完对角线上所有 $N$ 个房间后能吃到的最大坚果数量。
• vector<int> &solution：一个向量，将包含松鼠在每一步吃掉的坚果数量。（更准确地说，满足 $0 \leq i < N$ 的 solution$_{i}$ 代表松鼠在房间 $(i, i)$ 时吃掉的坚果数量）

对于 $A$ 和 solution，索引都从 $0$ 开始，且 solution 向量的大小应正好为 $N$。

样例

输入

5
1
14 6
8 2 15
3 10 4 12
9 5 13 11 7

输出

64
14 10 15 12 13

数据范围与提示

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

• $1 \leq N \leq 2000$
• $1 \leq A_{i j} \leq \frac{N \times(N+1)}{2}$

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