CF1873F Money Trees

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.

N/A

N/A

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 $ .