1873F.md (2112B)
1 Source: https://codeforces.com/problemset/problem/1873/F 2 3 F. Money Trees 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Luca is in front of a row of $n$ trees. The $i$-th tree has $a_i$ fruit and height $h_i$. 22 23 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 \lt 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. 24 25 What is the maximum length of a subarray Luca can choose so he doesn't get caught? 26 27 $^{\dagger}$ $x$ is divisible by $y$ if the ratio $\frac{x}{y}$ is an integer. 28 29 Input 30 31 The first line contains a single integer $t$ ($1 \leq t \leq 1000$) — the number of test cases. 32 33 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. 34 35 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. 36 37 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. 38 39 The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 40 41 Output 42 43 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. 44 45 Example 46 47 Input 48 49 ``` 50 5 51 52 5 12 53 54 3 2 4 1 8 55 56 4 4 2 4 1 57 58 4 8 59 60 5 4 1 2 61 62 6 2 3 1 63 64 3 12 65 66 7 9 10 67 68 2 2 4 69 70 1 10 71 72 11 73 74 1 75 76 7 10 77 78 2 6 3 1 5 10 6 79 80 72 24 24 12 4 4 2 81 ``` 82 83 Output 84 85 ``` 86 3 87 2 88 1 89 0 90 3 91 ``` 92 93 Note 94 95 In the first test case, Luca can select the subarray with $l=1$ and $r=3$. 96 97 In the second test case, Luca can select the subarray with $l=3$ and $r=4$. 98 99 In the third test case, Luca can select the subarray with $l=2$ and $r=2$.