Siêu Chuỗi Ba Điều Kiện

Buổi 39 — DP + Data Structures Dynamic Programming
Points
100
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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:

  1. $X_{i_1} < X_{i_2} < \dots < X_{i_k}$
  2. $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$
Draft saved