PreVOI 2025 - Contest 3 - Cặp nhảy

Xem dạng PDF

Gửi bài giải

Điểm: 60,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Pascal, PyPy, Python, Scratch

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

Một lớp học nhảy có ~n~ học viên, học viên thứ ~i~ có chiều cao là ~h_i~ ~(i = 1, 2, \dots, n)~. Trong một buổi học, sau khi hướng dẫn cho tất cả các học viên, thầy giáo muốn chọn ra ~k~ đôi nhảy, mỗi đôi gồm hai học viên để trình diễn và rút kinh nghiệm. Với một đôi nhảy, chênh lệch chiều cao giữa hai học viên càng nhỏ càng tốt, do đó, thầy giáo muốn lựa chọn ra ~k~ đôi nhảy mà tổng các chênh lệch chiều cao giữa hai học viên trong cùng một đôi của cả ~k~ đôi là nhỏ nhất.

Yêu cầu: Cho ~n~ số nguyên dương ~h_1, h_2, \dots, h_n~ là chiều cao của ~n~ học viên và số nguyên dương ~k~, hãy chọn ra ~k~ đôi nhảy mà tổng các chênh lệch chiều cao giữa hai học viên trong cùng một đôi của cả ~k~ đôi là nhỏ nhất.

Input

  • Dòng đầu chứa hai số nguyên dương ~n, k~ ~(2k \le n \le 10^5)~;

  • Tiếp theo là một dòng chứa ~n~ số nguyên dương ~h_1, h_2, \dots, h_n~ ~(h_i \le 10^9)~.

Output

Ghi ra một số là số tổng các chênh lệch chiều cao giữa hai học viên trong cùng một đôi của cả ~k~ đôi là nhỏ nhất.

Scoring

Subtask Điểm Ràng buộc
1 ~40\%~ ~n \le 20~
2 ~30\%~ ~n \le 2000~
3 ~30\%~ Không có giới hạn gì thêm

Sample Input 1

5 2
70 80 65 65 75

Sample Output 1

5

Bình luận

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