Pagini recente » Cod sursa (job #725629) | Cod sursa (job #3338778) | Cod sursa (job #1152276) | Cod sursa (job #532877) | Cod sursa (job #3355019)
#include <fstream>
#include <stack>
using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
int n,m;
int A[205][205];
int up[205][205], l[205][205], r[205][205];
void read()
{
fin >> n >> m;
for(int i = 0; i < n; ++i){
string s;
fin >> s;
for(int j = 0; j < m; ++j){
A[i][j] = s[j] - '0';
}
}
}
void buildUp()
{
for(int j = 0; j < m; ++j){
for(int i = 0; i < n; ++i){
if(A[i][j] == 0){
if(i == 0){
up[i][j] = 1;
}
else{
up[i][j] = up[i - 1][j] + 1;
}
}
else{
up[i][j] = 0;
}
}
}
}
void buildLeftRight()
{
for(int i = 0; i < n; ++i){
stack<int> st;
st.push(0);
l[i][0] = -1;
for(int j = 1; j < m; ++ j){
while(!st.empty() && up[i][j] <= up[i][st.top()]){
st.pop();
}
if(st.empty()){
l[i][j] = -1;
}
else{
l[i][j] = st.top();
}
st.push(j);
}
}
for(int i = 0; i < n; ++i){
stack<int> st;
st.push(m - 1);
r[i][m - 1] = m;
for(int j = m - 2; j >= 0; --j){
while(!st.empty() && up[i][j] <= up[i][st.top()]){
st.pop();
}
if(st.empty()){
r[i][j] = m;
}
else{
r[i][j] = st.top();
}
st.push(j);
}
}
}
int maxArea(int r1, int r2, int c1, int c2)
{
int maxA = 0;
for(int i = r1; i <= r2; ++i){
for(int j = c1; j <= c2; ++j){
int lp = l[i][j], rp = r[i][j], h = up[i][j];
if(l[i][j] < c1){
lp = c1 - 1;
}
if(r[i][j] > c2){
rp = c2 + 1;
}
if(up[i][j] > i - r1 + 1){
h = i - r1 + 1;
}
int a = (rp - lp - 1) * h;
if(a > maxA){
maxA = a;
}
}
}
return maxA;
}
void solve()
{
int maxA = 0;
for(int i = 0; i < n - 1; ++i){
int a = maxArea(0, i, 0, m - 1) + maxArea(i + 1, n - 1, 0, m - 1);
if(a > maxA){
maxA = a;
}
}
for(int j = 0; j < m - 1; ++j){
int a = maxArea(0, n - 1, 0, j) + maxArea(0, n - 1, j + 1, m - 1);
if(a > maxA){
maxA = a;
}
}
fout << maxA;
}
int main()
{
read();
buildUp();
buildLeftRight();
solve();
return 0;
}