Collection de feuilles – Regional event 2017

Level 7

Énoncé

Après s'être légèrement assoupi au pied d'un arbre, Joseph Marchand observe les feuilles tombées des arbres le long de l'allée. Il remarque que quelqu'un avant lui s'est amusé à assembler les feuilles par tas à intervalles réguliers le long d'une ligne parcourant l'allée. Cela le perturbe beaucoup, il trouve qu'il y a trop de tas, il aimerait en fusionner pour qu'il y en ait moins. Joseph est encore un peu fatigué et il souhaiterait faire un minimum d'effort pour réorganiser les tas.

Il y a $N$ tas de feuilles tout au long de l'allée. Joseph se trouve initialement au début de l'allée, à la position 0, et il y a 1 tas de feuille par mètre. Le i-ème tas de feuilles plus proche de Joseph, à la position $i$, contient $M_i$ feuilles.

Joseph ne veut pas à avoir à faire de demi-tours, il peut donc uniquement transporter des feuilles du début de l'allée vers la fin de l'allée. Le coût pour transporter un tas de $M_i$ feuilles de la position $x_i$ vers la position $x_j$ est de $M_i\cdot (x_j - x_i)$.

Joseph souhaite rassembler ces feuilles en $K$ tas, aide-le en trouvant le coût minimal pour obtenir $K$ tas de feuilles à partir des $N$ tas initiaux.

Entrée

L'entrée comprendra 2 lignes :

  • La première ligne contiendra deux entiers $N$ et $K$.
  • La deuxième contiendra $N$ entiers, le i-ème d'entre eux sera le nombre de feuilles du tas à la position $i$.

Sortie

Vous afficherez un entier, le coût minimal pour rassembler les feuilles en $K$ tas à partir de la répartition initiale.

Contraintes

  • $1 \le N \le 500$
  • $1 \le K \le 50$
  • $1 \le M_i \le 10$

Contrainte de performance

  • $1 \le N \le 30\ 000$

Runtime constraints

Maximum memory usage
20000 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
5 2
5 4 3 2 1
Sample output
13
Sample input
10 3
7 9 3 8 1 4 9 5 2 4
Sample output
60

Submit your solution

You have to register or log in to be able to submit your solution.