Pagini recente » Cod sursa (job #1721609) | Cod sursa (job #962465) | Cod sursa (job #3133472) | Cod sursa (job #2587476) | Cod sursa (job #2576130)
#include <fstream>
#include <stack>
#include <cstring>
//#include <iostream>
using namespace std;
ifstream cin("bmatrix.in");
ofstream cout("bmatrix.out");
stack<int> s;
string pula;
int m,n,v[505][505],st[505],dr[505],h[505],d1[505],d2[505],d3[505],d4[505],rasp;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>pula;
for(int j=0;j<m;j++){
v[i][j+1]=pula[j]-'0';
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(v[i][j]==0){
h[j]++;
}
else
h[j]=0;
}
while(s.size()>0){
s.pop();
}
for(int j=1;j<=m;j++){
while(s.size()>0 && h[j]<=h[s.top()]){
s.pop();
}
if(s.size()==0){
st[j]=0;
}
else{
st[j]=s.top();
}
s.push(j);
}
while(s.size()>0){
s.pop();
}
for(int j=m;j>0;j--){
while(s.size()>0 && h[j]<=h[s.top()]){
s.pop();
}
if(s.size()==0){
dr[j]=m+1;
}
else{
dr[j]=s.top();
}
s.push(j);
}
for(int j=1;j<=m;j++){
d1[i]=max(d1[i],max(h[j],(dr[j]-st[j]-1)*h[j]));
}
d1[i]=max(d1[i],d1[i-1]);
}
for(int i=1;i<=m;i++){
h[i]=0;
}
while(s.size()>0){
s.pop();
}
rasp=0;
for(int i=n;i>0;i--){
for(int j=1;j<=m;j++){
if(v[i][j]==0){
h[j]++;
}
else
h[j]=0;
}
while(s.size()>0){
s.pop();
}
for(int j=1;j<=m;j++){
while(s.size()>0 && h[j]<=h[s.top()]){
s.pop();
}
if(s.size()==0){
st[j]=0;
}
else{
st[j]=s.top();
}
s.push(j);
}
while(s.size()>0){
s.pop();
}
for(int j=m;j>0;j--){
while(s.size()>0 && h[j]<=h[s.top()]){
s.pop();
}
if(s.size()==0){
dr[j]=m+1;
}
else{
dr[j]=s.top();
}
s.push(j);
}
for(int j=1;j<=m;j++){
d2[i]=max(d2[i],max(h[j],(dr[j]-st[j]-1)*h[j]));
}
d2[i]=max(d2[i],d2[i-1]);
}
for(int i=1;i<=m;i++){
h[i]=0;
}
while(s.size()>0){
s.pop();
}
rasp=0;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(v[j][i]==0){
h[j]++;
}
else
h[j]=0;
}
while(s.size()>0){
s.pop();
}
for(int j=1;j<=n;j++){
while(s.size()>0 && h[j]<=h[s.top()]){
s.pop();
}
if(s.size()==0){
st[j]=0;
}
else{
st[j]=s.top();
}
s.push(j);
}
while(s.size()>0){
s.pop();
}
for(int j=n;j>0;j--){
while(s.size()>0 && h[j]<=h[s.top()]){
s.pop();
}
if(s.size()==0){
dr[j]=n+1;
}
else{
dr[j]=s.top();
}
s.push(j);
}
for(int j=1;j<=n;j++){
d3[i]=max(d3[i],max(h[j],(dr[j]-st[j]-1)*h[j]));
}
d3[i]=max(d3[i],d3[i-1]);
}
for(int i=1;i<=n;i++){
h[i]=0;
}
while(s.size()>0){
s.pop();
}
rasp=0;
for(int i=m;i>0;i--){
for(int j=1;j<=n;j++){
if(v[j][i]==0){
h[j]++;
}
else
h[j]=0;
}
while(s.size()>0){
s.pop();
}
for(int j=1;j<=n;j++){
while(s.size()>0 && h[j]<=h[s.top()]){
s.pop();
}
if(s.size()==0){
st[j]=0;
}
else{
st[j]=s.top();
}
s.push(j);
}
while(s.size()>0){
s.pop();
}
for(int j=n;j>0;j--){
while(s.size()>0 && h[j]<=h[s.top()]){
s.pop();
}
if(s.size()==0){
dr[j]=n+1;
}
else{
dr[j]=s.top();
}
s.push(j);
}
for(int j=1;j<=n;j++){
d4[i]=max(d4[i],max(h[j],(dr[j]-st[j]-1)*h[j]));
}
d4[i]=max(d4[i],d4[i-1]);
}
rasp=0;
for(int i=1;i<=n;i++){
rasp=max(rasp,d1[i]+d2[i+1]);
}
for(int i=1;i<=m;i++){
rasp=max(rasp,d3[i]+d4[i+1]);
}
cout<<rasp;
return 0;
}