codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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