Codeforces Round 696 (Div. 2) |
---|
Закончено |
У Игоря была последовательность $$$d_1, d_2, \dots, d_n$$$. Когда Игорь зашёл в класс, на доске было записано число $$$x$$$.
Игорь создал последовательность $$$p$$$ по следующему алгоритму:
Например, если $$$x = 3$$$, $$$d = [1, -1, 2]$$$, последовательность $$$p$$$ будет равна $$$[3, 4, 3, 4, 5]$$$.
Игорь решил посчитать длину наибольшей возрастающей подпоследовательности $$$p$$$ и их количество.
Последовательность $$$a$$$ является подпоследовательностью $$$b$$$, если $$$a$$$ может быть получена из $$$b$$$ удалением нескольких (возможно, ни одного или всех) элементов.
Последовательность $$$a$$$ является возрастающей, если каждый элемент $$$a$$$ (кроме первого) строго больше предыдущего.
При $$$p = [3, 4, 3, 4, 5]$$$ длина наибольшей возрастающей подпоследовательности равна $$$3$$$, а их количество равно $$$3$$$: $$$[\underline{3}, \underline{4}, 3, 4, \underline{5}]$$$, $$$[\underline{3}, 4, 3, \underline{4}, \underline{5}]$$$, $$$[3, 4, \underline{3}, \underline{4}, \underline{5}]$$$.
В первой строке задано одно целое число $$$n$$$ ($$$1 \leq n \leq 50$$$) — количество элементов в $$$d$$$.
Во второй строке задано одно целое число $$$x$$$ ($$$-10^9 \leq x \leq 10^9$$$) — число на доске.
В третьей строке заданы $$$n$$$ целых чисел $$$d_1, d_2, \ldots, d_n$$$ ($$$-10^9 \leq d_i \leq 10^9$$$).
Выведите два целых числа:
По модулю $$$998244353$$$ надо выводить только второе число.
3 3 1 -1 2
3 3
3 100 5 -3 6
9 7
3 1 999999999 0 1000000000
2000000000 1
5 34 1337 -146 42 -69 228
1393 3876
Первый пример разобран в условии.
Во втором примере $$$p = [100, 101, 102, 103, 104, 105, 104, 103, 102, 103, 104, 105, 106, 107, 108]$$$.
В третьем примере $$$p = [1, 2, \ldots, 2000000000]$$$.
Название |
---|