追忆(recall)

追忆（recall）

题目背景

考虑到评测机性能差距，本题较官方赛事增加了 -5 秒的额外时限。

我常常追忆过去。

生命瞬间定格在脑海。我将背后的时间裁剪、折叠、蜷曲，揉捻成天上朵朵白云。

云朵之间亦有分别：积云厚重，而卷云飘渺。生命里震撼的场景掠过我的思绪便一生无法忘怀，而更为普通平常的记忆在时间的冲刷下只留下些许残骸。追忆宛如入梦，太过清楚则无法愉悦自己的幻想，过分模糊却又坠入虚无。只有薄雾间的山水，面纱下的女子，那恰到好处的朦胧，才能满足我对美的苛求。

追忆总在不经意间将我裹进泛黄的纸页里。分别又重聚的朋友，推倒又重建的街道，种种线索协助着我从一个具体的时刻出发沿时间的河逆流而上。曾经的日子无法重来，我只不过是一个过客。但我仍然渴望在每一次追忆之旅中留下闲暇时间，在一个场景前驻足，在岁月的朦胧里瞭望过去的自己，感受尽可能多的甜蜜。美好的时光曾流过我的身体，我便心满意足。

过去已经凝固，我带着回忆向前，只是时常疏于保管，回忆也在改变着各自的形态。这给我的追忆旅程带来些许挑战。

我该在哪里停留？我问我自己。

题目描述

我将自己的记忆整理成一个层层展开的结构。

共有 \(N\) 层记忆，第 \(i\) 层（\(1 \le i \le N\)）包含 \(i\) 个记忆片段，编号为 \((i,1),(i,2),\dots,(i,i)\)。
其中，第 \(i\) 层第 \(j\) 个记忆片段具有甜蜜程度 \(A_{i,j}\)。

所有记忆片段的甜蜜程度两两不同，并且恰好构成 \(1 \sim \frac{N(N+1)}{2}\) 的一个排列。

在一次追忆旅程中，我会沿着“主线记忆”依次前进，也就是依次经过：

\[(1,1),(2,2),\dots,(N,N) \]

当我来到主线记忆 \((i,i)\) 时，可以在一个指定区域内选择一个记忆片段停留。
具体来说，我可以选择任意一个满足以下条件的记忆片段 \((x,y)\)：

• \(i \le x \le N\)；
• \(1 \le y \le i\)。

换句话说，当位于 \((i,i)\) 时，我可以在一个“以当前主线记忆为右上角、以最底层最左侧记忆为左下角”的区域中，任选一个记忆片段停留。

整场追忆旅程中：

• 我会在这 \(N\) 个主线记忆处各停留一次；
• 每次停留所选的记忆片段必须互不相同；
• 每次停留都能获得该记忆片段对应的甜蜜程度。

现在，我想知道：

1. 在最优选择下，这次追忆旅程能够获得的最大甜蜜程度之和是多少；
2. 对于每一个主线记忆，分别应当停留在哪一个甜蜜程度的记忆片段上。

简要题意

给定一个大小为 \(N\) 的下三角矩阵 \(A\)，其中：

• 第 \(i\) 行有 \(i\) 个元素；
• 所有元素两两不同，且恰好是 \(1 \sim \frac{N(N+1)}{2}\) 的一个排列。

你需要从主对角线上的每个位置 \((i,i)\) 各进行一次选择。

对于第 \(i\) 次选择，你可以选取任意一个满足

• \(i \le x \le N\)；
• \(1 \le y \le i\)

的格子 \((x,y)\)。

要求：

• 共进行 \(N\) 次选择；
• 所有被选中的格子互不相同；
• 最大化所选格子中的权值总和。

你需要输出最大总和，以及一种对应的选择方案。

输入格式

第一行包含一个整数 \(N\)，表示记忆层数。

接下来共 \(N\) 行：

• 第 \(1\) 行包含 \(1\) 个整数，表示 \(A_{1,1}\)；
• 第 \(2\) 行包含 \(2\) 个整数，表示 \(A_{2,1}, A_{2,2}\)；
• ……
• 第 \(N\) 行包含 \(N\) 个整数，表示 \(A_{N,1}, A_{N,2}, \dots, A_{N,N}\)。

输出格式

第一行输出一个整数，表示最大甜蜜程度之和。

第二行输出 \(N\) 个整数，第 \(i\) 个整数表示当位于主线记忆 \((i,i)\) 时，所选择停留的记忆片段的甜蜜程度。

输入输出样例 #1

输入 #1

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

输出 #1

64
14 10 15 12 13

说明/提示

【样例解释】

一种最优方案为：

• 在 \((1,1)\) 时停留在甜蜜程度为 \(14\) 的记忆片段；
• 在 \((2,2)\) 时停留在甜蜜程度为 \(10\) 的记忆片段；
• 在 \((3,3)\) 时停留在甜蜜程度为 \(15\) 的记忆片段；
• 在 \((4,4)\) 时停留在甜蜜程度为 \(12\) 的记忆片段；
• 在 \((5,5)\) 时停留在甜蜜程度为 \(13\) 的记忆片段。

因此最大总和为：

\[14+10+15+12+13=64 \]

【数据范围】

• \(1 \le N \le 2000\)
• \(1 \le A_{i,j} \le \frac{N(N+1)}{2}\)

子任务	分值	限制
\(1\)	\(11\)	\(N \le 5\)
\(2\)	\(12\)	\(N \le 100\)
\(3\)	\(23\)	\(N \le 500\)
\(4\)	\(15\)	\(N \le 1000\)
\(5\)	\(13\)	\(N \le 1200\)
\(6\)	\(8\)	矩阵内容随机分配
\(7\)	\(18\)	无额外限制