Pagini recente » Cod sursa (job #1041353) | Cod sursa (job #2153141) | Cod sursa (job #2455643) | Cod sursa (job #2694064) | Cod sursa (job #1191176)
#include<fstream>
using namespace std;
struct element
{
int val,poz;
};
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
const int NMAX = 205;
int n,m,a[NMAX][NMAX],sumepart[NMAX][NMAX],dp[NMAX][NMAX],aux[NMAX][NMAX];
int b[NMAX],c[NMAX];
char s[NMAX];
int S;
int sumes[NMAX],sumej[NMAX];
element deq[NMAX];
inline void Citire()
{
fin>>n>>m;
for (int i=1;i<=n;i++)
{
fin>>(s+1);
for (int j=1;j<=m;j++)
a[i][j]=s[j]-'0';
}
}
inline void Preprocess()
{
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;i--)
for (j=1;j<=m;j++)
if (!a[i][j]) dp[i][j]=dp[i+1][j]+1;
}
inline void D_E(int linia,int mat[NMAX][NMAX])
{
int j,ul;
for (j=0;j<=NMAX;j++) b[j]=c[j]=deq[j].val=deq[j].poz=0;
ul=0;deq[0].poz=0;
for (j=1;j<=m;j++)
if (mat[linia][j])
{
while (ul>=1 && mat[linia][j]<=deq[ul].val) ul--;
ul++;
deq[ul].val=mat[linia][j];
deq[ul].poz=j;
b[j]=deq[ul-1].poz+1;
}
else {ul=0;deq[ul].poz=j;}
ul=0;deq[0].poz=m+1;
for (j=m;j;j--)
if (mat[linia][j])
{
while (ul>=1 && mat[linia][j]<=deq[ul].val) ul--;
ul++;
deq[ul].val=mat[linia][j];
deq[ul].poz=j;
c[j]=deq[ul-1].poz-1;
}
else {ul=0;deq[ul].poz=j;}
}
inline void Rezolva()
{
int i,j;
for (i=1;i<=n;i++)
{
D_E(i,sumepart);
sumes[i]=sumes[i-1];
for (j=1;j<=m;j++)
sumes[i]=max(sumes[i],(c[j]-b[j]+1)*sumepart[i][j]);
}
for (i=n;i;i--)
{
D_E(i,dp);
sumej[i]=sumej[i+1];
for (j=1;j<=m;j++)
sumej[i]=max(sumej[i],(c[j]-b[j]+1)*dp[i][j]);
}
}
inline void Rotate()
{
int i,j,l;
for (j=1;j<=m;j++)
for (i=n;i;i--)
aux[j][n-i+1]=a[i][j];
for (i=1;i<=n;i++)
{
sumes[i]=sumej[i]=0;
for (j=1;j<=m;j++) sumepart[i][j]=dp[i][j]=0;
}
swap(n,m);
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
a[i][j]=aux[i][j];
}
int main()
{
int i;
Citire();
Preprocess();
Rezolva();
for (i=1;i<n;i++) S=max(S,sumes[i]+sumej[i+1]);
Rotate();
Preprocess();
Rezolva();
for (i=1;i<n;i++) S=max(S,sumes[i]+sumej[i+1]);
fout<<S<<"\n";
return 0;
}