Sphere online judge repair road

After the earthquake, many road were damaged. Each road has some blocks were damaged, so vehicles cannot move on these blocks. To ensure the traffic network is connected, they need to repair those roads. For each road, to repair 1 block, they need 1 unit of money. So if a road has M blocks are damaged, then they need M unit of money. However, too many roads were damaged, they only have K unit of money to repair a specific road. Then with K unit of money, they wish to repair the road such that the number of consecutive blocks that vehicles can move on is maximum.

For example, the following is a road with 11 blocks, there are 4 blocks need to repair are marked in gray color (block 2, 3, 6 and 8).

If they have only 2 unit of money to repair this road, to get maximum the number of consecutive blocks that vehicles can move on after repair, they must to repair the block 6 and 8, then the vehicles can move from block 4 to block 11, and the length is 8.

Given a status of road, print out the maximum consecutive blocks that vehicles can move on after repair with maximum K unit of money. The answer for the above example should be 8.

Input

The total number of test cases T (1  T ) will be given the in the first line.

Each test case will be given in the following 2 lines, the first line of each test case is a number of blocks of the roadN (5 <= N <= 10000) and a number K (0 <= K <= N) separated by a space. The next line is the status of road, those blocks were damaged are indicated with ‘0’ and those not are indicated with ‘1’. Adjacent blocks in the same line are separated with a blank space.

Output

Print the answer for each test case on 1 line.

Spoj Link : http://www.spoj.com/problems/REPROAD/

Sample

Solution in cpp using sliding window approach :

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>

#define INT_MIN -999999

using namespace std;

// O(n) solution using sliding window strategy maintaining starting and ending pointer
void maxConsBlocks (int *str1, int m, int n)
{

int temp[m] ;
int sInd= 0 , eInd=-1,j=0,max=INT_MIN;
if(n==0) //Problem reduces to max consecutive number of one’s
{
int count=0;
for(int i=0 ; i < m ; i++)
{
if(str1[i] ==1)
count++;
else
{
if(count > max)
max=count;
count=0;
}
}
if(count > max)
max=count;
cout << max <<endl;
return;

}

for(int i=0 ; i < m ; i++)
{
if(str1[i] ==1)
eInd++;
else if(str1[i] ==0 )
{
j++; // j counts number of 0 , shouldn’t be greater than n
if(j > n)
{
eInd++;
if(eInd -sInd > max)
max= eInd-sInd;

while(str1[sInd] !=0 )
{
sInd++;
}
if(eInd -sInd > max)
max= eInd-sInd;
sInd++;
j–; // Since excluded zero at the start of window
}
else{
eInd++;
if(j==n)
{
if((eInd – sInd +1) > max)
max= eInd-sInd+1;
}
}
}
}
if((eInd – sInd+1) > max)
max= eInd-sInd+1;
cout << max <<endl;
}

int main()
{
int t=0;
cin >> t;
for(int i=0 ; i < t ; i++)
{
int m ,n;
cin >> m >> n;
int str1[m];
for(int i =0 ; i <m ; i++)
cin >> str1[i];
maxConsBlocks (str1, m, n);
}
return 0;
}