(replacesum.*)

Hôm nay Nhật được thầy Hùng cho một bài tập như sau:

Cho một dãy số gồm \(n\) phần tử \(a_{1},a_{2},\ldots,a_{n}\) và một số nguyên dương \(k\)

Trong mỗi thao tác bạn được thực hiện:

+ Nếu trong mảng còn ít nhất \(k\) phần tử, bạn phải chọn ra \(k\) phần tử nhỏ nhất (hoặc chọn tất cả nếu số lượng phần tử trong mảng ít hơn \(k\)) rồi thay thế bằng tổng của chúng.

+ Chi phí cho mỗi lần thực hiện chính là hiệu của số lớn nhất và số nhỏ nhất trong các số vừa chọn.

+ Lặp lại thao tác đến khi nào trong mảng còn đúng một phần tử.

Yêu cầu: Hãy cho biết phần tử còn lại trong mảng và tổng chi phí thực hiện?

Dữ liệu vào:

+ Dòng đầu tiên ghi số nguyên dương \(n\) là số lượng phần tử (\(1 \leq n \leq 2 \times 10^{5})\) và số nguyên dương \(k\ (2 \leq k \leq n)\)

+ Dòng tiếp theo chứa \(n\) số nguyên \(a_{1},a_{2},\ldots,a_{n}\ (0 \leq a_{i} \leq 10^{9})\)

Kết quả:

+ Dòng đầu tiên là giá trị của phần tử còn lại trong mảng

+ Dòng thứ hai là tổng chi phí thực hiện.

Ràng buộc:

+ Có 50% số test có \(n \leq 2000\)

+ Có 50% số test còn lại không có ràng buộc nào thêm

Ví dụ:

Solution:

Sử dụng hàng đợi ưu tiên để tổ chức lưu trữ và thực hiện các thao tác như trong đề bài