Read it you will never screw again.
2 Likes
Thanks a lot for sharing this!!
Oh I see you have gained a star, congrats on being 5 star cube. 
1 Like
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
2 Likes
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…