问题 4220 --4.汽车旅行 (car)

4220: 4.汽车旅行 (car)

题目描述

  小明想在暑假里自己开车回家,顺带进行短途的旅行,现在他有一辆 油缸容量 为L 单位的汽车,他的学校在 1 号点,家在 n 号点。把起点和终点计算在内,依次会经过 n 个城市。 从第 i  号城市到 i+1  号城市需要消耗 W i 的油量,并且不能往回开(不能从 i+1 号城市开回到 i 号城市)。但是小明是个小机灵鬼,他发现每个城市的油价都不一样,这意味着需要有准备地规划自己应当在哪个城市加多少油。更有意思的是,他发现这 n 所城市都可以进行油价的自由买卖。在城市 i,如果每单位的购 买油价为 C i ,那么每单位的 售卖油价就为 0.95*C i 。当然小明不能太过于贪心,他只能把油放在油缸里,而不能放进瓶子或者罐子里,因为那样太危险。
现在小明有 m 单位的钱,请问到目的地最多还能够剩下多少钱?注意途中小明不能够欠钱!如果途中小明开不到终点,那么请输出-1。

输入

输入一共有 3 行,第一行依次为 n(城市数量), m(初始钱数), L(油缸容量)。
其中 n≤300,m≤10 9 ,L≤400。
第二行包含 n-1 个整数 W i (1≤W i ≤400)。
第三行包含 n 个整数 C i (1≤C i ≤10 9 )。

输出

输出共一行,保留两位小数,表示最后最多剩下多少钱。如果小明中途是在没有钱开回到家里,则输出-1。

样例输入输出

输入#1 复制
3 100 12
5 5
9 20 10
输出#1 复制
20.00
输入#2 复制
3 100 5
5 5
9 100 10
输出#2 复制
-1

提示

【样例解释】
对于样例 1,在 1 号城市购买 11 升油消费 99,在 2 号城市卖掉 1 升, 盈利
20*0.95=19,最终开到终点 3 号城市。
所以最终剩下的钱数是 100-99+19=20
【数据范围】
对 30%的数据,n<8, L<8。
对 70%的数据,n<100, L<100。

序号 标题 作者 发表时间 费用 订购数 操作