A5883. 「CEOI2016」Popeala
编程题
省选/NOI-
知识点
题目描述
**译自 [CEOI2016](http://www.ceoi2016.ro/) Day2 T2「[Popeala](http://ceoi.inf.elte.hu/probarch/16/popeala-statement.pdf)」**
> 罗马尼亚语中的「popeală」一词起源于一篇罗马尼亚历史短篇小说 [*Alexandru Lăpuşneanul*](https://ro.wikipedia.org/wiki/Alexandru_L%C4%83pu%C8%99neanul_(nuvel%C4%83))，这篇小说中用 Moldavia 王子的口吻，用这个词的变体描述了他将对篡位者进行的报复行动。这个词最近在罗马尼亚程序竞赛中复活了，有点令人惊讶。它用来描述科学委员会用一些非正统并且（通常）非自愿的方式让选手生活更难的一切情况：十分严格的时间限制，不合法的输入数据，错误的题面，偷键盘或者其他诸如此类的外设。
>
> 这是有关「popeală」的一道题。
考虑一场有 $N$ 个选手参加的程序设计竞赛。比赛只有一道题，这道题有 $T$ 组测试数据。科学委员会想要把这些数据组成最多 $S$ 个子任务。
**子任务如何工作**：每组测试数据将会属于**恰好一个**子任务中。一个子任务可以包含任意数量的测试数据，但它不能为空。如果一个选手没有通过某个子任务中的**任一**测试数据，这个选手在这个子任务中将获得 $0$ 分。否则，这个子任务的得分将等于子任务内所有测试数据的得分之和。
这是程序设计竞赛中的通常实践，但问题是科学委员会想要在**比赛之后**做这件事。他们知道每一个选手正确解出了哪些测试点，它们想要把这些测试点组成子任务，以**最小化比赛中选手获得分数的和**。
具体来说，给你一个大小为 $T$ 的整数数组 $\texttt{Points[]}$。$\texttt{Points[i]}$ 是第 $i$ 组数据的得分。同样给你一个大小为 $N\times T$ 的二维数组 $\texttt{Results[][]}$。如果第 $i$ 个选手正确解决了第 $j$ 组测试数据，那么 $\texttt{Results[i][j]}$ 等于 $1$，否则等于 $0$。并且委员会决定所有的子任务将包含一些**连续的测试数据**。换句话说，如果测试数据 $X$ 和 $Y$ 将出现在同一子任务中，那么对于所有测试数据 $Z$，满足 $X\le Z\le Y$ 的测试数据同样必须属于这个子任务。
你需要帮助委员会。他们想知道，对于每个 $1\le K\le S$，如果恰好把测试数据分为 $K$ 个子任务的话，选手获得分数和的最小值是多少。
> 罗马尼亚语中的「popeală」一词起源于一篇罗马尼亚历史短篇小说 [*Alexandru Lăpuşneanul*](https://ro.wikipedia.org/wiki/Alexandru_L%C4%83pu%C8%99neanul_(nuvel%C4%83))，这篇小说中用 Moldavia 王子的口吻，用这个词的变体描述了他将对篡位者进行的报复行动。这个词最近在罗马尼亚程序竞赛中复活了，有点令人惊讶。它用来描述科学委员会用一些非正统并且（通常）非自愿的方式让选手生活更难的一切情况：十分严格的时间限制，不合法的输入数据，错误的题面，偷键盘或者其他诸如此类的外设。
>
> 这是有关「popeală」的一道题。
考虑一场有 $N$ 个选手参加的程序设计竞赛。比赛只有一道题，这道题有 $T$ 组测试数据。科学委员会想要把这些数据组成最多 $S$ 个子任务。
**子任务如何工作**：每组测试数据将会属于**恰好一个**子任务中。一个子任务可以包含任意数量的测试数据，但它不能为空。如果一个选手没有通过某个子任务中的**任一**测试数据，这个选手在这个子任务中将获得 $0$ 分。否则，这个子任务的得分将等于子任务内所有测试数据的得分之和。
这是程序设计竞赛中的通常实践，但问题是科学委员会想要在**比赛之后**做这件事。他们知道每一个选手正确解出了哪些测试点，它们想要把这些测试点组成子任务，以**最小化比赛中选手获得分数的和**。
具体来说，给你一个大小为 $T$ 的整数数组 $\texttt{Points[]}$。$\texttt{Points[i]}$ 是第 $i$ 组数据的得分。同样给你一个大小为 $N\times T$ 的二维数组 $\texttt{Results[][]}$。如果第 $i$ 个选手正确解决了第 $j$ 组测试数据，那么 $\texttt{Results[i][j]}$ 等于 $1$，否则等于 $0$。并且委员会决定所有的子任务将包含一些**连续的测试数据**。换句话说，如果测试数据 $X$ 和 $Y$ 将出现在同一子任务中，那么对于所有测试数据 $Z$，满足 $X\le Z\le Y$ 的测试数据同样必须属于这个子任务。
你需要帮助委员会。他们想知道，对于每个 $1\le K\le S$，如果恰好把测试数据分为 $K$ 个子任务的话，选手获得分数和的最小值是多少。
输入格式
第一行包含三个整数 $N,T,S$。
第二行包含 $T$ 个整数，表示数组 $\texttt{Points[]}$ 中的元素。
接下来 $N$ 行，每行一个长度为 $T$ 的 $01$ 串，表示二维数组 $\texttt{Results[][]}$ 中的元素。
第二行包含 $T$ 个整数，表示数组 $\texttt{Points[]}$ 中的元素。
接下来 $N$ 行，每行一个长度为 $T$ 的 $01$ 串，表示二维数组 $\texttt{Results[][]}$ 中的元素。
输出格式
输出 $S$ 行，第 $i$ 行包含一个整数，表示如果测试数据被分为 $i$ 个子任务的话选手得分之和的最小值。
输入输出样例
输入 #1
2 3 3 4 3 5 101 110
输出 #1
0 8 16
说明/提示
对于全部数据，$1\le T\le 2\times 10^4,1\le N\le 50,1\le S\le \min(50,T)$。
保证对于所有 $1\le i\le T$，都有 $1\le \texttt{Points[i]}\le 10^4$，且对于所有数据，$N\cdot(\texttt{Points[1]}+\texttt{Points[2]}+\ldots +\texttt{Points[T]})\le 2\times 10^9$。
- 对于其中 $8$ 分的数据，$T\le 40$；
- 对于另外 $9$ 分的数据，$40<T\le 500$；
- 对于另外 $9$ 分的数据，$500<T\le 4\times10^3$。
~~*你写过的任何代码都可能被用来让你拿到更低的分数。*（开个玩笑）~~
保证对于所有 $1\le i\le T$，都有 $1\le \texttt{Points[i]}\le 10^4$，且对于所有数据，$N\cdot(\texttt{Points[1]}+\texttt{Points[2]}+\ldots +\texttt{Points[T]})\le 2\times 10^9$。
- 对于其中 $8$ 分的数据，$T\le 40$；
- 对于另外 $9$ 分的数据，$40<T\le 500$；
- 对于另外 $9$ 分的数据，$500<T\le 4\times10^3$。
~~*你写过的任何代码都可能被用来让你拿到更低的分数。*（开个玩笑）~~