Pagini recente » Cod sursa (job #437344) | Cod sursa (job #3002326) | Cod sursa (job #1913161) | Cod sursa (job #816665) | Cod sursa (job #1191115)
#include<fstream>
using namespace std;
struct nod
{
int val,nivel;
};
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
const int Nmax=205;
int n,m,sumepart[Nmax][Nmax],dp[Nmax][Nmax],dr[Nmax],st[Nmax],M;
bool a[Nmax][Nmax];
char s[205];
nod deq[Nmax];
inline void Citire()
{
int i,j;
fin>>n>>m;
for (i=1;i<=n;i++)
{
fin>>(s+1);
for (j=1;j<=m;j++)
a[i][j]=s[j]-'0';
}
}
inline void Preprocesare()
{
int i,j;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
if (!a[i][j]) sumepart[i][j]=sumepart[i-1][j]+1;
for (i=n;i>=1;i--)
for (j=1;j<=m;j++)
if (!a[i][j]) dp[i][j]=dp[i+1][j]+1;
}
inline void DEQ(int lin,int mat[Nmax][Nmax])
{
int j,ul;
for (j=0;j<=Nmax;j++) st[j]=dr[j]=deq[j].val=deq[j].nivel=0;
ul=0;
for (j=1;j<=m;j++)
if (mat[lin][j])
{
while (ul>=1 && mat[lin][j]<=deq[ul].val) ul--;
deq[++ul].val=mat[lin][j];
deq[ul].nivel=j;
st[j]=deq[ul-1].nivel+1;
}
else {ul=0;deq[0].nivel=j;}
ul=0;deq[0].nivel=m+1;
for (j=m;j;j--)
if (mat[lin][j])
{
while (ul>=1 && mat[lin][j]<=deq[ul].val) ul--;
deq[++ul].val=mat[lin][j];
deq[ul].nivel=j;
dr[j]=deq[ul-1].nivel-1;
}
else {ul=0;deq[0].nivel=j;}
}
inline void Rezolva()
{
int i,j,m1,m2;
for (i=1;i<n;i++)
{
m1=m2=0;
DEQ(i,sumepart);
for (j=1;j<=m;j++)
m1=max(m1,(dr[j]-st[j]+1)*sumepart[i][j]);
DEQ(i+1,dp);
for (j=1;j<=m;j++)
m2=max(m2,(dr[j]-st[j]+1)*dp[i+1][j]);
//fout<<m1<<" "<<m2<<"\n";
M=max(M,m1+m2);
}
}
int main()
{
Citire();
Preprocesare();
Rezolva();
fout<<M<<"\n";
return 0;
}