Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

NKLEAVES - Leaves

Đọc đề đẹp hơn ở:
https://codeforces.com/group/FLVn1Sc504/contest/274824/problem/J
{assign var="code" value="NKLEAVES"} {if $par==""} {assign var=par value=$locale} {/if}
{if $par=="vn"} {literal}

Một ngày thu đẹp trời, Radu và Mars nhận ra rằng khu vườn của họ chứa đầy lá rụng. Họ quyết định gom lá thành đúng K đống lá.

Biết rằng khu vườn có dạng một đường thẳng. 2 người đã thiết lập một hệ tọa độ với gốc ở điểm đầu của khu vườn.

Có N chiếc lá nằm thẳng hàng với trọng lượng khác nhau, khoảng cách giữa 2 chiếc lá liên tiếp là 1. Nghĩa là, chiếc lá đầu tiên có tọa độ 1, chiếc lá thứ 2 có tọa độ 2,..., chiếc lá thứ N có tọa độ N. Ban đầu, 2 người đang đứng ở tọa độ N.

Radu và Mars thực hiện việc gom lá trong khi rời khỏi khu vườn, do đó những chiếc lá chỉ có thể di chuyển về bên trái. Chi phí di chuyển một chiếc lá bằng tích của trọng lượng chếc lá và khoảng cách di chuyển. Hiển nhiên, một trong K đống lá sẽ nằm ở tọa độ 1, tuy nhiên những đống còn lại có thể nằm ở bất kỳ vị trí nào.

Yêu cầu: tìm chi phí nhỏ nhất để gom N chiếc lá thành đúng K đống lá.

Dữ liệu

  • Dòng đầu tiên chứa 2 số nguyên dương N và K, cách nhau bởi 1 khoảng trắng.
  • Dòng thứ i trong số N dòng tiếp theo chứa 1 số nguyên dương cho biết trọng lượng của chiếc lá thứ i.

Kết qủa

In ra 1 số nguyên là chi phí nhỏ nhất để gom N chiếc lá lại thành đúng K đống lá.

Giới hạn

  • 0 < N ≤ 100000
  • 0 < K ≤ 10, K < N
  • Trọng lượng của mỗi chiếc lá không vượt quá 1000.

Ví dụ

Dữ liệu:
5 2
1
2
3
4
5

Kết qủa
13

Giải thích: Cách tốt nhất là đặt 2 đống lá ở vị trí 1 và 4. {/literal}{elseif ($par=="en" || $par=="")}{literal}

One 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.

There 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.

The 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.

Task

Find out the total minimum cost of gathering the N leaves in exactly K piles.

Input

The 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).

Output

The output will contain a single line on which the minimum cost for gathering all the leaves in exactly K piles will be written.

Constraints

  • 0 < N < 100 001
  • 0 < K < 11, K < N
  • 0 < the weight of any leaf < 1 001

Example

Input
5 2
1
2
3
4
5

Output
13

It would be best to form the 2 piles in points 1 and 4. Leaves 1, 2 and 3 are taken to coordinate 1, and 4 and 5 are taken to coordinate 4. The total cost is:

1 * 0 + 2 * 1 + 3 * 2 + 4 * 0 + 5 * 1 = 13

{/literal} {/if}

Được gửi lên bởi:Jimmy
Ngày:2007-12-06
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Campion 2005

hide comments
2019-08-16 11:35:09


Last edit: 2019-08-19 15:00:34
2019-08-16 10:18:47


Last edit: 2019-08-16 10:32:48
2019-08-16 10:17:10
Tôi là Nguyễn Tiến Hùng chồng Thu Huyền
2019-08-16 10:15:36
toi la trung ca xin chao tran duc manh
2019-08-16 09:29:19
toi la tran duc manh xin chao fan ham mo
2019-03-28 04:24:21
có ai biết làm không chỉ mình cách làm với
2017-08-04 05:57:05
http://cowboycoder.tech/spoj/spoj-nkleaves-leaves
2016-12-08 04:41:02 le tuan dung
Tôi là Lê Tuấn Dũng. Xin chào các fan hâm mộ.
2016-07-30 12:07:36
IT cũng AC đc :)
2016-07-26 17:39:30
sử dụng IT cũng có thể AC zz dù time hơi chậm
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.