#pragma GCC optimize("Ofast")
#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 = 2501;
string a[mxn];
int dp[2][mxn][mxn];
int w[mxn];
int att[mxn];
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, m; cin >> n >> m;
F0R(i,n)cin>>a[i];
int mw = INT_MAX;
F0R(j,m){
F0R(i,n)if(a[i][j]=='1'){
dp[0][i][j]=1;
if(i)dp[0][i][j] += dp[0][i-1][j];
}
R0F(i,n)if(a[i][j]=='1'){
dp[1][i][j]=1;
if(i<n-1)dp[1][i][j] += dp[1][i+1][j];
}
F0R(i,n){
if(a[i][j]=='1')att[i]++;
else {
if(att[i])mw=min(mw,att[i]);
att[i]=0;
}
}
}
F0R(j,m)if(att[j])mw=min(mw,att[j]);
int mh=INT_MAX;
F0R(i,n)F0R(j,m)if(a[i][j]=='1')mh=min(mh,dp[0][i][j]+dp[1][i][j]-1);
/*F0R(i,n){
F0R(j,m)cout<<dp[1][i][j]<<' ';cout<<endl;
}
cout << mw << ' ' << mh << endl;*/
fill_n(w,mw+1,mh);
F0R(i,n){
int ln=0,ma=INT_MAX,mb=INT_MAX;
F0R(j,m){
if (a[i][j]=='1'){
ln++,ma=min(ma,dp[0][i][j]),mb=min(mb,dp[1][i][j]);
w[ln]=min(w[ln],ma+mb-1);
}else ln=0;
}
}
int ans=0;
F0R(i,mw+1)ans=max(ans,i*w[i]);
cout << ans << endl;
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |