Educational DP Contest AtCoder Q - Flowers

View as PDF

Submit solution

Points: 15
Time limit: 1.4s
Memory limit: 1G

Problem types

There are N flowers arranged in a row. For each i (1 \le i \le N), the height and the beauty of the i-th flower from the left is h_i and a_i, respectively. Here, h_1, h_2, \dots, h_N are all distinct.

Taro is pulling out some flowers so that the following condition is met:

  • The heights of the remaining flowers are monotonically increasing from left to right.

Find the maximum possible sum of the beauties of the remaining flowers.

Constraints

  • All values in input are integers.
  • 1 \le N \le 2 \times 10^5
  • 1 \le h_i \le N
  • h_1, h_2, \dots, h_N are all distinct.
  • 1 \le a_i \le 10^9

Input Specification

The first line will contain the integer N.

The next line will contain N integers, h_i.

The next line will contain N integers, a_i.

Output Specification

Print the maximum possible sum of the beauties of the remaining flowers.

Sample Input 1

4
3 1 4 2
10 20 30 40

Sample Output 1

60

Explanation For Sample 1

We should keep the second and fourth flowers from the left. Then, the heights would be 1, 2 from left to right, which is monotonically increasing, and the sum of the beauties would be 20+40 = 60.

Sample Input 2

1
1
10

Sample Output 2

10

Explanation For Sample 2

The condition is met already at the beginning.

Sample Input 3

5
1 2 3 4 5
1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

5000000000

Explanation For Sample 3

The answer may not fit into a 32-bit integer type.

Sample Input 4

9
4 2 5 8 3 6 1 7 9
6 8 8 4 6 3 5 7 5

Sample Output 4

31

Explanation For Sample 4

We should keep the second, third, sixth, eighth and ninth flowers from the left.


Comments


  • 5
    anishmahto  commented on Jan. 17, 2019, 5:15 p.m.

    It isn't mentioned here, but assuming the randomly generated test data complies with the original problem's constraints, 1 \leq h_i \leq N. In other words, the heights form a permutation of the integers from 1 to N.

    https://atcoder.jp/contests/dp/tasks/dp_q