Hàng Rào Chia Ô

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho một mảnh đất hình chữ nhật có kích thước $A \times B$ . Trên mảnh đất này có $N$ hàng rào dọc (song song với cạnh chiều cao) và $M$ hàng rào ngang (song song với cạnh chiều rộng), chia mảnh đất thành $(N + 1) \times (M + 1)$ ô hình chữ nhật.

Hàng rào dọc thứ $i$ nằm tại vị trí $x_{i}$ ( $0 < x_{i} < A$ ) và kéo dài toàn bộ chiều cao $B$ . Hàng rào ngang thứ $j$ nằm tại vị trí $y_{j}$ ( $0 < y_{j} < B$ ) và kéo dài toàn bộ chiều rộng $A$ .

Bạn muốn dỡ bỏ một số đoạn hàng rào sao cho tất cả các ô đều thông với nhau (từ bất kỳ ô nào có thể di chuyển sang bất kỳ ô nào khác). Mỗi hàng rào dọc có độ dài $B$ , mỗi hàng rào ngang có độ dài $A$ , nhưng khi dỡ bỏ, bạn chỉ cần dỡ một đoạn trên hàng rào đó để nối hai ô liền kề (đoạn dỡ có độ dài bằng kích thước của ô theo chiều vuông góc).

Cụ thể, để nối hai ô liền kề theo chiều ngang (cùng hàng, ngăn cách bởi một hàng rào dọc), chi phí bằng chiều cao của ô đó (khoảng cách giữa hai hàng rào ngang liền kề). Để nối hai ô liền kề theo chiều dọc (cùng cột, ngăn cách bởi một hàng rào ngang), chi phí bằng chiều rộng của ô đó (khoảng cách giữa hai hàng rào dọc liền kề).

Hãy tìm tổng độ dài hàng rào nhỏ nhất cần dỡ bỏ để tất cả các ô thông nhau.

Dữ liệu vào

Dòng đầu: bốn số nguyên $A$ , $B$ , $N$ , $M$ .
Dòng thứ hai: $N$ số nguyên $x_{1}, x_{2}, \dots, x_{N}$ — vị trí các hàng rào dọc.
Dòng thứ ba: $M$ số nguyên $y_{1}, y_{2}, \dots, y_{M}$ — vị trí các hàng rào ngang.

Dữ liệu ra

In ra một số nguyên duy nhất — tổng độ dài hàng rào nhỏ nhất cần dỡ bỏ.

Ràng buộc

$1 \leq A, B \leq 10^{9}$
$1 \leq N, M \leq 2000$ (trong một số test, $N, M \leq 25000$ )
Các vị trí hàng rào đôi một phân biệt và nằm trong khoảng hợp lệ.

Ví dụ

Input	Output	Giải thích
15 15 5 2 2 5 10 6 4 11 3	44	Xem giải thích bên dưới.

Giải thích ví dụ 1:

Mảnh đất $15 \times 15$ được chia bởi 5 hàng rào dọc tại vị trí ${2, 4, 5, 6, 10}$ và 2 hàng rào ngang tại vị trí ${3, 11}$ .

Các khoảng cách giữa các hàng rào dọc (sau khi sắp xếp: $0, 2, 4, 5, 6, 10, 15$ ) là: $2, 2, 1, 1, 4, 5$ .

Các khoảng cách giữa các hàng rào ngang (sau khi sắp xếp: $0, 3, 11, 15$ ) là: $3, 8, 4$ .

Cần dỡ bỏ tổng cộng $44$ đơn vị hàng rào để nối thông toàn bộ $6 \times 3 = 18$ ô.

Ghi chú

Bài toán tương đương với tìm cây khung nhỏ nhất (MST) trên đồ thị lưới $(N + 1) \times (M + 1)$ đỉnh, trong đó trọng số cạnh giữa hai ô liền kề là kích thước của ô theo chiều vuông góc với hàng rào ngăn cách chúng.

Bình luận

Không có bình luận tại thời điểm này.