CODE
// #include<bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <string>
#include <cstring>
#include <random>
#include <bitset>
using namespace std;
#define vt vector
#define ar array
#define sz(a) (int)a.size()
#define ll long long
// debugger credits: https://codeforces.com/blog/entry/68809
//#pragma GCC optimize "trapv"
#define F_OR(i, a, b, s) for (int i = (a); ((s) > 0 ? i < (b) : i > (b)); i += (s))
#define F_OR1(e) F_OR(i, 0, e, 1)
#define F_OR2(i, e) F_OR(i, 0, e, 1)
#define F_OR3(i, b, e) F_OR(i, b, e, 1)
#define F_OR4(i, b, e, s) F_OR(i, b, e, s)
#define GET5(a, b, c, d, e, ...) e
#define F_ORC(...) GET5(__VA_ARGS__, F_OR4, F_OR3, F_OR2, F_OR1)
#define FOR(...) F_ORC(__VA_ARGS__)(__VA_ARGS__)
#define EACH(x, a) for (auto& x: a)
template<class T> bool umin(T& a, const T& b) {
return b<a?a=b, 1:0;
}
template<class T> bool umax(T& a, const T& b) {
return a<b?a=b, 1:0;
}
template<class A> void read(vt<A>& v);
template<class A, size_t S> void read(ar<A, S>& a);
template<class T> void read(T& x) {
cin >> x;
}
void read(double& d) {
string t;
read(t);
d=stod(t);
}
void read(long double& d) {
string t;
read(t);
d=stold(t);
}
template<class H, class... T> void read(H& h, T&... t) {
read(h);
read(t...);
}
template<class A> void read(vt<A>& x) {
EACH(a, x)
read(a);
}
template<class A, size_t S> void read(array<A, S>& x) {
EACH(a, x)
read(a);
}
const int mxN=1e5,di[4]={1,0,-1,0},dj[4]={0,-1,0,1};
void solve(){
int n,m,k ;
read(n,m,k) ;
vt<string>a(n) ;read(a) ;
vt<vt<int>>dp(n+2,vt<int>(m+2)),dp2(n+2,vt<int>(m+2));
int c=0 ;
FOR(i,1,n+1)
FOR(j,1,m+1){
c+=a[i-1][j-1]=='0' ;
dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+(a[i-1][j-1]=='1') ;
dp2[i][j]=dp2[i-1][j]+dp2[i][j-1]-dp2[i-1][j-1]+(a[i-1][j-1]=='0') ;
}
int ans = -1 ;
FOR(i,1,n+1)
FOR(j,1,m+1){
int lb=1,rb=min(n-i+1,m-j+1) ;
while(lb<=rb){
int mb=(lb+rb)/2 ;
int lx=i,ly=j ;
int rx=min(i+mb-1,n),ry=min(j+mb-1,m) ;
int A=dp[rx][ry]-dp[rx][ly-1]-dp[lx-1][ry]+dp[lx-1][ly-1] ;
int Z=dp2[rx][ry]-dp2[rx][ly-1]-dp2[lx-1][ry]+dp2[lx-1][ly-1] ;
Z=c-Z ;
bool ok=1 ;
if(A>Z)
ok=0 ;
if(A>k)
ok=0 ;
if(ok)
lb=mb+1 ;
else
rb=mb-1 ;
}
umax(ans,lb-1) ;
}
cout<<ans<<'\n';
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//cout << setprecision(20) << fixed ;
int T=1;
read(T);
FOR(_,T){
// pff("Case #", _+1, ": ");
solve();
}
return 0;
}
Now this one got accepted, I only changed the < to <= and rb=mb-1. I wish someone would’ve told this to me earlier. Thanks a ton!!
