#P18929. [2026多校联测]频道轮值

[2026多校联测]频道轮值

频道轮值

题目描述

气象台要对 kk 个接收频道各做一次连续测试。测试只能使用预先允许的时段,切换频道也需要时间。管理员希望在这些限制下,尽量延长各频道的测试时间。

共有 nn 个等长时段,编号为 1,2,…,n1,2,\ldots,n;频道编号为 1,2,…,k1,2,\ldots,k。给定一个 nn 行 kk 列的表 aa,其中 ai,c=1a_{i,c}=1 表示时段 ii 可以用于频道 cc 的测试,ai,c=0a_{i,c}=0 表示不可以。同一个时段可以允许多个频道,也可以不允许任何频道。

你需要选择一个正整数 xx,并为每个频道 cc 安排一个长度恰好为 xwcxw_c 的连续测试段。测试段内的每个时段都必须允许该频道。每个频道恰好测试一次,各个测试段互不重叠,频道的测试顺序可以自行决定。

把测试段按开始时间排序。若相邻两段分别测试频道 u,vu,v,则两段之间至少要留下 gu,vg_{u,v} 个空闲时段。这些时段不能安排其他频道的测试,但不要求它们允许频道 uu 或 vv。第一个测试段之前、最后一个测试段之后,都不需要额外留出时段。允许 gu,vg_{u,v} 与 gv,ug_{v,u} 不同。

没有安排测试的时段可以空着。请你求出 xx 的最大值。如果连 x=1x=1 都无法安排,输出 00。

输入格式

第一行两个整数 n,kn,k。

接下来 nn 行,每行 kk 个整数。第 ii 行第 cc 个整数为 ai,ca_{i,c}。

接下来一行 kk 个整数 w1,w2,…,wkw_1,w_2,\ldots,w_k。

接下来 kk 行,每行 kk 个整数。第 uu 行第 vv 个整数为 gu,vg_{u,v}。

输出格式

输出一个整数,表示最大的 xx;不存在正整数解时输出 00。

样例 1 输入

8 2
1 0
1 1
0 1
1 1
1 0
1 1
0 1
1 1
1 1
0 1
2 0

样例 1 输出

2

样例 1 解释

当 x=2x=2 时,可在时段 1,21,2 测试频道 11,空出时段 3,4,53,4,5,在时段 6,76,7 测试频道 22。每段内都允许相应频道,切换间隔也符合要求。x=3x=3 时无法给两个频道都安排长度为 33 的测试段,因此答案为 22。

样例 2 输入

6 3
1 1 0
1 1 0
1 1 0
1 1 0
1 1 0
1 1 0
1 1 1
0 0 0
0 0 0
0 0 0

样例 2 输出

0

样例 2 解释

所有时段都不允许频道 33,无法安排它的测试,因此输出 00。

样例 3

见下发文件中的 channel/3.in 和 channel/3.ans。这是一组较大的样例,题面中不展开。

数据范围与子任务

对于所有测试数据,保证:1≤n≤1000001\le n\le100000,1≤k≤141\le k\le14,ai,c∈{0,1}a_{i,c}\in\{0,1\},1≤wc≤100001\le w_c\le10000,0≤gu,v≤n0\le g_{u,v}\le n,gu,u=0g_{u,u}=0。

本题共有四个子任务,各组独立计分。通过某组全部测试点,才能得到该组分数。

子任务 分值 额外约束
1 20 n≤18n\le18,k≤4k\le4
2 k≤3k\le3
3 所有 gu,v=0g_{u,v}=0
4 40 无额外约束