Chuỗi Không Gian Ba Chiều

Buổi 39 — DP + Data Structures Dynamic Programming
Points
68
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
dp
Submissions
Đề bài

Cho $N$ điểm trong không gian ba chiều, điểm thứ $i$ có tọa độ $(X_i, Y_i, Z_i)$.

Hãy tìm độ dài lớn nhất của một chuỗi các điểm $(x_1, y_1, z_1), (x_2, y_2, z_2), \dots, (x_k, y_k, z_k)$ sao cho cả ba tọa độ đều tăng nghiêm ngặt: $x_1 < x_2 < \dots < x_k$, $y_1 < y_2 < \dots < y_k$ và $z_1 < z_2 < \dots < z_k$.

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, Z_i$.

Dữ liệu ra

In ra một số nguyên duy nhất là số điểm tối đa trong chuỗi.

Ví dụ
Input Output
4
1 2 3
2 3 4
2 1 5
3 4 5
3
5
1 5 2
2 4 3
3 3 4
4 2 5
5 1 6
1
Giới hạn
  • $1 \le N \le 5 \cdot 10^4$
  • $1 \le X_i, Y_i, Z_i \le 10^9$
Draft saved