eolymp
bolt
Try our new interface for solving problems
Məsələlər

K блоков

K блоков

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Вам дана последовательность A из n целых положительных чисел. Назовем значением разбиения последовательности на k блоков, сумму максимумов в каждом из k блоков. Вам нужно по заданному числу k найти величину разбиения с минимальным значением.

Giriş verilənləri

В первой строке находятся два целых числа n и k (1n10^5, 1k ≤ min(n, 100)). В следующей строке заданы n целых чисел A[1], A[2], ..., A[n] (1A[i]10^6) - элементы последовательности.

Выведите единственное число - значение минимального разбиения.

Nümunə

Giriş verilənləri #1
5 1
1 2 3 4 5
Çıxış verilənləri #1
5
Giriş verilənləri #2
5 2
1 2 3 4 5
Çıxış verilənləri #2
6
Mənbə 2014 X Международная Жаутыковская Олимпиада Алматы, Казахстан, 12-18 января