Олимпиадный тренинг

Задача . O. Первоапрельская задача (сложная)


Планы для HC2 довольно надуманны: остаётся чуть более чем 500 000 дней до HC2 3387, например, и, соответственно, мы планируем сделать несколько сотен тысяч задач в соответствующем году (мы надеемся, что соревнования по программированию станут более популярными). Суркам нужно приступать к работе, и они могли бы использовать хороший план ...

Входные данные

Входные данные те же, что и в средней версии этой задачи, но изменены ограничения: 1 ≤ k ≤ n ≤ 500 000.

Выходные данные

Выходные данные те же, что и в средней версии этой задачи.


Примеры
Входные данныеВыходные данные
1 8 4
3 8 7 9 9 4 6 8
2 5 9 4 3 8 9 1
32

time 10000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w643
Комментарий учителя