Gộp tệp K-phân

Buổi 12 — Greedy Algorithm greedy
Points
45
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Submissions
Đề bài

Có $N$ đống sỏi, đống thứ $i$ có kích thước $a_i$. Mỗi lần bạn được phép chọn từ $2$ đến $K$ đống sỏi để gộp lại thành một đống mới có kích thước bằng tổng kích thước các đống được chọn, với chi phí đúng bằng tổng kích thước đó. Hãy tìm tổng chi phí nhỏ nhất để gộp tất cả $N$ đống sỏi thành đúng $1$ đống duy nhất.

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên $N$ và $K$.
  • Dòng thứ hai chứa $N$ số nguyên $a_1, a_2, \dots, a_N$.
Dữ liệu ra

Một số nguyên duy nhất là tổng chi phí nhỏ nhất.

Ví dụ
Input Output
4 3\n1 2 3 4 13
5 2\n1 2 3 4 5 33
Giới hạn
  • $1 \le N \le 10^5$
  • $2 \le K \le 10^5$
  • $1 \le a_i \le 10^6$
Draft saved