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

FR_14_17 - Grupy

Andrzej uczy n uczniów algorytmiki. Każdy uczeń posiada pewien poziom wiedzy pi.

Nasz bohater chciałby podzielić swoich uczniów na m grup. Do każdej z m grup musi zostać przydzielony minimum 1 uczeń. Zdefiniujmy sobie poziom problematyczności jako różnicę poziomu wiedzy najlepszego i najsłabszego ucznia w grupie. Andrzej chciałby, aby po podziale na m grup, suma poziomów problematyczności była minimalna.

Odpowiedz na pytanie, ile wynosi minimalna suma poziomów problematyczności jaką może uzyskać Andrzej?

Wejście

W pierwszej linii wejścia znajduje się liczba uczniów n ∈ [1, 8000] oraz liczba grup m ∈ [1, n].

W drugiej linii wejścia znajduje się n liczb naturalnych pi ∈ [1, n], określających poziom wiedzy każdego z uczniów naszego bohatera.

Wyjście

Na wyjściu należy wypisać odpowiedź na pytanie, ile wynosi minimalna suma poziomów problematyczności jaką może uzyskać Andrzej.

Przykład

Wejście:

8 3
8 7 1 3 5 5 4 1

Wyjście:

3

Wyjaśnienie do przykładu:

Optymalny podział na grupy wygląda następująco:

  • 8 7
  • 3 5 5 4
  • 1 1

Poziom problematyczności powyższych grup wynosi odpowiednio: 1, 2, 0


Dodane przez:Maciej Boniecki
Data dodania:2021-12-17
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.