Codeforces Round 917 (Div. 2) |
---|
Закончено |
У вас есть массив целых чисел $$$a_1, a_2, \ldots, a_n$$$ длины $$$n$$$. В $$$i$$$-й из следующих $$$d$$$ дней вы собираетесь выполнить ровно одно из следующих двух действий:
Изначально ваш счет равен $$$0$$$. Обратите внимание, что в каждый день вы должны выполнить ровно одно из указанных выше действий: нельзя пропустить день или выполнить оба действия в один и тот же день.
Какой максимальный счет вы можете получить в конце?
Поскольку $$$d$$$ может быть довольно большим, последовательность $$$b$$$ дается вам в сжатом виде:
Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^3$$$) — количество наборов входных данных.
Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$k$$$ и $$$d$$$ ($$$1 \le n \le 2000$$$, $$$1 \le k \le 10^5$$$, $$$k \le d \le 10^9$$$) — длину массива $$$a$$$, длину последовательности $$$v$$$ и количество дней, в течение которых будут выполняться операции.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le n$$$) — массив $$$a$$$.
Третья строка каждого набора входных данных содержит $$$k$$$ целых чисел $$$v_1, v_2, \ldots, v_k$$$ ($$$1 \le v_i \le n$$$) — последовательность $$$v$$$.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2000$$$, а сумма $$$k$$$ по всем наборам входных данных не превосходит $$$10^5$$$.
Для каждого набора входных данных выведите одно целое число: максимальный счет, который вы можете получить в конце $$$d$$$-го дня.
53 4 41 2 31 3 2 36 2 36 1 2 4 1 56 65 1 10 5 0 5 051 1 1113 4 61 2 31 3 2 3
4 3 0 1 5
В первом наборе входных данных последовательность $$$b$$$ равняется $$$[1, 3, 2, 3, 1, 3, 2, 3, \ldots]$$$ и одно из оптимальных решений выглядит следующим образом:
Можно показать, что набрать больше $$$4$$$ невозможно, поэтому ответ — $$$4$$$.
Во втором наборе входных данных последовательность $$$b$$$ равняется $$$[6, 6, 6, 6, \ldots]$$$. Один из способов набрать $$$3$$$ — это выполнить операции первого типа в $$$1$$$-й и $$$3$$$-й дни и выполнить операцию второго типа во $$$2$$$-й день.
Название |
---|