#P13076. [NOISG 2019] Lasers
[NOISG 2019] Lasers
题目背景
熊猫先生知道小猫非常喜欢激光玩具,于是他决定给 Rar the Cat 买一个激光玩具。
题目描述
这个激光玩具的顶部有 个间距均匀的激光,全部朝下。第 个激光距离左边缘 个单位,第 个激光距离右边缘 个单位,相邻激光之间距离为 个单位。
该玩具共有 排滑动的挡板,每排有若干不重叠的挡板。具体来说:
- 每排有若干长度为正整数的挡板,总长度不超过 。
- 同一排内,所有挡板可以整体平移,但挡板之间相对位置不变,且不会重叠。
- 一个宽度为 的挡板可以完全阻挡连续 个激光。
请你计算,在所有挡板可能的配置中,有多少个激光会始终被至少一个挡板阻挡。
输入格式
第一行包含两个整数 和 。
接下来 行描述每排的挡板情况,每行格式如下:
- 一个整数 ,表示该排有 个挡板。
- 接下来 个整数,依次表示每个挡板的宽度,第一个整数是最左边挡板的宽度。
保证每排所有挡板的总宽度不超过 。
输出格式
输出一个整数,表示始终被至少一个挡板阻挡的激光数量。
11 3
2 2 3
1 7
2 4 1
3
10 3
3 1 5 1
4 2 2 3 1
3 1 6 2
6
10 1
1 4
0
提示
【样例解释】
对于样例 1:
第 排有一个宽度为 的挡板,它无论怎么移动,第 、、 号激光总会被阻挡。
对于样例 2:
第 、、、、、 号激光始终被至少一个挡板阻挡。
对于样例 3:
所有激光在至少一种挡板配置下都可以通过。
【数据范围】
- 每排所有挡板宽度和不超过
子任务编号 | 分值 | 额外限制 |
---|---|---|
无额外限制 |