Hoa Hồng Trọng Số
Points
28
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Đề bài
Trong một khu vườn có $N$ bông hoa hồng xếp thành hàng ngang. Bông hoa thứ $i$ có chiều cao $H_i$ và vẻ đẹp $V_i$.
Bạn muốn giữ lại một dãy con các bông hoa sao cho chiều cao của các bông hoa được giữ lại tăng nghiêm ngặt từ trái sang phải ($H_{i_1} < H_{i_2} < \dots < H_{i_k}$). Hãy tìm tổng vẻ đẹp lớn nhất có thể của các bông hoa được giữ lại.
Dữ liệu vào
Dòng đầu tiên chứa số nguyên dương $N$. Dòng thứ hai chứa $N$ số nguyên $H_1, H_2, \dots, H_N$. Dòng thứ ba chứa $N$ số nguyên dương $V_1, V_2, \dots, V_N$.
Dữ liệu ra
In ra một số nguyên duy nhất là tổng vẻ đẹp lớn nhất.
Ví dụ
| Input | Output |
|---|---|
| 4 3 1 2 4 10 5 6 8 |
19 |
| 5 5 4 3 2 1 10 50 20 30 40 |
50 |
Giới hạn
- $1 \le N \le 2 \cdot 10^5$
- $-10^9 \le H_i \le 10^9$
- $1 \le V_i \le 10^9$
Community Discussion