Pagini recente » Cod sursa (job #95572) | Cod sursa (job #620451) | Cod sursa (job #2803847) | Cod sursa (job #744734) | Cod sursa (job #1598009)
#include<iostream>
#include<fstream>
using namespace std;
ifstream in("bmatrix.in");
ofstream out("bmatrix.out");
const int N = 202;
int mat[N][N];
int n,m;
int v[N],h[N];
int sol;
int stiva[N], n_stiva;
int arie_histogram(int st, int dr)
{
int j,top,arie,arie_max;
stiva[0] = 0;
n_stiva = 0;
arie_max = 0;
j = st;
while(j <= dr)
{
top = stiva[n_stiva];
if(n_stiva == 0 || h[top] <= h[j])
{
++n_stiva;
stiva[n_stiva] = j;
++j;
}
else
{
if(n_stiva == 1) arie = h[top] * (j - stiva[n_stiva - 1] - 1 - st + 1);
else arie = h[top] * (j - stiva[n_stiva - 1] - 1);
arie_max = max(arie, arie_max);
--n_stiva;
}
}
while(n_stiva > 0)
{
top = stiva[n_stiva];
if(n_stiva == 1) arie = h[top] * (j - stiva[n_stiva - 1] - 1 - st + 1);
else arie = h[top] * (j - stiva[n_stiva - 1] - 1);
arie_max = max(arie, arie_max);
--n_stiva;
}
return arie_max;
}
int solve()
{
int i,j,mij,area1,area2,area1_max,area2_max,area_max;
area_max = 0;
for(mij=2; mij<=m; ++mij)
{
area1_max = 0;
area2_max = 0;
for(i=1; i<=m; ++i) h[i] = 0;
for(i=1; i<=n; ++i)
{
for(j=1; j<=m; ++j)
{
if(mat[i][j] == 1) h[j] = 0;
else ++h[j];
}
area1 = arie_histogram(1, mij-1);
area2 = arie_histogram(mij, m);
///cout<<"i = "<<i<<", area1 = "<<area1<<", area2 = "<<area2<<"\n";
area1_max = max(area1_max, area1);
area2_max = max(area2_max, area2);
}
///cout<<"mij = "<<mij<<", area1 = "<<area1_max<<", area2 = "<<area2_max<<"\n";
area_max = max(area_max, area1_max + area2_max);
}
///cout<<"AREA MAX = "<<area_max<<"\n";
return area_max;
}
void flip_stanga()
{
int newmat[N][N];
int i,j;
for(i=1; i<=n; ++i)
for(j=1; j<=m; ++j)
{
newmat[m-j+1][i] = mat[i][j];
}
swap(n, m);
for(i=1; i<=n; ++i)
for(j=1; j<=m; ++j)
mat[i][j] = newmat[i][j];
}
void afis()
{
int i,j;
for(i=1; i<=n; ++i)
{
for(j=1; j<=m; ++j)
cout<<mat[i][j];
cout<<"\n";
}
cout<<"\n";
}
int main()
{
int i,j;
char sir[N];
in>>n>>m;
in.getline(sir, N);
for(i=1; i<=n; ++i)
{
in.getline(sir, N);
for(j=0; j<m; ++j) mat[i][j+1] = sir[j] - '0';
}
///afis();
sol = solve();
///cout<<"\n";
flip_stanga();
///afis();
sol = max(sol, solve());
out<<sol;
return 0;
}