Pagini recente » Cod sursa (job #2537845) | Cod sursa (job #1960067) | Cod sursa (job #1720398) | Cod sursa (job #2616147) | Cod sursa (job #2435746)
#include<bits/stdc++.h>
#define maxim 210
using namespace std;
ifstream f("bmatrix.in");
ofstream g("bmatrix.out");
int n,m ;
char mat[maxim][maxim],aux[maxim][maxim];
int down[maxim] , max2[maxim];
int up[maxim];
int stiva[maxim];
int vf;
void start()
{
for (int i=n; i>=1; i--) // cati de 0 sunt sub el ( inceputul unei matrice)
{
stiva[0]=stiva[1]=0;
vf=1;
for (int j=1; j<=m+1; j++)
{
if (mat[i][j]=='1' || j == m+1 )
down[j]=0;
else
down[j]++;
if (down[stiva[vf]] == down[j])
stiva[vf]=j;
else
{
while (vf && down[stiva[vf]] > down[j])
{
max2[i]=max(max2[i], down[stiva[vf]]*(j-stiva [ vf-1 ]-1));
vf--;
}
stiva[++vf]=j;
}
}
// cout<<endl;
}
for (int i = n-1; i>=1; i-- )
max2[i]=max(max2[i],max2[i+1]); // matrice de arie max care incepe de la linia i in jos
/*for (int i=1; i<=n ;i++)
cout<<max2[i]<<'\n';
cout<<endl<<'\n'; */
}
int solve()
{
int ans=0;
for (int i=1; i<=n; i++)
{
stiva[0]=stiva[1]=0;
vf=1;
int arie1=0;
for (int j= 1; j<=m+1 ; j++)
{
if ( mat[i][j]=='1' || j == m+1 )
up[j]=0;
else
up[j]++;
if (up[stiva[vf]] == up[j])
stiva[vf]=j;
else
{
while (vf && up[stiva[vf]] > up[j])
{
arie1=max(arie1, up[stiva[vf]]* ( j - stiva [ vf-1 ]-1 ) );
vf--;
}
stiva[++vf]=j;
}
}
//cout<<i<<" "<<arie1<<endl;
ans=max(ans,arie1+max2[i+1]);
}
return ans;
}
int main()
{
int ANS=0;
f>>n>>m;
for (int i=1; i<=n ; i++)
for (int j=1; j<=m; j++)
f>>mat[i][j];
start();
ANS=solve();
memset(max2, 0, sizeof(max2));
for (int i=1 ; i<=m+1 ;i++)
up[i]=down[i]=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
aux[j][i]=mat[n-i+1][j];
swap(n,m);
for(int i=1;i<=n;i++)
for (int j = 1; j <= m; j++)
mat[i][j] = aux[i][j];
start();
g<<max(ANS,solve());
}