Chuỗi Không Gian Ba Chiều
Points
68
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
dp
Đề 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$
Community Discussion