P1901 发射站
题目描述
某地有 n 个能量发射站排成一行,从左往右依次编号为 1,2,…,n。第 i 个发射站的高度为 hi,并且能够同时向左右两边发射能量值为 vi 的能量;位于两端的发射站只有一侧有邻居,因此只向这一侧发射。
每个发射站发出的能量,只会被它两侧距离它最近的、高度严格大于它的发射站接收。若某一侧不存在比它高的发射站,那么这一侧发出的能量不会被任何发射站接收。
因此,一个发射站发出的能量可能被 0 个、1 个或 2 个发射站接收。请计算出接收能量最多的发射站收到了多少能量。
输入格式
第一行输入一个整数 n(1≦n≦106) 代表发射站的数量。
此后 n 行,第 i 行输入两个整数 $h_i, v_i \left(1 \leqq h_i \leqq 2 \times 10^9;\ 1 \leqq v_i \leqq 10^4\right)$,分别代表第 i 个发射站的高度和它发射的能量值。保证 h1,h2,…,hn 两两不同。
输出格式
在一行上输出一个整数,代表接收能量最多的发射站所接收到的能量值。
测试样例
3
4 2
3 5
6 10
7
样例 1 解释
三个发射站的高度依次为 4,3,6,发射的能量值依次为 2,5,10,能量的去向如下:
∙第 1 个发射站:左侧没有发射站,向左发射的能量无人接收;向右发射的能量值为 2,被第 3 个发射站接收;
∙第 2 个发射站:向左发射的能量值为 5,被第 1 个发射站接收;向右发射的能量值为 5,被第 3 个发射站接收;
∙第 3 个发射站:两侧都没有比它高的发射站,发出的能量全部无人接收。
于是第 1 个发射站共接收 5,第 2 个发射站共接收 0,第 3 个发射站共接收 2+5=7,接收能量的最大值为 7。
6
5 3
2 4
4 6
3 1
6 5
1 2
12
提示
对于 40% 的数据,1≦n≦5×103,1≦hi≦105,1≦vi≦104。
对于 70% 的数据,1≦n≦105,1≦hi≦2×109,1≦vi≦104。
对于 100% 的数据,1≦n≦106,1≦hi≦2×109,1≦vi≦104。
保证答案不超过 231−1。