Chef and Surprise Chessboard

All submissions for this problem are available.
###Read problems statements [Hindi](http://www.codechef.com/download/translated/OCT18/hindi/SURCHESS.pdf) ,[Bengali](http://www.codechef.com/download/translated/OCT18/bengali/SURCHESS.pdf) , [Mandarin chinese](http://www.codechef.com/download/translated/OCT18/mandarin/SURCHESS.pdf) , [Russian](http://www.codechef.com/download/translated/OCT18/russian/SURCHESS.pdf) and [Vietnamese](http://www.codechef.com/download/translated/OCT18/vietnamese/SURCHESS.pdf) as well. Chef loves to play chess, so he bought a new chessboard with width $M$ and height $N$ recently. Chef considers a chessboard *correct* if its width (number of columns) is equal to its height (number of rows) and each cell has no sideadjacent cell of the same color (this is the socalled "chess order" which you can see in realworld chessboards). Chef's chessboard does not have to be a correct chessboard (in particular, it may have $N \neq M$). A *subboard* of Chef's chessboard is a rectangular piece of this board with an arbitrarily chosen top left and bottom right cell (possibly equal to the original chessboard). Every subboard is also a chessboard. Chef can invert some cells; inverting a cell means changing its color from white to black or from black to white. After inverting those cells, he wants to cut the maximum correct subboard out of the original chessboard. Chef has not yet decided how many cells he would like to invert. Now he wonders about the answers to $Q$ question. In the $i$th question ($1 \le i \le Q$), he is allowed to invert at most $c_i$ cells (possibly zero); he would like to know the side length of the largest possible correct subboard of his chessboard. Help Chef answer these questions. ### Input  The first line of the input contains two spaceseparated integers $N$ and $M$.  $N$ lines follow. For each valid $i$, the $i$th of these lines contains a string with length $M$ describing the $i$th row of Chef's chessboard. Each character of this string is either '0', representing a black cell, or '1', representing a white cell.  The next line contains a single integer $Q$.  The last line contains $Q$ spaceseparated integers $c_1, c_2, \dots, c_Q$. ### Output For each question, print a single line containing one integer — the maximum size of a correct subboard. ### Constraints  $1 \le N, M \le 200$  $1 \le Q \le 10^5$  $0 \le c_i \le 10^9$ for each valid $i$ ### Subtasks **Subtask #1 (20 points):**  $1 \le N, M \le 20$  $1 \le Q \le 100$ **Subtask #2 (30 points):** $1 \le N, M \le 20$ **Subtask #3 (50 points):** original constraints ### Example Input ``` 8 8 00101010 00010101 10101010 01010101 10101010 01010101 10101010 01010101 4 1 2 0 1001 ``` ### Example Output ``` 7 8 6 8 ``` ### Explanation If we don't change the board, the best answer here is the 6x6 bottom right subboard. We can invert cells $(2, 2)$ and $(1, 1)$ to get a better answer.Author:  izaron 
Editorial  https://discuss.codechef.com/problems/SURCHESS 
Tags  easymedium, izaron, oct18, prefixsum 
Date Added:  16092018 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions