Có N thời điểm phân biệt. Một cuộc gặp được xác định bởi hai thời điểm trong danh sách, thời điểm nhỏ hơn là lúc bắt đầu và thời điểm lớn hơn là lúc kết thúc; độ dài cuộc gặp là hiệu của hai thời điểm đó.
Hãy chọn đúng K cuộc gặp sao cho các khoảng thời gian đôi một không chồng nhau và không có hai cuộc gặp dùng chung một thời điểm làm đầu mút. Tối thiểu hóa tổng độ dài của K cuộc gặp.
Input
Dòng đầu chứa K và N.
Dòng thứ hai chứa N thời điểm phân biệt ti; thứ tự ban đầu không nhất thiết tăng.
Output
In tổng thời lượng nhỏ nhất của K cuộc gặp.
Constraints
2≤2K≤N≤5⋅105.
K≤5000.
1≤ti≤109 và mọi ti đôi một phân biệt.
Scoring
Subtask 1 (50% số điểm): dữ liệu nằm trong miền nhỏ, phù hợp với lời giải vét cạn hoặc DP trực tiếp được mô tả trong tài liệu.
Subtask 2 (50% số điểm): Không có giới hạn bổ sung.
Example
Test 1
Input
2 6
10 1 4 20 21 7
Output
4
Giải thích: Sau khi sắp xếp, chọn các cuộc gặp [1,4] và [20,21]. Hai độ dài là 3 và 1, nên tổng nhỏ nhất bằng 4.
Lời giải tóm tắt
Mô hình: Từ N thời điểm phân biệt, chọn đúng K khoảng gặp không chồng nhau và không dùng chung đầu mút để tổng độ dài nhỏ nhất. Đại lượng bị giới hạn về số lượng được chuyển thành một khoản phạt hoặc phần thưởng, nhờ đó bỏ được chiều đếm lớn khỏi DP hay thuật toán tối ưu cơ sở.
Thuật toán: Sau khi sắp xếp, bài toán thành chọn đúng K cạnh không kề trên một đường; gắn thưởng cho mỗi cạnh được chọn và dùng DP hai bước kết hợp nhị phân.
Chứng minh đúng: Sau khi sắp xếp, trong một nghiệm tối ưu mỗi cuộc gặp có thể co hai đầu về hai thời điểm liên tiếp mà không tăng chi phí và không tạo giao nhau. Bài toán vì thế là matching đúng K cạnh trên đường. DP fixed-lambda so sánh bỏ gap hiện tại với chọn gap hiện tại sau trạng thái i−2; mọi nghiệm bị trừ lambda cho mỗi cạnh. Số cạnh tối ưu tăng theo lambda, nên ngưỡng nhỏ nhất đạt ít nhất K cạnh cho phép cộng lại lambda*K và nhận đúng chi phí tối thiểu.
Độ phức tạp: Sắp xếp O(N log N), mỗi lần DP O(N); tổng O(N log N + N log V) thời gian và O(N) bộ nhớ.