Pagini recente » Cod sursa (job #3131062) | Cod sursa (job #1024346) | Cod sursa (job #1852923) | Cod sursa (job #1416208) | Cod sursa (job #2689677)
#include <iostream>
#include <vector>
#include <cstring>
#include <stdio.h>
using namespace std;
int liniiArie(vector<int> l)
{
vector <int> stiva;
vector <int> left(l.size());
vector <int> right(l.size());
//right limit
stiva.push_back(0);
for(int i=1;i<l.size();i++)
{
if(l[i]>=l[stiva[stiva.size()-1]])
{
stiva.push_back(i);
}
else
{
while(!stiva.empty()&&l[i]<l[stiva[stiva.size()-1]])
{
right[stiva[stiva.size()-1]]=i;
stiva.pop_back();
}
stiva.push_back(i);
}
}
while(!stiva.empty())
{
right[stiva[stiva.size()-1]]=l.size();
stiva.pop_back();
}
stiva.clear();
//left limit
stiva.push_back(l.size()-1);
for(int i=l.size()-2;i>=0;i--)
{
if(l[i]>=l[stiva[stiva.size()-1]])
{
stiva.push_back(i);
}
else
{
while(!stiva.empty()&&l[i]<l[stiva[stiva.size()-1]])
{
left[stiva[stiva.size()-1]]=i;
stiva.pop_back();
}
stiva.push_back(i);
}
}
while(!stiva.empty())
{
left[stiva[stiva.size()-1]]=-1;
stiva.pop_back();
}
int res=0;
for(int i=0;i<l.size();i++)
{
int p=l[i]*(right[i]-left[i]-1);
if(p>res) res=p;
}
return res;
}
int bmatrix(vector<vector<int>> m, int n, int mm)
{
//a
vector<int> dmax;
vector<int> umax;
vector<int> lmax;
vector<int> rmax;
vector<int> lines; //nmax
//for dmax
for(int i=0;i<mm;i++) lines.push_back(0);
for(int i=0;i<n;i++)
{
for(int j=0;j<mm;j++)
{
if(m[i][j]==0) lines[j]++;
else lines[j]=0;
}
int nr=liniiArie(lines);
if(i==0) dmax.push_back(nr);
else dmax.push_back(dmax[dmax.size()-1]>nr?dmax[dmax.size()-1]:nr);
}
lines.clear();
//for umax
for(int i=0;i<mm;i++) lines.push_back(0);
for(int i=0;i<n;i++)
{
for(int j=0;j<mm;j++)
{
if(m[n-1-i][j]==0) lines[j]++;
else lines[j]=0;
}
int nr=liniiArie(lines);
if(i==0) umax.push_back(nr);
else umax.push_back(umax[umax.size()-1]>nr?umax[dmax.size()-1]:nr);
}
lines.clear();
//for lmax
for(int i=0;i<n;i++) lines.push_back(0);
for(int i=0;i<mm;i++)
{
for(int j=0;j<n;j++)
{
if(m[j][i]==0) lines[j]++;
else lines[j]=0;
}
int nr=liniiArie(lines);
if(i==0) lmax.push_back(nr);
else lmax.push_back(lmax[lmax.size()-1]>nr?lmax[lmax.size()-1]:nr);
}
lines.clear();
//for rmax
for(int i=0;i<n;i++) lines.push_back(0);
for(int i=0;i<mm;i++)
{
for(int j=0;j<n;j++)
{
if(m[j][mm-i-1]==0) lines[j]++;
else lines[j]=0;
}
int nr=liniiArie(lines);
if(i==0) rmax.push_back(nr);
else rmax.push_back(rmax[rmax.size()-1]>nr?rmax[rmax.size()-1]:nr);
}
lines.clear();
int mx=0;
for(int i=0;i<n-1;i++) if(umax[n-2-i]+dmax[i]>mx) {mx=umax[n-2-i]+dmax[i];}
for(int i=0;i<mm-1;i++) if(rmax[mm-2-i]+lmax[i]>mx) { mx=rmax[mm-2-i]+lmax[i];}
return mx;
}
int main()
{
freopen("bmatrix.in","r",stdin);
freopen("bmatrix.out","w",stdout);
int n,m;
cin>>n>>m;
vector <vector<int>> mx(n);
for(int i=0;i<n;i++)
{
char s[201];
cin>>s;
for(int j=0;j<m;j++)
if(s[j]=='0') mx[i].push_back(0);
else mx[i].push_back(1);
}
cout<<bmatrix(mx,n,m);
return 0;
}