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

Задача . C. Подпоследовательности


Задача

Темы: дп Структуры данных *1900

Вам задана последовательность из n чисел. Найдите количество её возрастающих подпоследовательностей из k + 1 элемента. Гарантируется, что ответ не превосходит величины 8·1018.

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

В первой строке находятся два целых числа n и k (1 ≤ n ≤ 105, 0 ≤ k ≤ 10) — длина последовательности и количество элементов в возрастающей подпоследовательности. В следующих n строках находится по одному числу ai (1 ≤ ai ≤ n) — элементы последовательности. Все числа в последовательности различны.

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

Выведите одно число — ответ на задачу.


Примеры
№Входные данныеВыходные данные
1 5 2
1
2
3
5
4 
7

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

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

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет