Gộp tệp K-phân
Points
45
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Đề 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$
Community Discussion