P15830 [JOI Open 2015] 染色瓷砖 / Colored Tiles

2018 年，国际信息学奥林匹克竞赛（IOI）将在日本举办。为了庆祝这一盛事，IOI 组委会计划制作一件“略显奇特设计”的艺术品，并用它来装饰比赛场地。组委会委托 JOI（Just Odd Inventions）有限公司进行设计。JOI 的设计师们提出了以下方案： - 艺术品将制作在一个 $H \times W$ 的矩形网格板上。我们将用 $N$ 个瓷砖铺满整个网格板。瓷砖之间不能重叠。 - 第 $i$ 个（$1 \leq i \leq N$）瓷砖的尺寸要么是 $1 \times 1$，要么是 $1 \times 2$。瓷砖 $i$ 的颜色为 $C_i$。 - 我们可以旋转 $1 \times 2$ 的瓷砖，将其作为 $2 \times 1$ 的瓷砖使用。 此外，他们还提出了艺术品所用瓷砖的种类。然而，作为设计中最关键的部分，他们并未提出如何在网格板上铺设瓷砖。由于 JOI 提出的设计总是很美观，组委会决定采纳 JOI 关于瓷砖种类的方案。组委会现在需要思考如何在网格板上铺设瓷砖。他们决定以最大化设计的**美观度**为目标来铺设瓷砖。 设计的美观度计算方式如下： - 对于网格中每一条被颜色为 $j$ 和颜色为 $k$ 的两个瓷砖共同占据的单元格边，该边的得分为 $A_{j,k}$。 - 设计的美观度即为网格板上所有单元格边的得分总和。 如果两块 $1 \times 2$ 的瓷砖共享了相邻两个单元格的边，这两条边的得分需要分别计算。 你需要计算出一个能使美观度尽可能大的瓷砖铺设方案。 ### 任务 给定网格板的大小、每个瓷砖的尺寸和颜色，以及美观度的计算方式，请确定一个能使美观度尽可能大的瓷砖铺设方案。

共有五个子任务。每个子任务对应一个公开的输入数据文件。每个输入数据文件的格式如下。 - 输入的第一行包含四个以空格分隔的整数 $H, W, K, N$。这表示矩形网格板由 $H \times W$ 个单元格组成，瓷砖共有 $K$ 种颜色，设计中将使用 $N$ 块瓷砖。 - 接下来的 $N$ 行中，第 $i$ 行（$1 \leq i \leq N$）包含两个以空格分隔的整数 $S_i, C_i$。这表示瓷砖 $i$ 的尺寸为 $1 \times S_i$，颜色为 $C_i$。 - 接下来的 $K$ 行中，第 $j$ 行（$1 \leq j \leq K$）包含 $K$ 个以空格分隔的整数 $A_{j,1}, A_{j,2}, \dots, A_{j,K}$。这表示当颜色为 $j$ 和颜色为 $k$ 的两块瓷砖共享一条边时，该边的得分为 $A_{j,k}$。

你需要为每个输入数据文件提交一个对应的输出数据文件。输出数据文件应由 $N$ 行组成。第 $i$ 行（$1 \leq i \leq N$）按以下格式描述瓷砖 $i$ 的放置方式。 - 当 $S_i = 1$ 时，第 $i$ 行应包含两个以空格分隔的整数 $A_i, B_i$。这表示瓷砖 $i$ 被放置在从上往下数第 $A_i$ 行、从左往右数第 $B_i$ 列的单元格上。 - 当 $S_i = 2$ 时，第 $i$ 行应包含四个以空格分隔的整数 $A_i, B_i, C_i, D_i$。这表示瓷砖 $i$ 被放置在网格板上，覆盖了从上往下数第 $A_i$ 行、从左往右数第 $B_i$ 列的单元格，以及从上往下数第 $C_i$ 行、从左往右数第 $D_i$ 列的单元格。

