Chuỗi Thống Trị Hai Chiều

Buổi 38 — Divide & Conquer DP Dynamic Programming
Points
68
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Submissions
Đề bài

Cho $N$ vật phẩm được đánh số từ $1$ đến $N$, vật phẩm thứ $i$ có hai chỉ số $(a_i, b_i)$ và trọng số $w_i$. Bạn có thể chọn một dãy con các chỉ số $1 \le i_1 < i_2 < \dots < i_m \le N$ sao cho với mọi $1 \le t < m$, ta có $a_{i_t} \le a_{i_{t+1}}$ và $b_{i_t} \le b_{i_{t+1}}$. Hãy tìm tổng trọng số lớn nhất của một dãy con hợp lệ.

Dữ liệu vào
  • Dòng đầu tiên chứa số nguyên $N$ ($1 \le N \le 10^5$).
  • $N$ dòng tiếp theo, dòng thứ $i$ chứa ba số nguyên $a_i, b_i, w_i$ ($1 \le a_i, b_i \le 10^9, 1 \le w_i \le 10^9$).
Dữ liệu ra
  • Một số nguyên duy nhất là tổng trọng số lớn nhất có thể.
Ví dụ
Input Output
4
1 3 5
2 2 6
2 4 4
3 5 7
17
3
3 3 10
2 2 10
1 1 10
10
Giới hạn
  • $1 \le N \le 10^5$
  • $1 \le a_i, b_i, w_i \le 10^9$
Draft saved