Pagini recente » Cod sursa (job #2108688) | Cod sursa (job #2448754) | Cod sursa (job #1098797) | Cod sursa (job #1222841) | Cod sursa (job #1645753)
#include <fstream>
#include <string.h>
#define nMax 205
using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
int A[nMax][nMax], H[nMax][nMax], MaxDr[5][nMax], n, m, AUX[nMax][nMax], Sol;
char line[nMax], val;
struct stiva
{
int h;
int ind;
}stck[nMax];
void read()
{
fin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
fin>>val;
A[i][j]=val-'0';
}
}
}
void sum_part_coloane()
{
memset(H, 0, sizeof(H));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
H[i][j]=(A[i][j]==0 ? H[i-1][j]+1 : 0);
}
void compute_matrix(int step)
{
int poz, sol, vf;
for(int i=1;i<=n;i++)
{
vf=0;
sol=0;
for(int j=1;j<=m+1;j++)
{
poz=j;
while(H[i][j]<stck[vf].h)
{
sol=max(sol, stck[vf].h*(j-stck[vf].ind));
poz=stck[vf].ind;
vf--;
}
vf++;
stck[vf].h=H[i][j];
stck[vf].ind=poz;
}
switch(step)
{
case 1:MaxDr[1][i]=sol;break;
case 2:MaxDr[2][i]=sol;break;
case 3:MaxDr[3][n-i+1]=sol;break;
case 4:MaxDr[4][n-i+1]=sol;break;
}
}
}
void rotate_matrix()
{
memcpy(AUX, A, sizeof(A));
swap(n, m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
A[i][j]=AUX[m-j+1][i];
}
void solve()
{
int vf, poz, sol, max_another;
for(int i=1;i<=n;i++)
{
vf=0;
sol=0;
for(int j=1;j<=m+1;j++)
{
poz=j;
while(H[i][j]<stck[vf].h)
{
sol=stck[vf].h*(j-stck[vf].ind);
max_another=max(max(MaxDr[1][i-stck[vf].h], MaxDr[2][stck[vf].ind-1]), max(MaxDr[3][i+1], MaxDr[4][j+1]));
if(sol!=0 && max_another!=0)
Sol=max(Sol, sol+max_another);
vf--;
}
vf++;
stck[vf].h=H[i][j];
stck[vf].ind=poz;
}
}
}
void prec()
{
sum_part_coloane();
compute_matrix(1);
rotate_matrix();
sum_part_coloane();
compute_matrix(2);
rotate_matrix();
sum_part_coloane();
compute_matrix(3);
rotate_matrix();
sum_part_coloane();
compute_matrix(4);
rotate_matrix();
sum_part_coloane();
for(int i=1;i<=n;i++)
MaxDr[1][i]=max(MaxDr[1][i], MaxDr[1][i-1]);
for(int i=1;i<=m;i++)
MaxDr[2][i]=max(MaxDr[2][i], MaxDr[2][i-1]);
for(int i=n;i>=1;i--)
MaxDr[3][i]=max(MaxDr[3][i], MaxDr[3][i+1]);
for(int i=m;i>=1;i--)
MaxDr[4][i]=max(MaxDr[4][i], MaxDr[4][i+1]);
}
void write()
{
fout<<Sol;
}
int main()
{
read();
prec();
solve();
write();
return 0;
}