Prologin
2024
É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$