Skyline Photo

题意翻译

[题目链接](https://www.luogu.com.cn/problem/CF1483C) 有 $n$ 栋楼房，每栋楼有一个高度 $a_i$ 和美丽值 $b_i$。 现在，你需要把这 $n$ 栋楼房划分成若干个连续段，每一个连续段的美丽值为该段中最矮的楼房的美丽值。总的划分美丽值为每个连续段的美丽值之和。 你需要求出最大可能的总划分美丽值。 ### 输入格式 第一行一个整数 $n$，表示楼房数。 第二行 $n$ 个整数，表示 $a_{1\dots n}$。 第三行 $n$ 个整数，表示 $b_{1\dots n}$。 ### 输出格式 输出一行一个整数，表示最大的总划分美丽值。 **数据范围** $1 \le n \le 3\cdot 10^5$。 $a$ 为一个长度为 $n$ 的排列。 $0 \le |b_i| \le 10^9$。

题目描述

Alice is visiting New York City. To make the trip fun, Alice will take photos of the city skyline and give the set of photos as a present to Bob. However, she wants to find the set of photos with maximum beauty and she needs your help. There are $ n $ buildings in the city, the $ i $ -th of them has positive height $ h_i $ . All $ n $ building heights in the city are different. In addition, each building has a beauty value $ b_i $ . Note that beauty can be positive or negative, as there are ugly buildings in the city too. A set of photos consists of one or more photos of the buildings in the skyline. Each photo includes one or more buildings in the skyline that form a contiguous segment of indices. Each building needs to be in exactly one photo. This means that if a building does not appear in any photo, or if a building appears in more than one photo, the set of pictures is not valid. The beauty of a photo is equivalent to the beauty $ b_i $ of the shortest building in it. The total beauty of a set of photos is the sum of the beauty of all photos in it. Help Alice to find the maximum beauty a valid set of photos can have.

输入输出格式

输入格式

The first line contains an integer $ n $ ( $ 1 \le n \le 3 \cdot 10^5 $ ), the number of buildings on the skyline. The second line contains $ n $ distinct integers $ h_1, h_2, \ldots, h_n $ ( $ 1 \le h_i \le n $ ). The $ i $ -th number represents the height of building $ i $ . The third line contains $ n $ integers $ b_1, b_2, \ldots, b_n $ ( $ -10^9 \le b_i \le 10^9 $ ). The $ i $ -th number represents the beauty of building $ i $ .

输出格式

Print one number representing the maximum beauty Alice can achieve for a valid set of photos of the skyline.

输入输出样例

输入样例 #1

5
1 2 3 5 4
1 5 3 2 4

输出样例 #1

15

输入样例 #2

5
1 4 3 2 5
-3 4 -10 2 7

输出样例 #2

10

输入样例 #3

2
2 1
-2 -3

输出样例 #3

-3

输入样例 #4

10
4 7 3 2 5 1 9 10 6 8
-4 40 -46 -8 -16 4 -10 41 12 3

输出样例 #4

96

说明

In the first example, Alice can achieve maximum beauty by taking five photos, each one containing one building. In the second example, Alice can achieve a maximum beauty of $ 10 $ by taking four pictures: three just containing one building, on buildings $ 1 $ , $ 2 $ and $ 5 $ , each photo with beauty $ -3 $ , $ 4 $ and $ 7 $ respectively, and another photo containing building $ 3 $ and $ 4 $ , with beauty $ 2 $ . In the third example, Alice will just take one picture of the whole city. In the fourth example, Alice can take the following pictures to achieve maximum beauty: photos with just one building on buildings $ 1 $ , $ 2 $ , $ 8 $ , $ 9 $ , and $ 10 $ , and a single photo of buildings $ 3 $ , $ 4 $ , $ 5 $ , $ 6 $ , and $ 7 $ .