Jest sobie n dziur w rzędzie, jedna za drugą. W niektórych dziurach mieszkają robaki. Chcemy zasłonić wszystkie dziury gdzie mieszkają robaki deskami, tak, aby zużyć jak najmniej drewna; zasłonięcie jednej dziury kosztuje nas decymetr kwadratowy deski. Przy tym mamy mało gwoździ i jesteśmy w stanie zamocować tylko k desek. Ile minimalnie decymetrów kwadratowych deski zużyjemy?
W pierwszym wierszu wejścia są trzy liczby całkowite: 1 <= n <= 100 000, 1 < k,m <= n. Liczba n to liczba dziur, k to maksymalna liczba desek, zaś m to liczba robaków. W drugim wierszu wejścia jest rosnący ciąg liczb całkowitych 1 <= a1 < a2 ... am < n, w tych dziurach mieszkają robaki.
Dla danych wejściowych:
12 2 8 2 4 5 7 8 9 11 12
poprawnym wynikiem jest:
10
Należy położyć deskę od 2 do 5 oraz od 6 do 12.
[Zgłoś rozwiązanie] [Moje zgłoszenia]