{"code":"19dhbbpagoda","name":"Famous Pagoda (F - ACM ICPC Vietnam Regional 2017)","description":"Khi xây dựng cầu thang đến các ngôi chùa nổi tiếng ở trên đỉnh núi, Chính quyền địa phương đã xác định $N$ vị trí dọc theo sườn núi với các độ cao  $a_1, a_2, …, a_n$. Trong đó $a_i< a_{i+1}$ và $0< i< N$.\r\nGiá để xây dựng cầu thang từ vị trí đến $i$ vị trí $j$ là:\r\n\r\n$min_{v\\in \\mathbb{Z}}\\sum_{s=i}^{j}|a_s-v|^K$\r\n\r\nĐể đẩy nhanh quá trình xây dựng cầu thang từ vị trí 1 đến vị trí $N$, chính quyền địa phương đã quyết định giao việc cho $G$  nhà xây dựng để xây dựng cầu thang song song nhau. Với $N$ vị trí  sẽ được chia thành $G$ đoạn khác nhau và mỗi đoạn sẽ được phụ trách bởi một nhà thầu xây dựng khác nhau.\r\n\r\nVới $G$ nhà thầu xây dựng bạn hãy phân chia để $G$ nhà thầu xây dựng cây cầu với tổng chi phí bé nhất.\r\n\r\n#### Input\r\n - Dòng 1 ghi ba số nguyên $N, G, K$ ($1≤ N,G ≤2000, 1 ≤ K ≤ 2$).\r\n - Dòng 2 ghi dãy số nguyên $a_1  , a_2, … ,a_n$ $(1≤ a_i ≤ 10^6,a_i ≤ a_{i+1} ∀0  <   i< N)$  các vị trí cần xây dựng.\r\n\r\n#### Output\r\n - In giá trị xây dựng bé nhất.\r\n\r\n#### Scoring\r\n\r\n\r\n#### Example\r\n\r\n!!! question \"Test 1\"\r\n    \r\n    ???+ \"Input\"\r\n    \r\n        ```sample\r\n        5 1 1\r\n        1 2 3 4 5\r\n        ```\r\n        \r\n    ???+ success \"Output\"\r\n        ```sample\r\n        6\r\n        ```\r\n!!! question \"Test 2\"\r\n    \r\n    ???+ \"Input\"\r\n    \r\n        ```sample\r\n        5 1 2\r\n        1 2 3 4 5\r\n\r\n        ```\r\n        \r\n    ???+ success \"Output\"\r\n        ```sample\r\n        10\r\n        ```","points":2000.0,"partial":true,"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,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}