[HSG3_HT_24] Chọn bạn nhảy

Xem dạng PDF
Gửi bài giải
Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Pascal, Python

Câu lạc bộ khiêu vũ nhà trường sau thành lập có ~m~ bạn nam được đánh số từ ~1~ đến ~m~ và ~n~ bạn nữ đánh số từ ~1~ đến ~n~ đăng ký tham gia. Bạn nam thứ ~i~ có chiều cao ~a_i~ ~(i = 1, 2, ..., m)~, bạn nữ thứ ~j~ có chiều cao ~b_j~ ~(j = 1, 2, ..., n)~.

Việc bố trí cặp nhảy trong các rất quan trọng, câu lạc bộ cần chọn một đội hình gồm ~k~ cặp bạn nhảy. Mỗi cặp nhảy có đúng một bạn nam và một bạn nữ. Chỉ số phù hợp của một cặp bạn nhảy là chênh lệch chiều cao của hai người, chỉ số phù hợp của cả đội hình bằng chỉ số phù hợp của cặp bạn nhảy lớn nhất.

Yêu cầu

Hãy chọn một đội hình gồm ~k~ cặp bạn nhảy sao cho chỉ số phù hợp của đội hình là nhỏ nhất.

Dữ liệu đầu vào

Gồm ba dòng:

  • Dòng đầu tiên chứa ba số nguyên dương ~m, n, k \le 10^5~ ~(k \le min(m, n))~;
  • Dòng 2 chứa ~m~ số nguyên dương ~a_1, a_2, ..., a_m~ ~(a_i \le 10^9)~;
  • Dòng 3 chứa ~n~ số nguyên dương ~b_1, b_2, ..., b_n~ ~(b_i \le 10^9)~.

Dữ liệu đầu ra

Gồm một số nguyên dương duy nhất là chỉ số phù hợp của đội hình theo phương án được chọn.

Ràng buộc dữ liệu

  • Có 30% số test ứng với 30% số điểm thỏa mãn: ~m, n \le 10^3,\ k = 1~;
  • 30% số test ứng với 30% số điểm thỏa mãn: ~m, n \le 10^5,\ k = 1~;
  • 40% số test còn lại ứng với 40% số không có ràng buộc gì thêm.

Ví dụ

Ví dụ 1
INPUT
4 5 3
1 2 3 4
2 2 1 4 5
OUTPUT
0
Ví dụ 2
INPUT
4 5 4
1 2 3 4
2 2 1 4 5
OUTPUT
1

Bình luận

Hãy đọc nội quy trước khi bình luận.