Oh, so sorry that I was not able to find the editorial.
// I AM TRYING TO DEBUGGING MY CODE FROM LAST 2 HRS BUT NOT ABLE THAT WHERE I AM WRONG .PLEASE SOMEONE HELP ME! THNX
import java.util.*;
import java.lang.*;
public class Main
{
static int[][] arr ;
static int[][] dp ;
static int n,m,k,c0,c1 ;
public static boolean check(int a)
{
if(a*a > c0)return false ;
for(int i = 1 ; i <= n-a+1 ;i++)
{
for(int j = 1 ; j <= m-a+1 ;j++)
{
int x = i+a-1 ;int y = j+a-1 ;
int val1 = dp[x][y] ;
int val2 = dp[i-1][j-1] ;
int val3 = dp[i-1][y] ;
int val4 = dp[x][j-1] ;
int val = val1 -val3-val4+val2 ;
val = (a*a) -val ;
if(val <= k)return true ;
}
}
return false ;
}
public static void solve()
{
Scanner scn = new Scanner(System.in) ;
int testcase = 1;
testcase = scn.nextInt() ;
for(int testcases =1 ; testcases <= testcase ;testcases++)
{
n= scn.nextInt() ; m= scn.nextInt() ; k= scn.nextInt() ;
arr = new int[n+10][m+10] ;dp = new int[n+10][m+10] ;
for(int i = 1 ; i <= n ;i++)
{
String s = scn.next() ;
s= "%" + s ;
for(int j = 1 ; j <= m ;j++)
{
if(s.charAt(j) == '1')arr[i][j] = 1;
else arr[i][j] = 0 ;
if(arr[i][j] == 0)c0++ ;
else c1++ ;
}
}
if(arr[1][1] == 0)dp[1][1] =1 ;
else dp[1][1] =0;
for(int j = 2 ; j <= m;j++)
{
dp[1][j] = dp[1][j-1] ;
if(arr[1][j] == 0)dp[1][j]++ ;
}
for(int i = 2 ; i <= n;i++)
{
dp[i][1] = dp[i-1][1] ;
if(arr[i][1] == 0)dp[i][1]++ ;
}
for(int i = 2 ; i <= n ; i++)
{
for(int j = 2; j <= m ;j++)
{
dp[i][j] = dp[i-1][j] + dp[i][j-1] -dp[i-1][j-1] ;
if(arr[i][j] == 0)dp[i][j]++ ;
}
}
int s = 0 ;int e = Math.min(n,m) ;
int ans = 0 ;
while(s <= e)
{
int m = (s+e)/2 ;
if(check(m))
{
ans = m ;
s=m+1 ;
}
else{
e=m-1 ;
}
}
System.out.println(ans) ;
}
}
public static void main (String[] args) throws java.lang.Exception
{
solve() ;
}
}
IT CAN LOOK A BIT LARGE AT FIRST GLANCE BUT IT IS SAME ,CHECK Fn CHECKING THE CONDITION AND REST JUST PREFIX CALCULATION .
For calculating mid. The best practice is to use mid = r-l / 2 + l
This will prevent overflow in case of l+r
Read it you will never screw again.
Thanks a lot for sharing this!!
Oh I see you have gained a star, congrats on being 5 star cube. 
Thank you taran for also providing links to get more information about the 2-D prefix sum.
What about this test case-
1 1 1
Hey there, I think we can also reduce the factor of log2() from time complexity.
Please correct me if I am wrong.
Idea
we can search for a square from a given vertex in increasing order.
i.e. if MAX sq. size of p is founded till now, then it needs not search for a size smaller than p.
I guess it’s time complexity will be o(n*m+min(n,m));
My code
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define fast_io ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define read(a) ll a; cin >> a;
#define ll long long int
#define endl '\n';
ll aux[1005][1005];
ll mat[1005][1005];
ll sumQuery(int tli, int tlj, int rbi,int rbj)
{
int res = aux[rbi][rbj];
if (tli > 0) res = res - aux[tli-1][rbj];
if (tlj > 0) res = res - aux[rbi][tlj-1];
if (tli > 0 && tlj > 0) res = res + aux[tli-1][tlj-1];
return res;
}
int main()
{
fast_io;
//“Don’t wish it were easier. Wish you were better.” – Jim Rohn;
read(t);
while(t--)
{
ll cnt=0;
ll m,n,k; cin>>m>>n>>k;
char c;
FOR(i,0,m-1) FOR(j,0,n-1)
{
cin>>c;
if(c=='1') mat[i][j]=1;
else cnt++,mat[i][j]=0;
aux[i][j]=0;
}
FOR(i,0,n-1) aux[0][i] = mat[0][i];
FOR(i,1,m-1) FOR(j,0,n-1) aux[i][j] = mat[i][j] + aux[i-1][j];
FOR(i,0,m-1) FOR(j,1,n-1)aux[i][j] += aux[i][j-1];
ll sq_size=0;
FOR(i,0,m-1) FOR(j,0,n-1) FOR(p,sq_size+1,min(n,m))
{
if(i+p-1>m-1 or j+p-1>n-1) break;
ll sum=sumQuery(i,j,i+p-1,j+p-1);
if(sum<=k and p*p<=cnt) sq_size++;
else break;
}
cout<<sq_size<<endl;
}
}
That case is really rare. How many time have you used long long r = 2e18 or int r = 2e9?
Nice Question
Nice question with great explanation 
why take a chance
in a contest where there could be a penalty for the wrong submissions
leetcode.com is an interview preparation website. That question is specifically designed so that you know how to calculate mid without overflow.
can anyone help me out in the second test case…
Here is my code…