PreVOI 2023 - Phú Thọ - Truyền tin

Xem dạng PDF

Gửi bài giải

Điểm: 50,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

Có ~n~ người đánh số từ ~1~ đến ~n~ xếp thành một hàng và cùng nhau chơi trò chơi truyền tin. Người thứ ~i~ ~(1 \le i \le n)~ có độ trễ khi truyền tin là ~d_i~, khi đó độ trễ người thứ ~i~ truyền tin cho người thứ ~j~ ~(1 \le i \le j \le n)~ được tính bằng ~D(i, j) = \max\{d_i, d_{i+1}, \dots, d_j\}~.

Người quản trò muốn tìm ra ~k~ ~(1 \le k \le n)~ người chơi để tổng độ trễ liên lạc là nhỏ nhất. Một cách hình thức, cần chọn ra ~k~ chỉ số ~1 \le i_1 < i_2 < \dots < i_k \le n~ sao cho ~w = \sum_{1 \le x \le y \le k} D(i_x, i_y)~ là nhỏ nhất.

Yêu cầu: Tính giá trị ~w~ nhỏ nhất.

Input

  • Dòng đầu chứa hai số nguyên ~n, k~;

  • Dòng thứ hai chứa ~n~ số nguyên dương ~d_1, d_2, \dots, d_n~ ~(d_i \le 10^9)~.

Output

Ghi ra một số nguyên duy nhất là giá trị ~w~ tính được.

Scoring

Subtask Điểm Ràng buộc
1 ~20\%~ ~n \le 20~;
2 ~30\%~ ~k = 3~ và ~n \le 10^4~;
3 ~30\%~ ~n \le 500~;
4 ~20\%~ ~n \le 10^4~.

Sample Input 1

4 3
1 2 2 1

Sample Output 1

10

Notes

Chọn ba người ~1, 2, 4~ có tổng độ trễ nhỏ nhất bằng:

~D(1, 2) + D(1, 4) + D(2, 4) + D(1, 1) + D(2, 2) + D(4, 4) = 10~


Bình luận

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


Không có bình luận tại thời điểm này.