#P17872. [Ontak2019]WAT
[Ontak2019]WAT
— 漏斗浇花
花园有 行、 列。行编号为 ,列编号为 。雨水可能从第 行的任意一列出现,通常沿所在列向下流动,直到底部第 行。
你有 个可选漏斗。第 个漏斗安装在第 行,覆盖第 至第 列,出水口在第 列,重量为 。若安装这个漏斗,进入这一行且列坐标位于 的水滴都会被引到下一行的第 列;其他列的水滴保持原列坐标。不安装时,这一行的水滴全部竖直下落。
选择一些漏斗,使从任意起始列落下的水最终都到达底部同一个格子。求所选漏斗的最小总重量。
输入格式
第一行两个整数 。
接下来 行,第 行四个整数 ,描述第 个漏斗。顺序就是从上到下的行顺序。
输出格式
输出一个整数,表示最小总重量。若无法将所有水汇集到一个格子,输出 -1。
数据范围及原文说明
,,。
原 PDF 将最后一个不等号印为 ,但样例明确含 ,这里按允许覆盖最右列理解。原 PDF 未给出重量 的数值上限;重量按非负量理解,标程使用 64 位整数存储费用。未凭空补写原题没有的上限。
| 子任务 | 漏斗数上限 | 分值 |
|---|---|---|
| 1 | 24 | 9 |
| 2 | 500 | 15 |
| 3 | 1500 | 14 |
| 4 | 10000 | 18 |
| 5 | 100000 | 37 |
| 6 | 500000 | 7 |
样例 1
输入:
5 6
2 4 3 3
1 2 2 5
3 6 5 4
4 6 4 9
2 4 3 2
输出:
16
样例 2
输入:
3 5
2 4 3 7
1 3 1 2
2 5 4 3
输出:
-1