8964: 限速路段
[Creator : ]
Description
园博会的某路段上有 $n$ 个路牌,相邻两个路牌之间间隔 $10$ 千米,这些路牌将这个路段划分为等间距的 $n-1$ 个区间。
路牌有两种类型:(1)限速,接下来的全部区间的速度都不能超过标识值;(2)取消限速,取消最近的一个与标识值相同的限速。其中,限速路牌用正整数表示,取消限速路牌用负整数表示,其真实标志值等于输入数据的绝对值。
例如,$60$ 表示限速 $60$ 的路牌,而 $-60$ 表示取消限速 $60$ 的路牌。
假设车辆在通过路牌的瞬间可以立即变速,那么通过此路段且不违反限速的最短用时是多少?多个限速同时生效时,车辆的速度应不超过有效的最低限速。
本题中速度的单位均为千米每小时。
路牌有两种类型:(1)限速,接下来的全部区间的速度都不能超过标识值;(2)取消限速,取消最近的一个与标识值相同的限速。其中,限速路牌用正整数表示,取消限速路牌用负整数表示,其真实标志值等于输入数据的绝对值。
例如,$60$ 表示限速 $60$ 的路牌,而 $-60$ 表示取消限速 $60$ 的路牌。
假设车辆在通过路牌的瞬间可以立即变速,那么通过此路段且不违反限速的最短用时是多少?多个限速同时生效时,车辆的速度应不超过有效的最低限速。
本题中速度的单位均为千米每小时。
Input
第一行包括 $2$ 个整数 $n\ (2 \leq n \leq 2 \times 10^5),\ m\ (1 \leq m \leq 100)$,分别表示路牌的数量和车辆的最高时速。
接下来一行包括 $n$ 个整数,按顺序表示遇到的路牌。保证速度的绝对值不超过 $600$。
接下来一行包括 $n$ 个整数,按顺序表示遇到的路牌。保证速度的绝对值不超过 $600$。
Output
输出一行包括一个数字,表示答案,保留两位小数输出。
Sample 1 Input
5 100
10 -10 30 20 40
Sample 1 Output
1.93
第 $1$ 个区间,速度为 $10$,用时 $1$
第 $2$ 个区间,速度为 $100$,用时 $0.1$
第 $3$ 个区间,速度为 $30$,用时 $\frac{1}{3}$
第 $4$ 个区间,速度为 $20$,用时 $0.5$
合计总用时 $1+0.1+\frac{1}{3}+0.5=1.93$
第 $2$ 个区间,速度为 $100$,用时 $0.1$
第 $3$ 个区间,速度为 $30$,用时 $\frac{1}{3}$
第 $4$ 个区间,速度为 $20$,用时 $0.5$
合计总用时 $1+0.1+\frac{1}{3}+0.5=1.93$
Sample 2 Input
6 100
40 40 -40 30 30 30
Sample 2 Output
1.42
第 $3$ 个区间,取消了一个限速 $40$,但是还有另外一个限速 $40$ 生效,因此速度还是 $40$。
Sample 3 Input
4 100
10 40 -40 1
Sample 3 Output
3.00