{"code":"cses2087","name":"CSES - Houses and Schools | Nhà và Trường","description":"Có $n$ ngôi nhà nằm trên một con đường, được đánh số $1, 2, \\ldots, n$. Khoảng cách từ ngôi nhà $a$ đến $b$ là $|a - b|$. Bạn biết được số đứa trẻ trong từng căn nhà.\r\n\r\nNhiệm vụ của bạn là thành lập $k$ ngôi trường sao cho mỗi ngôi trường nằm ở một căn nhà nào đó. Sau đó, những đứa trẻ sẽ đi học ở trường gần chúng nhất. Tổng quãng đường đi bộ nhỏ nhất của những đứa trẻ là gì nếu bạn thực hiện một cách tối ưu? \r\n\r\n### Input\r\nDòng đầu vào đầu tiên có hai số nguyên $n$ và $k$: số ngôi nhà và số ngôi trường. Các ngôi nhà được đánh số $1, 2, \\ldots, n$.\r\n\r\nSau đó, có $n$ số nguyên $c_1, c_2, \\ldots, c_n$ : số đứa trẻ trong mỗi nhà.\r\n\r\n### Output\r\nIn ra tổng quãng đường nhỏ nhất.\r\n\r\n### Constraints\r\n- $1 \\leq k \\leq n \\leq 3000$\r\n- $1 \\leq c_i \\leq 10^9$\r\n\r\n### Example\r\n### Sample Input\r\n```\r\n6 2\r\n2 7 1 4 6 4\r\n```\r\n### Sample Output\r\n```\r\n11\r\n```\r\n**Giải thích:** Ngôi nhà 2 và 5 sẽ có trường học.","points":1900.0,"partial":false,"time_limit":1.0,"memory_limit":524288,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}