# Maximize 1s Codechef Solution

### We Are Discuss About CODECHEF SOLUTION

Maximize 1s Codechef Solution

## Problem

You are given a binary string S. You are allowed to perform the following operation at most once:

• Pick some substring of S
• Flip all the values in this substring, i.e, convert 0 to 1 and vice versa

For example, if S = 1\underline{00101}011, you can pick the underlined substring and flip it to obtain S = 1\underline{11010}011.

For the substring of S consisting of all the positions from L to R, we define a function f(L, R) to be the number of 1‘s in this substring. For example, if S = 100101011, then f(2, 5) = 1 and f(4, 9) = 4 (the respective substrings are 0010 and 101011).

If you perform the given operation optimally, find the maximum possible value of

\sum_{L=1}^N \sum_{R=L}^N f(L, R)

that can be obtained. Note that the substring flip operation can be performed at most once.

### Input Format

• The first line of input will contain a single integer T, denoting the number of test cases.
• Each test case consists of single line of input, containing a binary string S.

### Output Format

For each test case, output on a new line the maximum possible value of \sum_{L=1}^N \sum_{R=L}^N f(L, R) that can be obtained.

### Constraints

• 1 \leq T \leq 10^5
• 1 \leq |S| \leq 3\cdot 10^5
• The sum of |S| over all test cases won’t exceed 3\cdot 10^5.

### Sample 1:

Input

Output

3
111
000
00100
10
10
26

### Explanation:

Test case 1: There is no need to apply the operation since everything is already a 1. The answer is thus the sum of:

• f(1, 1) = 1
• f(1, 2) = 2
• f(1, 3) = 3
• f(2, 2) = 1
• f(2, 3) = 2
• f(3, 3) = 1

which is 10.

Test case 2: Flip the entire string to obtain 111, whose answer has been computed above.

Test case 3: Flip the entire string to obtain 11011. The sum of f(L, R) across all substrings is now 26, which is the maximum possible.

## Maximize 1s Codechef Solution

Yhaa You have done it but next? if YOU Want to Get Others Please Visit Here JOIN NOW