1348: PIPI的序列问题Ⅱ
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 299 Solved: 103
[Submit] [Status] [Web Board] [Creator:]
Description
PIPI又来考察大家序列处理能力啦。
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
Input
第一行给出一个整数n，表示柱子的个数。 n<=1e5.
接下来给出n个整数，表示n根柱子的高度，都不超过50000.
接下来给出n个整数，表示n根柱子的高度，都不超过50000.
Output
输出一共能接住多少雨水。
Sample Input
12
0 1 0 2 1 0 1 3 2 1 2 1
Sample Output
6