Kanino và bài toán bông hoa(*)
Xem PDF
Điểm:
1600 (p)
Thời gian:
2.0s
Bộ nhớ:
1023M
Input:
bàn phím
Output:
màn hình
Có \(N\) bông hoa được sắp thành \(1\) hàng. Với mỗi \(i(1\le i\le N)\), chiều cao và độ "đẹp" của bông hoa thứ \(i\) lần lượt là \(h_i\) và \(a_i\). Ở đây \(h_1,h_2,...,h_N\) phân biệt với nhau từng đôi một!
\(Kaninho\) muốn lấy đi vài bông hoa để những bông hoa còn lại thỏa mãn điều kiện sau :
- Chiều cao của những bông hoa còn lại là một dãy đơn điều tăng dần từ trái sang phải
Yêu cầu: Tìm độ "đẹp" lớn nhất có thể có của những bông hoa còn lại
Input
-
Dòng thứ nhất chứa số nguyên \(N(1\le N\le 2\times 10^5)\)
-
Dòng thứ hai chứa \(n\) số nguyên \(h_1,h_2,...,h_N(1\le h_i\le N)\)
-
Dòng thứ ba chứa \(n\) số nguyên \(a_1,a_2,...,a_N(1\le a_i\le 10^9)\)
Output
- In ra đáp án cần tìm
Example
Test 1
Input
4
3 1 4 2
10 20 30 40Output
60Note
Giải thích: Ở đây ta sẽ lấy đi bông hoa thứ \(1\) và bông hoa thứ \(3\). Khi đó những bông hoa còn lại thỏa mãn yêu cầu bài toán và chúng có tổng độ "đẹp" lớn nhất là \(60\)
Bình luận
À các anh cứ comment các bài khác nữa nhé !!!
trong đề n<=2e5 mà các test n tối đa chỉ có 15 ?