Money Trees
题意翻译
有 $n$ 棵树,每棵树高 $h_i$,有 $a_i$ 个果子。
你可以选一对 $l$ 和 $r$,使得 $h_{i+1}\mid h_i\space(l\le i<r)$ 且 $a_l+a_{l+1}+\dots +a_r\le k$。
求 $r-l+1$ 的最大值。
By @[Larryyu](https://www.luogu.com.cn/user/475329)
题目描述
Luca is in front of a row of $ n $ trees. The $ i $ -th tree has $ a_i $ fruit and height $ h_i $ .
He wants to choose a contiguous subarray of the array $ [h_l, h_{l+1}, \dots, h_r] $ such that for each $ i $ ( $ l \leq i < r $ ), $ h_i $ is divisible $ ^{\dagger} $ by $ h_{i+1} $ . He will collect all the fruit from each of the trees in the subarray (that is, he will collect $ a_l + a_{l+1} + \dots + a_r $ fruits). However, if he collects more than $ k $ fruits in total, he will get caught.
What is the maximum length of a subarray Luca can choose so he doesn't get caught?
$ ^{\dagger} $ $ x $ is divisible by $ y $ if the ratio $ \frac{x}{y} $ is an integer.
输入输出格式
输入格式
The first line contains a single integer $ t $ ( $ 1 \leq t \leq 1000 $ ) — the number of test cases.
The first of each test case line contains two space-separated integers $ n $ and $ k $ ( $ 1 \leq n \leq 2 \cdot 10^5 $ ; $ 1 \leq k \leq 10^9 $ ) — the number of trees and the maximum amount of fruits Luca can collect without getting caught.
The second line of each test case contains $ n $ space-separated integers $ a_i $ ( $ 1 \leq a_i \leq 10^4 $ ) — the number of fruits in the $ i $ -th tree.
The third line of each test case contains $ n $ space-separated integers $ h_i $ ( $ 1 \leq h_i \leq 10^9 $ ) — the height of the $ i $ -th tree.
The sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .
输出格式
For each test case output a single integer, the length of the maximum length contiguous subarray satisfying the conditions, or $ 0 $ if there is no such subarray.
输入输出样例
输入样例 #1
5
5 12
3 2 4 1 8
4 4 2 4 1
4 8
5 4 1 2
6 2 3 1
3 12
7 9 10
2 2 4
1 10
11
1
7 10
2 6 3 1 5 10 6
72 24 24 12 4 4 2
输出样例 #1
3
2
1
0
3
说明
In the first test case, Luca can select the subarray with $ l=1 $ and $ r=3 $ .
In the second test case, Luca can select the subarray with $ l=3 $ and $ r=4 $ .
In the third test case, Luca can select the subarray with $ l=2 $ and $ r=2 $ .