Siêu Chuỗi Ba Điều Kiện
Points
100
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
dp
Đề bài
Cho một dãy gồm $N$ điểm theo thứ tự từ $1$ đến $N$. Điểm thứ $i$ có tọa độ $(X_i, Y_i)$ và trọng số dương $W_i$.
Hãy chọn một dãy con các chỉ số $1 \le i_1 < i_2 < \dots < i_k \le N$ sao cho:
- $X_{i_1} < X_{i_2} < \dots < X_{i_k}$
- $Y_{i_1} < Y_{i_2} < \dots < Y_{i_k}$
Tìm tổng trọng số $\sum_{t=1}^k W_{i_t}$ lớn nhất có thể.
Dữ liệu vào
Dòng đầu tiên chứa số nguyên dương $N$. $N$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $X_i, Y_i, W_i$.
Dữ liệu ra
In ra một số nguyên duy nhất là tổng trọng số lớn nhất tìm được.
Ví dụ
| Input | Output |
|---|---|
| 5 1 1 5 3 3 10 2 2 8 4 4 6 5 3 20 |
33 |
| 4 4 4 10 3 3 10 2 2 10 1 1 10 |
10 |
Giới hạn
- $1 \le N \le 5 \cdot 10^4$
- $-10^9 \le X_i, Y_i \le 10^9$
- $1 \le W_i \le 10^9$
Community Discussion