‹ 上一题 下一题 ›

07413. 接雨水·宽度版 未做

1000 ms 256 MB 测试点 10 线性DP

题目描述

一排宽度不一的柱子依次紧贴:第 根柱子宽 、高 。下雨后,第 根柱子上方的水深 = 它左边最高柱子和右边最高柱子中较矮的一根的高度,减去自身高度(为负记 0)。整排柱子共接住多少水?(水量 = 水深 × 柱宽 再求和)

输入格式

第一行一个整数 。
第二行 个整数 。
第三行 个整数 。

输出格式

一行一个整数:接住的总水量。

样例

输入
3
2 1 2
1 5 1
输出
5

数据范围

,,。

输入
输出

            
答案