Входной файл: | Стандартный вход | Ограничение времени: | 2 сек | |
Выходной файл: | Стандартный выход | Ограничение памяти: | 512 Мб | |
Максимальный балл: | 100 |
Кай работает в лаборатории изучения массивов, он экспериментирует с двумя массивами натуральных чисел: A=[a1,a2,…,an] длины n и B=[b1,b2,…,bm] длины m.
Эксперимент, который проводит Кай, устроен следующим образом. У каждого из массивов отбрасывается произвольный, возможно пустой, префикс, а также произвольный, возможно пустой, суффикс, таким образом, чтобы оставшиеся части массивов имели равную длину. Обозначим получившиеся массивы как A′ и B′, а их длину как k. Затем Кай суммирует поэлементно получившиеся массивы, итоговый массив Кай обозначает как C=[c1,c2,…,ck].
Пусть, например, n=5, A=[4,3,3,2,1], m=6, B=[4,1,5,1,3,2], от массива A отбрасывается первый и последний элемент, от массива B три первых. После этого массивы имеют вид A′=[3,3,2], B′=[1,3,2], результат их поэлементного суммирования C=[4,6,4].
Задача Кая заключается в том, чтобы получать такие C, которые являются массивами-палиндромами, то есть если числа на первой и последней позиции совпадают, числа на второй и предпоследней позиции совпадают, и так далее, для всех i числа на позициях i и k−i+1 совпадают.
Помогите Каю понять, какой максимальный по длине массив-палиндром он может получить в результате эксперимента.
В первой строке ввода даны два целых числа n и m — количество элементов в первом и во втором массиве, соответственно (1⩽).
Во второй строке ввода даны n целых чисел a_{i} — массив A (1 \leqslant a_i \leqslant 100).
В третьей строке ввода даны m целых чисел b_{j} — массив B (1 \leqslant b_j \leqslant 100).
Выведите единственное целое число — максимальное k, что Кай в результате эксперимента может получить массив-палиндром длины k.
1 \leqslant n,\,m \leqslant 100\,000
1 \leqslant a_i \leqslant 100
1 \leqslant b_j \leqslant 100
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке |
1 | 13 | n,\,m \le 300 | первая ошибка | |
2 | 33 | все элементы массива B одинаковые | первая ошибка | |
3 | 16 | n \le 500, m \le 10^5 | 1 | первая ошибка |
4 | 38 | 1 — 3 | первая ошибка |
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|