初学者指南

首先编写一个程序来计算从一对输入和输出中得出的分数。通过提交你的解决方案，或者在本次比赛中通常会提供一个官方的用于计算分数的程序进行本地评估，你可以知道总分。尽管如此，自己编写一个分数计算器仍然有用，可以检查对问题规范的理解。而且，分数计算器的源代码经常可以用于解决该问题或调试你的解决方案。因此，编写一个分数计算器是值得的，除非它非常复杂。

问题陈述

你将获得一个为 $D$ 天的比赛日程安排。对于每个 $d=1,2,\ldots,D$，计算第 $d$ 天结束时的满意度。

输入

输入以标准输入的形式给出，先是问题 A 的输入，然后是问题 A 的输出。

$D$ $c_1$ $c_2$ $\cdots$ $c_{26}$ $s_{1,1}$ $s_{1,2}$ $\cdots$ $s_{1,26}$ $\vdots$ $s_{D,1}$ $s_{D,2}$ $\cdots$ $s_{D,26}$ $t_1$ $t_2$ $\vdots$ $t_D$

• 输入部分的约束条件和生成方法与问题 A 相同。
• 对于每个 $d$，$t_d$ 是满足 $1\leq t_d \leq 26$ 的整数，并且你的程序预计能够正确处理满足约束条件的任何值。

输出

设 $v_d$ 是第 $d$ 天结束时的满意度。以以下格式将 $D$ 个整数 $v_d$ 打印到标准输出：

$v_1$ $v_2$ $\vdots$ $v_D$

示例输入 1

5
86 90 69 51 2 96 71 47 88 34 45 46 89 34 31 38 97 84 41 80 14 4 50 83 7 82
19771 12979 18912 10432 10544 12928 13403 3047 10527 9740 8100 92 2856 14730 1396 15905 6534 4650 11469 3628 8433 2994 10899 16396 18355 11424
6674 17707 13855 16407 12232 2886 11908 1705 5000 1537 10440 10711 4917 10770 17272 15364 19277 18094 3929 3705 7169 6159 18683 15410 9092 4570
6878 4239 19925 1799 375 9563 3445 5658 19857 11401 6997 6498 19933 3848 2426 2146 19745 16880 17773 18359 3921 14172 16730 11157 5439 256
8633 15862 15303 10749 18499 7792 10317 5901 9395 11433 3514 3959 5202 19850 19469 9790 5653 784 18500 10552 17975 16615 7852 197 8471 7452
19855 17918 7990 10572 4333 438 9140 9104 12622 4985 12319 4028 19922 12132 16259 17476 2976 547 19195 19830 16285 4806 4471 9457 2864 2192
1
17
13
14
13

示例输出 1

18398
35037
51140
65837
79325

注意，这个示例是一个简单的用于检查问题规范的小例子。它不满足约束条件 $D=365$ 并且实际上从未给出作为一个测试用例。

下一步

我们可以按照第 1 天、第 2 天等的顺序构建一个解决方案（日程安排）。对于我们已经构建的每个部分解决方案，我们可以使用上述的分数计算器来计算好处（满意度）。因此，我们可以构建以下算法：对于每个 $d=1,2,\ldots,D$，我们选择在第 $d$ 天结束时最大化满意度的比赛类型。你可能已经遇到过这种“贪婪算法”在 ABC 等算法竞赛中。贪心算法可以保证多个问题的最优解，但不幸的是，对于这个问题它不能保证最优解。然而，即使它不能保证最优性，在许多情况下我们仍然可以得到一个合理的解决方案。让我们回到问题 A，并利用你刚刚实现的贪心算法来编写吧！

贪婪方法可以应用于各种问题，易于实现，并且与其他方法相比通常运行得相对较快。当我们需要处理大规模输入时，贪婪算法往往是最强大的方法。通过更改贪心选择标准（评估函数）、保留多个候选解而不仅仅关注一个最佳的部分解（束搜索），或者使用贪心算法的输出作为其他方法的初始解，我们可以进一步提高分数。有关更多信息，请参阅比赛后发布的解题报告。