{"code":"19dhbbseqpart","name":"SEQPART (IOI'14)","description":"Cho dãy $L$ gồm các  số $C[1..L]$, cần chia dãy này thành $G$ đoạn liên tiếp. Với phần tử thứ $i$, ta định nghĩa chi phí của nó là tích của $C_i$ và số lượng các số nằm cùng đoạn liên tiếp với $C_i$. Chi phí của dãy số ứng với một cách phân hoạch là tổng các chi phí của các phần tử của G đoạn đã chia.\r\n\r\n**Yêu cầu**: Hãy xác định cách phân hoạch dãy số để chi phí là nhỏ nhất.\r\n\r\n\r\n#### Input\r\n - Dòng đầu tiên chứa 2 số $L$ và $G$.\r\n - $L$ dòng tiếp theo, chứa giá trị của dãy $C_1, C_2, …, C_n$.\r\n\r\n#### Output\r\n - In một dòng duy nhất là chi phí nhỏ nhất.\r\n\r\n#### Scoring\r\n-\t$1 ≤  L ≤ 8000$.\r\n-\t$1 ≤ G  ≤ 800$.\r\n-\t$1 ≤ C_i  ≤ 10^9$.\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        6 3\r\n        11\r\n        11\r\n        11\r\n        24\r\n        26\r\n        100\r\n\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        299\r\n        ```\r\n    ??? warning \"Note\"\r\n        - Cách tối ưu là $C[]=(11,11,11), (24,26), (100)$  Chi phí   $11∗3 + 11∗3 + 11∗3 + 24∗2 + 26∗2 + 100∗1=299$.","points":1900.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}}