All Tracks>Algorithms> Greedy Algorithms> Basics of Greedy Algorithms> Problem
Zero subarray
★★★★★

4.3

32 votes
Algorithms, Basics of Greedy Algorithms, C++, Greedy Algorithms
Problem

Given an array A of N elements. You can apply the given operations on array A.

  • Type 1: Choose an index i (1 ≤ i ≤ N) and set A[i] = A[i] - 1.
  • Type 2: Choose an index i (1 ≤ i ≤ N) and set A[i] = 0.

Find the maximum length subarray in array ​A​​​​​​ where all the elements in the subarray is 0 by using at most X operations of Type 1 and Y operations of Type 2.

Note

  • Assume 1-based indexing.

Input

  • The first line contains an integer T denoting the number of test cases.
  • For each test case:
    • The first line contains 3 space-separated integers N, X, Y.
    • Next line contains N space-separated integers denoting the elements of array A.

Output

For each test case in a new line, print the maximum length subarray in A where all the elements in the subarray is 0. 

Constraints

1≤T≤51≤N≤1050≤X≤10140≤Y≤1090≤A[i]≤109

 

Time Limit: 5
Memory Limit: 256
Source Limit:
Explanation
  • Apply operation of Type 2 on index 2, array A becomes [4,0,0,1].
  • Apply operation of Type 1 on index 4, array A becomes [4,0,0,0].
  • Subarray A[2..4], contains all elements as 0.
  • Thus, 3 is the required answer.
Editor Image

?