Pagini recente » Cod sursa (job #1484764) | Istoria paginii runda/ktmalx_93/clasament | Cod sursa (job #984525) | Cod sursa (job #1304944) | Cod sursa (job #993882)
Cod sursa(job #993882)
#include <fstream>
#include <cstring>
#include <stack>
using namespace std;
stack<int> stiva;
int v[205];
int st[205];
int dr[205];
inline void clear(int k)
{
int i;
for(i=0;i<k;i++)
v[i]=0;
}
inline int maxim(int a,int b)
{
if(a>b)
return a;
return b;
}
int calc(int k)
{
int i;
while(!stiva.empty())
stiva.pop();
int varf;
for(i=0;i<k;i++)
{
while(!stiva.empty())
if(v[stiva.top()]>=v[i])
stiva.pop();
else
break;
if(stiva.empty())
varf=-1;
else
varf=stiva.top();
st[i]=i-varf;
stiva.push(i);
}
/////////////////////////////
while(!stiva.empty())
stiva.pop();
for(i=k-1;i>=0;i--)
{
while(!stiva.empty())
if(v[stiva.top()]>=v[i])
stiva.pop();
else
break;
if(stiva.empty())
varf=k;
else
varf=stiva.top();
dr[i]=varf-i;
stiva.push(i);
}
int maxim=-1;
for(i=0;i<k;i++)
{
st[i]+=dr[i],st[i]--,st[i]*=v[i];
if(st[i]>maxim)
maxim=st[i];
}
return maxim;
}
int main()
{
ifstream cin("bmatrix.in");
ofstream cout("bmatrix.out");
int n=0,m=0,i,j,mat[205][205];
cin>>n>>m;
cin.get();
char sir[205];
for(i=0;i<n;i++)
{
cin.get(sir,205);
cin.get();
for(j=0;j<m;j++)
{
mat[i][j]=1-(sir[j]-'0');
}
}
int sus[205],jos[205],st[205],dr[205];
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
v[j]=(mat[i][j])?(v[j]+1):0;
sus[i]=maxim(calc(m),((i>0)?(sus[i-1]):(0)));
}
clear(m);
for(i=n-1;i>=0;i--)
{
for(j=0;j<m;j++)
v[j]=(mat[i][j])?(v[j]+1):0;
jos[i]=maxim(calc(m),((i<(n-1))?(jos[i+1]):(0)));
}
int global=-1,aux;
for(i=1;i<n;i++)
{
aux=sus[i-1]+jos[i];
if(aux>global)
global=aux;
}
clear(m);
/////////////////////////////////////////
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
v[j]=(mat[j][i])?(v[j]+1):0;
st[i]=calc(n);
st[i]=maxim(calc(n),((i>0)?(st[i-1]):(0)));
}
clear(n);
for(i=m-1;i>=0;i--)
{
for(j=0;j<n;j++)
v[j]=(mat[j][i])?(v[j]+1):0;
dr[i]=calc(n);
dr[i]=maxim(calc(n),((i<(m-1))?(dr[i+1]):(0)));
}
for(i=1;i<m;i++)
{
aux=st[i-1]+dr[i];
if(aux>global)
global=aux;
}
cout<<global<<'\n';
// for(i=0;i<n;i++)
// {
// cout<<sus[i]<<' '<<jos[i]<<endl;
// }
// cout<<"stop"<<m<<endl;
//for(j=0;j<m;j++)
//{
// cout<<st[j]<<' '<<dr[j]<<endl;
// }
//system("PAUSE");
cin.close();
cout.close();
return 0;
}