{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv id\u003d\"problem-body\"\u003e\n\t\r\n\u003ctable class\u003d\"problems\" width\u003d\"100%\"\u003e\u003ctbody\u003e\u003ctr class\u003d\"navigation\"\u003e\r\n\u003ctd width\u003d\"50%\"\u003e\u003ca href\u003d\"https://www.spoj.com/problems/NKLEAVES/en/\"\u003eEnglish\u003c/a\u003e\u003c/td\u003e \r\n\u003ctd width\u003d\"50%\"\u003e\u003ca href\u003d\"https://www.spoj.com/problems/NKLEAVES/vn/\"\u003eVietnamese\u003c/a\u003e\u003c/td\u003e \r\n\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\r\n\r\n\u003cp\u003eOne beautiful autumn day Radu and Mars noticed that the garden alley where they usually spend time is rather full of leaves. They decided to gather all the leaves in exactly K piles. The alley is a straight line and they established a coordinate system on the alley, with the origine at the beginning of the alley.\u003c/p\u003e\r\n\u003cp\u003eThere are N leaves of various weights on the alley, all lined up, and the distance between each consecutive leaves is 1. More precisely the first leaf is at coordinate 1, the second at coordinate 2, ... , the N-th at coordinate N. Initially the two guys are at coordinate N.\u003c/p\u003e\r\n\u003cp\u003eThe leaf gathering operation takes place as Radu and Mars leave the garden, so the leaves can only be moved to the left. The cost of moving a leaf is equal to its weight times the distance it is moved. Obviously one of the K piles will be at coordinate 1, but the rest can be anywhere.\u003c/p\u003e\r\n\r\n\r\n\u003ch3\u003eTask\u003c/h3\u003e\r\n\u003cp\u003eFind out the total minimum cost of gathering the N leaves in exactly K piles.\u003c/p\u003e\r\n\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cp\u003eThe input contains on the first line two positive integers, N and K, separated by a space, having the significance given above. The following N lines contain N positive integers representing the weights of the leaves (line i+1 contains the weight of the leaf located at coordinate i).\u003c/p\u003e\r\n\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003eThe output will contain a single line on which the minimum cost for gathering all the leaves in exactly K piles will be written.\u003c/p\u003e\u003cp\u003e\r\n\r\n\u003c/p\u003e\u003ch3\u003eConstraints\u003c/h3\u003e\r\n\u003cul\u003e\r\n\u003cli\u003e0 \u0026lt; N \u0026lt; 100 001\u003c/li\u003e\r\n\u003cli\u003e0 \u0026lt; K \u0026lt; 11, K \u0026lt; N\u003c/li\u003e\r\n\u003cli\u003e0 \u0026lt; the weight of any leaf \u0026lt; 1 001\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\t\r\n\u003ch3\u003eExample\u003c/h3\u003e\r\n\u003cdiv\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5 2\r\n1\r\n2\r\n3\r\n4\r\n5\r\n\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e13\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/div\u003e\r\n\u003cp\u003eIt would be best to form the 2 piles in points 1 and 4.\r\nLeaves 1, 2 and 3 are taken to coordinate 1, and 4 and 5 are taken to coordinate 4.\r\nThe total cost is:\u003c/p\u003e\r\n\u003cp\u003e1 * 0 + 2 * 1 + 3 * 2 + 4 * 0 + 5 * 1 \u003d 13\u003c/p\u003e\r\n\r\n\n\u003c/div\u003e"}}]}