### 样例 1 解释 在此样例输入中，设计用的网格板大小为 $3 \times 2$，共使用 4 块瓷砖。每块瓷砖的颜色和尺寸如下： | 编号 | 颜色 | 尺寸 | |------|------|---------| | 1 | 1 | $1 \times 1$ | | 2 | 2 | $1 \times 2$ | | 3 | 3 | $1 \times 1$ | | 4 | 1 | $1 \times 2$ | 因此，有一块颜色为 1 的 $1 \times 1$ 瓷砖，一块颜色为 2 的 $1 \times 2$ 瓷砖，一块颜色为 3 的 $1 \times 1$ 瓷砖，以及一块颜色为 1 的 $1 \times 2$ 瓷砖。 我们按照以下方式铺设瓷砖。图中的数字表示瓷砖的编号。 :::align{center}  ::: 设计的美观度计算如下，最终美观度为 26。 - 由于颜色为 2 的瓷砖 2 与颜色为 1 的瓷砖 4 共享一条边，得到得分 7。 - 由于颜色为 2 的瓷砖 2 与颜色为 1 的瓷砖 1 共享一条边，得到得分 7。 - 由于颜色为 1 的瓷砖 4 与颜色为 1 的瓷砖 1 共享一条边，得到得分 2。 - 由于颜色为 1 的瓷砖 4 与颜色为 3 的瓷砖 3 共享一条边，得到得分 5。 - 由于颜色为 1 的瓷砖 1 与颜色为 3 的瓷砖 3 共享一条边，得到得分 5。 ### 约束条件 所有输入数据满足以下条件。 - $1 \leq H \leq 100$。 - $1 \leq W \leq 100$。 - $1 \leq K \leq 100$。 - $1 \leq N \leq 10\,000$。 - $1 \leq S_i \leq 2$（$1 \leq i \leq N$）。 - $1 \leq C_i \leq K$（$1 \leq i \leq N$）。 - $H \times W = S_1 + S_2 + \dots + S_N$。 - $0 \leq A_{j,k} \leq 1000$（$1 \leq j \leq K, 1 \leq k \leq K$）。 - $A_{j,k} = A_{k,j}$（$1 \leq j \leq K, 1 \leq k \leq K$）。 ### 子任务 对于每个子任务，$H$、$W$、$K$、$N$ 的值如下表所示。关于 $X$ 和 $Y$ 的具体含义，请参见评分细则。 | 子任务 | $H$ | $W$ | $K$ | $N$ | $X$ | $Y$ | | :----: | :-: | :-: | :-: | :--: | :--------: | :--------: | | 1 | 7 | 24 | 3 | 168 | 124 000 | 130 000 | | 2 | 50 | 50 | 80 | 1800 | 3 260 000 | 3 850 000 | | 3 | 100 | 100 | 100 | 7200 | 7 420 000 | 9 220 000 | | 4 | 100 | 100 | 100 | 7000 | 7 150 000 | 9 000 000 | | 5 | 100 | 100 | 100 | 5200 | 11 700 000| 13 850 000| ### 评分细则 这是一个**提交答案**任务。共有五个子任务，每个子任务包含一个输入数据文件。你需要为每个子任务提交一个对应的输出数据文件。每个子任务的得分计算方式如下： - 如果瓷砖的铺设方式不满足输出文件的格式要求，得分为 0。 - 如果瓷砖的铺设方式满足输出文件的格式要求，则根据 $X$ 和 $Y$ 的值按下述方式计算得分。设 $B$ 为该铺设方案的设计美观度。 - 如果 $B < X$，得分为 0。 - 如果 $X \leq B < Y$，得分为 $\left\lfloor 1 + 19 \times \left( \frac{B - X}{Y - X} \right)^2 \right\rfloor$。其中 $\lfloor x \rfloor$ 表示不超过 $x$ 的最大整数。 - 如果 $Y \leq B$，得分为 20。 翻译由 DeepSeek V3.2 完成