TẶNG QUÀ

Xem PDF

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Trong kỳ thi học sinh giỏi cấp tỉnh năm học 2022 – 2023. Để động viên, khích lệ tinh thần cho học sinh, ban tổ chức có chương trình tặng quà cho tất cả các thí sinh tham dự kỳ thi. Ban tổ chức chuẩn bị sẵn \( n \) hộp đựng quà, mỗi hộp được đặt trên một mặt bàn, các bàn được đánh số thứ tự từ 1 đến \( n \). Trên hộp quà thứ \( i \) có dán nhãn \( a_i \) và trong đó có món quà giá trị là \( w_i \).

Học sinh có thể chọn một hay nhiều hộp quà liên tiếp hay không liên tiếp từ hộp quà ở bàn 1 đến bàn thứ \( n \), hộp quà chọn sau phải có nhãn lớn hơn hộp quà chọn trước, tức là:

\[ \{a_{i_1} < a_{i_2} < a_{i_3} < ... < a_{i_k}\} \]
\[ 1 \leq i_1 < i_2 < i_3 < ... < i_k \leq n \]

Em hãy chọn cho mình các món quà để tổng giá trị là lớn nhất.

Dữ liệu

Đọc từ file văn bản QUA.INP gồm:

  • Dòng 1: số nguyên dương \( n \) (\( n \leq 5.10^5 \));
  • \( n \) dòng tiếp theo, dòng thứ \( i \) (\( i = 1..n \)) ghi hai số nguyên dương \( a_i \) (\( a_i \leq 10^9 \)) và \( w_i \) (\( w_i \leq 10^6 \)) là nhãn và giá trị của món quà trong hộp quà thứ \( i \).

Kết quả

Ghi ra file văn bản QUA.OUT là số nguyên duy nhất là tổng giá trị các món quà được chọn.

Ví dụ

QUA.INP QUA.OUT Giải thích
5 15 Chọn hộp quà thứ 1 có giá trị bằng 15
5 15
3 5
4 7
2 8
5 25 Có thể chọn các hộp quà 1, 3 có tổng giá trị là 10 + 15 = 25, hoặc có thể chọn các hộp quà 2, 4, 5 có tổng giá trị là 3 + 10 + 12 = 25
4 10
1 3
5 15
4 10

Giới hạn

  • Subtask 1: có 10/30 test tương ứng 1 điểm với \( n \leq 10^3 \);
  • Subtask 2: có 20/30 test tương ứng 3 điểm với \( n \leq 5.10^5 \).

Bình luận

Không có bình luận nào.