Chef and Parking Solution

Problem

Chef usually parks his car in a parking lot. Given a binary string $S$ of length $30$, if $S_i$ = '1', then it denotes that on the $i$-th day Chef parked his car in the parking lot and if $S_i$ = '0', then it denotes that Chef didn't use the parking lot. The cost of parking the car for a single day in the parking lot is Rs $A$.

Additionally, the longest parking streak (when Chef parks his car for consevutive days) is determined, and an additional Rs $B$ is charged for every day of the longest streak. If there are multiple longest streaks, then only one streak is considered for additional pay.

Determine the total bill that Chef has to pay.

Input Format

• The first line contains an integer $T$ denoting the number of test cases. The $T$ test cases then follow.
• The first line of each test case contains $A$ and $B$.
• The second line contains a binary string (it contains only '0' / '1').

Output Format

For each test case, output in a single line answer to the problem.

Constraints

• $1 \leq T \leq 10^4$
• $1 \leq A \leq 999$
• $1 \leq B \leq 999$
• $|S| = 30$

Sample 1:

Input

Output

2
4 5
101101010111101110000011101011
7 1
111000110101001010111100111101

92
130

Explanation:

Testcase $1$: Chef parks his car for $18$ days. Thus parking cost is $18 * 4 = 72$. The longest streak is $4$ days. Thus additional cost is $4 * 5 = 20$. Hence total parking cost comes out to be Rs $72 + 20 = 92$.

Program :

 /* package codechef; // don't place package name! */

import java.util.*;

import java.lang.*;

import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */

class Codechef

{

public static void main (String[] args) throws java.lang.Exception

{

// your code goes here

Scanner sc=new Scanner(System.in);

int t,n,a,b,i,oc,zc,c1,c2,j,occ;

String s;

t=sc.nextInt();

while(t-->0)

{

    zc=0;oc=0;c1=0;c2=0;occ=0;

    a=sc.nextInt();

    b=sc.nextInt();

    s=sc.next();

    for(i=0;i<s.length();i++)

    {

        if(s.charAt(i)==48)

            zc++;

        else if(s.charAt(i)==49)

            oc++;

    }

    c1=oc*a;

    int op=0,count=0; 

    for(i = 0;i<s.length();i++) 

    { 

if(s.charAt(i)=='1') 

{ 

count++; 

if(count > op) 

op = count; 

} 

else 

count = 0; 

    } 

    c2=op*b;

    System.out.println(c1+c2); 

}

}

}