#CW59. 左右采撷(harvest)
左右采撷(harvest)
题目描述
花园中有 行、 列花朵。第 行第 列的花记作 ,它含有 单位花粉。另有 只蜜蜂,第 只蜜蜂的初始位置为 。所有蜜蜂使用同一个非负整数体力值 ,但每只蜜蜂可以独立选择一种采集方式:
- 左右采撷:只在第 行采集,并且采集列号 满足 的花;
- 上下采撷:只在第 列采集,并且采集行号 满足 的花。
每只蜜蜂只能选择其中一种方式,不能先横向采集再纵向采集,也不能把一次选择拆成多个区间。区间超出花园边界的部分直接忽略。
不同蜜蜂的采集范围可能重叠,但每朵花最多只能计入一次总花粉。也就是说,应先取所有被至少一只蜜蜂覆盖的花朵的并集,再把这些花的花粉量相加。
请问要使所有蜜蜂合计采集到至少 单位花粉,体力值 至少是多少。如果即使把每只蜜蜂的范围扩展到整个对应行或列,也无法收集到 单位花粉,则不存在合法的 。
输入格式
从 harvest.in 文件读入数据。
第一行输入 。接下来 行每行输入 个正整数 。接下来 行每行输入 。
输出格式
将结果输出到 harvest.out 文件。
输出满足条件的最小整数 ,无解时输出 Impossible。
样例 1 输入
3 4 2 20
1 2 3 4
5 6 7 8
9 10 11 12
2 2
3 4
样例 1 输出
1
样例 1 解释
时,第一只蜜蜂最多采集 单位,第二只蜜蜂最多采集 单位,合计 ; 时,第一只蜜蜂可横向覆盖第 行的第 列(),第二只蜜蜂可纵向覆盖第 列的第 行(),并集花粉量不少于 。
样例 2 输入
2 3 1 100
1 2 3
4 5 6
1 1
样例 2 输出
Impossible
数据范围
对于全部数据,满足 ,,,,。
本题采用子任务捆绑计分:一个子任务中的全部测试点均通过后,才能获得该子任务的分数。各子任务分数可以累加。
| 子任务 | 分值 | 测试点 | 附加条件 |
|---|---|---|---|
| 1 | 10 | , | |
| 2 | , | ||
| 3 | 20 | , | |
| 4 | |||
| 5 | 15 | 所有 | |
| 6 | 25 | 无特殊限制 |