| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P187PROE - ROUND 7E - NỐI ĐIỂM |
Cho 2N điểm trên mặt phẳng, được chia thành 2 hàng bên trái và bên phải. Mỗi điểm có được gán cho một giá trị nhất định. Tập giá trị của mỗi hàng là 1, 2, …, N.
Bạn được phép nối điểm bên trái có giá trị bằng A với điểm bên phải có giá trị bằng B nếu như |A – B| <= 4.
Nhiệm vụ của bạn là hãy xác định xem có thể nối nhiều nhất được bao nhiêu cặp điểm sao cho:
- Mỗi điểm bên trái chỉ nối với một điểm bên phải
- Không có cặp đường thẳng nào cắt nhau.
Input
Dòng đầu tiên chứa số nguyên dương N (1 <= N <= 100 000).
N dòng tiếp theo, mỗi dòng gồm 1 số nguyên của hàng bên trái. Sau đó là N số nguyên của hàng bên phải. Các số được liệt kê theo thứ tự từ trên xuống dưới. Mỗi số xuất hiện ở trong một hàng duy nhất 1 lần.
Output
In ra số đường thẳng nhiều nhất có thể vẽ được thỏa mãn yêu cầu.
Example
Input: 6
1
2
3
4
5
6
6
5
4
3
2
1 Output: 5
Một cách ghép là: 1 – 5, 2 – 4, 3 – 3, 4 – 2, 5 – 1.
| Được gửi lên bởi: | adm |
| Ngày: | 2018-05-13 |
| Thời gian chạy: | 1s-2s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
