Nhà và Trường

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Có $n$ ngôi nhà xếp thành một hàng, nhà thứ $i$ có $c_{i}$ trẻ em. Hãy chọn đúng $k$ ngôi nhà để xây trường học sao cho tổng quãng đường đi học của tất cả trẻ em là nhỏ nhất (mỗi em đến trường gần nhất).

Dữ liệu vào

Dòng 1: hai số nguyên $n$ và $k$ .
Dòng 2: $n$ số nguyên $c_{1}, c_{2}, \dots, c_{n}$ .

Dữ liệu ra

Một số nguyên — tổng quãng đường nhỏ nhất.

Ràng buộc

$1 \leq k \leq n \leq 3000$
$1 \leq c_{i} \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
6 2 2 7 1 4 6 4	11	Đặt trường tại nhà 2 và nhà 5. Trẻ ở nhà 1 đi 1 bước đến nhà 2, tổng = 2×1 + 1×1 + 4×0 + 6×1 + 4×0 = 11.
1 1 5	0	Chỉ có 1 nhà và 1 trường — trẻ không cần đi đâu.

Bình luận

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