#P18929. [2026多校联测]频道轮值
[2026多校联测]频道轮值
频道轮值
题目描述
气象台要对 个接收频道各做一次连续测试。测试只能使用预先允许的时段,切换频道也需要时间。管理员希望在这些限制下,尽量延长各频道的测试时间。
共有 个等长时段,编号为 ;频道编号为 。给定一个 行 列的表 ,其中 表示时段 可以用于频道 的测试, 表示不可以。同一个时段可以允许多个频道,也可以不允许任何频道。
你需要选择一个正整数 ,并为每个频道 安排一个长度恰好为 的连续测试段。测试段内的每个时段都必须允许该频道。每个频道恰好测试一次,各个测试段互不重叠,频道的测试顺序可以自行决定。
把测试段按开始时间排序。若相邻两段分别测试频道 ,则两段之间至少要留下 个空闲时段。这些时段不能安排其他频道的测试,但不要求它们允许频道 或 。第一个测试段之前、最后一个测试段之后,都不需要额外留出时段。允许 与 不同。
没有安排测试的时段可以空着。请你求出 的最大值。如果连 都无法安排,输出 。
输入格式
第一行两个整数 。
接下来 行,每行 个整数。第 行第 个整数为 。
接下来一行 个整数 。
接下来 行,每行 个整数。第 行第 个整数为 。
输出格式
输出一个整数,表示最大的 ;不存在正整数解时输出 。
样例 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 解释
当 时,可在时段 测试频道 ,空出时段 ,在时段 测试频道 。每段内都允许相应频道,切换间隔也符合要求。 时无法给两个频道都安排长度为 的测试段,因此答案为 。
样例 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 解释
所有时段都不允许频道 ,无法安排它的测试,因此输出 。
样例 3
见下发文件中的 channel/3.in 和 channel/3.ans。这是一组较大的样例,题面中不展开。
数据范围与子任务
对于所有测试数据,保证:,,,,,。
本题共有四个子任务,各组独立计分。通过某组全部测试点,才能得到该组分数。
| 子任务 | 分值 | 额外约束 |
|---|---|---|
| 1 | 20 | , |
| 2 | ||
| 3 | 所有 | |
| 4 | 40 | 无额外约束 |