Atcoder Educational DP Contest Q - Flowers

Xem dạng PDF

Gửi bài giải


Điểm: 0,20 (OI)
Giới hạn thời gian: 2.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout

Người đăng:
Nguồn bài:
Atcoder Educational DP Contest
Dạng bài
Ngôn ngữ cho phép
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.


Bình luận

Hãy đọc nội quy trước khi bình luận.



  • -1
    vhung197  đã bình luận lúc 14, Tháng 1, 2024, 11:06

    d


  • -2
    vkhanh_298  đã bình luận lúc 28, Tháng 10, 2023, 16:03

    hay quá


  • -7
    GoverdyWang  đã bình luận lúc 14, Tháng 10, 2023, 2:50

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -3
    hieubecclc01  đã bình luận lúc 9, Tháng 9, 2023, 9:17

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