Pagini recente » Cod sursa (job #1593270) | Cod sursa (job #9354) | Cod sursa (job #999033) | Cod sursa (job #1592838) | Cod sursa (job #1836131)
#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
int b[203][203],n,m,sol,stg[203],drp[203],t[203],st[203];
char a[203][203];
int Solutie(int xi, int yi, int xf, int yf)
{
int i,j,L,rasp,top,x;
rasp = -INF;
L = yf - yi + 1;
for(i = xi; i <= xf; ++i)
{
for(j = yi; j <= yf; ++j)
t[j-yi+1] = max(0,b[i][j] - xi + 1);
//stg
t[0] = -INF - 1;
top=0;
st[top] = 0;
for(j = 1; j <= L; ++j)
{
x = t[j];
while(x <= t[st[top]])
top--;
stg[j] = j - st[top];
st[++top]=j;
}
//drp
t[L+1] = -INF - 1;
top=0;
st[top] = L+1;
for(j = L; j >= 1; --j)
{
x = t[j];
while(x <= t[st[top]])
top--;
drp[j] = st[top] - j;
st[++top]=j;
}
for(j = 1; j <= L; ++j)
if(t[j] != -INF)
rasp = max(rasp,(stg[j] + drp[j] - 1) * t[j]);
}
return rasp;
}
int main()
{
int i,j;
ifstream fin("bmatrix.in");
fin >> n >> m;
for(i = 1; i <= n; ++i)
fin >> (a[i]+1);
fin.close();
for(i = 1; i <= n; ++i)
for(j = 1; j <= m; ++j)
if(a[i][j] == '1')
b[i][j] = -INF;
else
b[i][j] = max(0,b[i-1][j]) + 1;
sol = -INF;
for(i = 1; i < n; ++i)
sol=max(sol,Solutie(1,1,i,m) + Solutie(i+1,1,n,m));
for(j = 1; j < m; ++j)
sol=max(sol,Solutie(1,1,n,j) + Solutie(1,j+1,n,m));
ofstream fout("bmatrix.out");
fout << sol << "\n";
fout.close();
return 0;
}