Dãy Con Tăng Trọng Số Lớn Nhất

Buổi 39 — DP + Data Structures Buổi 40 — Contest Chặng 5
Points
30
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Cho dãy gồm $N$ phần tử, phần tử thứ $i$ có giá trị $a_i$ và trọng số $w_i$. Hãy tìm một dãy con tăng ngặt ($a_{i_1} < a_{i_2} < \dots < a_{i_k}$ với $i_1 < i_2 < \dots < i_k$) sao cho tổng trọng số $\sum_{j=1}^k w_{i_j}$ là lớn nhất.

Dữ liệu vào
  • Dòng đầu tiên chứa số nguyên $N$.
  • Dòng thứ hai chứa $N$ số nguyên $a_1, a_2, \dots, a_N$.
  • Dòng thứ ba chứa $N$ số nguyên $w_1, w_2, \dots, w_N$.
Dữ liệu ra

In ra tổng trọng số lớn nhất tìm được.

Ví dụ
Input Output
4\n1 3 2 4\n10 50 20 30 90
Giới hạn
  • $1 \le N \le 10^5$
  • $1 \le a_i, w_i \le 10^9$
Draft saved