Hoa Hồng Trọng Số

Buổi 39 — DP + Data Structures Dynamic Programming
Points
28
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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$
Draft saved