Chuỗi Thống Trị Hai Chiều
Points
68
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Đề 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$
Community Discussion