4937. [Ceoi2016]popeala
#4937. [Ceoi2016]popeala
题目描述
你办了一场比赛，有n给人参加，只有一道题，有m个数据点，标号为1~m，每个测试点都有一个分数a[i]。现在所
有选手已经提交了程序并且测评完了，你知道每个人都能通过哪些测试点。你现在要安排捆绑测试的方式，把数据
点划分为若干个连续的区间，每个区间至少有一个测试点。每个区间只要有一个测试点错误就不会得分，如果所有
点都正确得分为所有测试点的分数的和。你的目的是最小化所有人的得分和。你需要对1<=i<=S，输出当把所有测
试点划分为i组时，最小的所有人分数和。
输入格式
第一行三个整数n,m,S
接下来一行m个整数，代表a[i]
接下来n行每行一个长度为m的01串，代表第i个人是否通过了第j个测试点
n<=50
m<=200000
S<=min(50,m)
a[i]<=10000,sigma a[i]*n<=2000000000
输出格式
S行，每行一个整数，代表当划分为i个捆绑测试点时所有人分数和的最小值
样例
样例输入
2 3 3
4 3 5
101
110
样例输出
0
8
16