Codeforces Round 898 (Div. 4) |
---|
Закончено |
Лука стоит перед рядом из $$$n$$$ деревьев. У $$$i$$$-го дерева есть $$$a_i$$$ фруктов и высота $$$h_i$$$.
Он хочет выбрать непрерывный подмассив массива $$$[h_l, h_{l+1}, \dots, h_r]$$$, такой что для каждого $$$i$$$ ($$$l \leq i < r$$$), $$$h_i$$$ делится$$$^{\dagger}$$$ на $$$h_{i+1}$$$. Он соберет все фрукты с каждого дерева в подмассиве (то есть, он соберет $$$a_l + a_{l+1} + \dots + a_r$$$ фруктов). Однако, если он соберет больше $$$k$$$ фруктов в общей сложности, его поймают.
Какова максимальная длина подмассива, который Лука может выбрать, чтобы не попасться?
$$$^{\dagger}$$$ $$$x$$$ делится на $$$y$$$, если отношение $$$\frac{x}{y}$$$ является целым числом.
Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 1000$$$) — количество наборов входных данных.
Первая строка каждого набора содержит два целых числа, разделенных пробелом: $$$n$$$ и $$$k$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$; $$$1 \leq k \leq 10^9$$$) — количество деревьев и максимальное количество фруктов, которое Лука может собрать, не попавшись.
Вторая строка каждого набора содержит $$$n$$$ целых чисел, разделенных пробелом: $$$a_i$$$ ($$$1 \leq a_i \leq 10^4$$$) — количество фруктов в $$$i$$$-м дереве.
Третья строка каждого набора содержит $$$n$$$ целых чисел, разделенных пробелом: $$$h_i$$$ ($$$1 \leq h_i \leq 10^9$$$) — высота $$$i$$$-го дерева.
Сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите одно целое число, длину максимального непрерывного подмассива, удовлетворяющего условиям, или $$$0$$$, если такого подмассива нет.
55 123 2 4 1 84 4 2 4 14 85 4 1 26 2 3 13 127 9 102 2 41 101117 102 6 3 1 5 10 672 24 24 12 4 4 2
3 2 1 0 3
В первом примере Лука может выбрать подмассив с $$$l=1$$$ и $$$r=3$$$.
Во втором примере Лука может выбрать подмассив с $$$l=3$$$ и $$$r=4$$$.
В третьем примере Лука может выбрать подмассив с $$$l=2$$$ и $$$r=2$$$.
Название |
---|