Atcoder Educational DP Contest Q - Flowers

View as PDF

Submit solution


Points: 0.20 (partial)
Time limit: 2.0s
Memory limit: 1G
Input: stdin
Output: stdout

Suggester:
Problem source:
Atcoder Educational DP Contest
Problem types
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Có ~N~ bông hoa được xếp thành một hàng trong vườn hoa của Taro. Với mỗi ~i\,(1 \le i \le N)~, chiều cao và vẻ đẹp của bông hoa thứ ~i~ từ trái sang phải lần lượt là ~h_i~ và ~a_i~. Trong vườn hoa, chiều cao của các bông hoa ~h_1, h_2, \ldots, h_N~ phân biệt đôi một với nhau.

Taro đang nhổ một số bông hoa đi để những bông hoa còn lại trong vườn thỏa mãn điều kiện sau đây:

  • Chiều cao của các bông hoa còn lại tăng dần từ trái sang phải.

Taro muốn vườn hoa của mình là đẹp nhất có thể (dĩ nhiên, ai mà chẳng muốn như vậy), vậy nên Taro muốn bỏ đi các bông hoa sao cho tổng vẻ đẹp của những bông hoa còn lại là lớn nhất. Tuy nhiên, Taro đang bận làm bài tập nên đã nhờ bạn làm giúp việc này. Hãy giúp Taro và in ra tổng vẻ đẹp lớn nhất có thể của các bông hoa còn lại.

Input

Dòng thứ nhất chứa một số nguyên ~N\,(1 \le N \le 2 \times 10^5)~.

Dòng thứ hai chứa ~N~ số nguyên ~h_i\,(1 \le h_i \le N)~ phân biệt đôi một.

Dòng thứ ba chứa ~N~ số nguyên ~a_i\,(1 \le a_i \le 10^9)~.

Output

In ra tổng vẻ đẹp lớn nhất có thể của những bông hoa còn lại.

Sample 1

Input
4
3 1 4 2
10 20 30 40
Output
60
Giải thích

Tổng vẻ đẹp lớn nhất của vườn hoa có thể là ~60~, bằng cách giữ lại các bông hoa thứ hai và thứ tư từ trái qua phải.

Sample 2

Input
1
1
10
Output
10
Giải thích

Vườn hoa đã thỏa mãn điều kiện đề bài từ ban đầu.

Sample 3

Input
5
1 2 3 4 5
1000000000 1000000000 1000000000 1000000000 1000000000
Output
5000000000

Sample 4

Input
9
4 2 5 8 3 6 1 7 9
6 8 8 4 6 3 5 7 5
Output
31
Giải thích

Tổng vẻ đẹp lớn nhất của vườn hoa có thể là ~31~, bằng cách giữ lại các bông hoa thứ hai, thứ ba, thứ sáu, thứ tám và thứ chín từ trái qua phải.

Lưu ý

Đáp án có thể vượt quá giới hạn của kiểu biến số nguyên 32-bit.


Comments

Please read the guidelines before commenting.



  • -7
    vhung197  commented on Jan. 14, 2024, 11:06 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -3
    vkhanh_298  commented on Oct. 28, 2023, 4:03 p.m.

    hay quá


  • -17
    GoverdyWang  commented on Oct. 14, 2023, 2:50 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -2
    hieubecclc01  commented on Sept. 9, 2023, 9:17 a.m.

    Bài rất hay và bổ ích.