Educational DP Contest AtCoder Q - Flowers - Olympiads Online Judge

Educational DP Contest AtCoder Q - Flowers

View as PDF

Submit solution

All submissions

Best submissions

Points: 15

Time limit: 1.4s

Memory limit: 1G

Problem types

There are $N$ $N$ flowers arranged in a row. For each $i$ $i$ $(1 \le i \le N)$ $(1 \leq i \leq N)$ , the height and the beauty of the $i$ $i$ -th flower from the left is $h_i$ $h_{i}$ and $a_i$ $a_{i}$ , respectively. Here, $h_1, h_2, \dots, h_N$ $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 \leq N \leq 2 \times 10^{5}$
$1 \le h_i \le N$ $1 \leq h_{i} \leq N$
$h_1, h_2, \dots, h_N$ $h_{1}, h_{2}, \dots, h_{N}$ are all distinct.
$1 \le a_i \le 10^9$ $1 \leq a_{i} \leq 10^{9}$

Input Specification

The first line will contain the integer $N$ $N$ .

The next line will contain $N$ $N$ integers, $h_i$ $h_{i}$ .

The next line will contain $N$ $N$ integers, $a_i$ $a_{i}$ .

Output Specification

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

Sample Input 1

Copy

4
3 1 4 2
10 20 30 40

Sample Output 1

Copy

Explanation For Sample 1

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

Sample Input 2

Copy

1
1
10

Sample Output 2

Copy

Explanation For Sample 2

The condition is met already at the beginning.

Sample Input 3

Copy

5
1 2 3 4 5
1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

Copy

5000000000

Explanation For Sample 3

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

Sample Input 4

Copy

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

Sample Output 4

Copy

Explanation For Sample 4

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

Comments

0

SimonV commented on Jan. 24, 2024, 3:23 a.m.

This is similar to longest increasing subsequence

7

anishmahto commented on Jan. 17, 2019, 10: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$ $1 \leq h_{i} \leq N$ . In other words, the heights form a permutation of the integers from $1$ $1$ to $N$ $N$ .

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