#include "bits/stdc++.h"
#define FOR(i,a,b)for(int i=(a);i<(b);i++)
#define F0R(i,a)FOR(i,0,a)
#define ROF(i,a,b)for(int i=(b)-1;i>=(a);i--)
#define R0F(i,a)ROF(i,0,a)
#define REP(a)F0R(_,a)
using namespace std;
const int mxn = 2500;
short dp[4][mxn][mxn];
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
vector<string> a;
int n, m; cin >> n >> m;
F0R(i,n){
string s; cin >> s;
a.push_back(s);
}
F0R(i,n){
F0R(j,m){
if (a[i][j]=='1')dp[0][i][j]=dp[1][i][j]=dp[2][i][j]=dp[3][i][j]=1;
if (a[i][j]=='1'){
if (i)dp[0][i][j]+=dp[0][i-1][j];
if (j)dp[1][i][j]+=dp[1][i][j-1];
}
}
R0F(j,m){
if (a[i][j]=='1' and j<m-1)dp[3][i][j]+=dp[3][i][j+1];
}
}
R0F(i,n){
F0R(j,m){
if (a[i][j]=='1' and i<n-1)dp[2][i][j]+=dp[2][i+1][j];
}
}
int mh = mxn, mw = mxn;
/*F0R(i,n){
F0R(j,n)cout<<dp[1][i][j]<<' ';cout<<endl;
}*/
F0R(i,n)F0R(j,m)if(a[i][j]=='1')
mh = min(mh, dp[0][i][j]+dp[2][i][j]-1), mw=min(mw,dp[1][i][j]+dp[3][i][j]-1);
//cout << "mw: " << mw << "; " << "mh: " << mh << endl;
int mmh = mh;
F0R(i,n){
multiset<int>c,d;
F0R(j,m){
if (a[i][j]=='1'){
c.insert(i-dp[0][i][j]+1);
d.insert(i+dp[2][i][j]-1);
}else{
c.clear();
d.clear();
}
if (c.size() == mw){
mmh = min(mmh, *d.begin()-*c.rbegin()+1);
c.erase(c.find(i-dp[0][i][j-mw+1]+1));
d.erase(d.find(i+dp[2][i][j-mw+1]-1));
}
}
}
int mmw = mw;
F0R(i,m){
multiset<int> c,d;
F0R(j,n){
if(a[j][i]=='1'){
c.insert(i-dp[1][j][i]+1);
d.insert(i+dp[3][j][i]-1);
//cout << j << ' ' << i << "; " << i-dp[1][j][i]+1 << ' ' << i+dp[3][j][i]-1<<endl;
}else{
c.clear();
d.clear();
}
if (c.size()==mh){
mmw = min(mmw, *d.begin()-*c.rbegin()+1);
//cout << j << ' ' << i << ": " << (*d.begin()-*c.rbegin()+1)<<endl;
c.erase(c.find(i-dp[1][j-mh+1][i]+1));
d.erase(d.find(i+dp[3][j-mh+1][i]-1));
}
}
}
//cout << mw << ' ' << mmh << "; " << mh << ' ' << mmw << endl;
cout << max(mw * mmh, mh * mmw) << '\n';
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |