Skyline Photo
Contest: Технокубок 2021 - Финал
Difficulty rating: 2100
Tags: data structures, divide and conquer, dp

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.

Input format:
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$$$.

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

Constraints:
Time limit: 2.5 s
Memory limit: 256.0 MB

Note:
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$$$.

Example input:
5
1 2 3 5 4
1 5 3 2 4

Example output:
15

Example input:
5
1 4 3 2 5
-3 4 -10 2 7

Example output:
10

Editorial:
We can solve this problem with DP. A trivial $$$O(n^2)$$$ algorithm would look like this: Define $$$dp_i$$$ as the maximum beauty that can be achieved if we have a set of photos of buildings from $$$1$$$ to $$$i$$$. We can check every possible splitting point $$$j \le i$$$ for the rightmost picture of the set, and keep the biggest answer. $$$dp_i = max_{j \le i}(dp_{j - 1} + b_{j..i})$$$.
Now we just need to optimize this solution. Assume we are calculating $$$dp_i$$$ First important thing we need to realize is that, if we find the position of the closest smaller number to the left of $$$i$$$, on position $$$j$$$, and we choose to add it in the rightmost photo with building $$$i$$$, then the best solution would be on $$$dp_j$$$, because all numbers after $$$j$$$ are bigger than $$$h_j$$$, so they would not change the beauty of the picture (this is assuming that $$$i$$$ and $$$j$$$ are on the same photo). Note that we had already calculated the max beauty of $$$dp_j$$$, so it is not necessary to go back any further, as we have the best answer stored at $$$dp_j$$$
Having this observation, we are just left to check numbers between $$$j$$$ and $$$i$$$ as possible splitting points for the rightmost picture (the case where building $$$j$$$ and building $$$i$$$ are in different pictures). But we now know that every height from $$$j + 1$$$ to $$$i - 1$$$ is bigger than $$$h_i$$$ ( this is because $$$j$$$ is the closets smaller height), so the answer will just be $$$dp_{k - 1}$$$ + $$$b_i$$$ for any $$$k$$$ between $$$j + 1$$$ and $$$i$$$. We want to maximize the answer, so we just want to look for the max $$$dp_k$$$ value in this range. To do this, we can keep a max segment tree with dp values, and query it in $$$O(lgn)$$$ time. After we calculate $$$dp_i$$$, we insert it to the segment tree. This gives un an $$$O(n*lgn)$$$ solution, enough to solve the problem.
For the final implementation, we can iterate from 1 to $$$n$$$, keeping a stack with height values, to calculate the closest smaller building for each building. We just pop the stack while the current building is smaller than the top value of the stack, and insert the current building on top of the stack. Actually, by using this trick right, a segment tree is not really necessary. We can calculate the minimum answer for the ranges by updating information as we delete or add numbers in the stack. So it is possible to achieve a linear time solution. However, $$$O(n*lgn)$$$ is enough to solve the problem, so this optimization is not necessary.