Pagini recente » Cod sursa (job #1106637) | Cod sursa (job #330534) | Cod sursa (job #2676624) | Cod sursa (job #169152) | Cod sursa (job #2716143)
#include <bits/stdc++.h>
#define NMAX 105
using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
int poz[NMAX], mat[NMAX][NMAX], vec[NMAX], whX, whY, n, m, lat, lung, maxUp[NMAX], maxDown[NMAX], maxLeft[NMAX], maxRight[NMAX];
deque<int> st;
int work(int val)
{
vec[val + 1] = -(1 << 30);
int Amax = 0;
st.clear();
for(int j = 1; j <= val + 1; ++j)
{
poz[j] = j;
while(!st.empty() && vec[st.back()] >= vec[j])
{
poz[j] = poz[st.back()];
int Arie = vec[st.back()] * (j - poz[st.back()]);
if(Arie >= Amax)
Amax = Arie;
st.pop_back();
}
st.push_back(j);
}
return Amax;
}
int main()
{
fin >> n >> m;
for(int i = 1; i <= n; ++i)
{
string s;
fin >> s;
for(int j = 0; j < m; ++j)
mat[i][j + 1] = s[j] - '0';
}
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= m; ++j)
if(mat[i][j] == 0)
vec[j]++;
else vec[j] = 0;
maxUp[i] = max(maxUp[i - 1], work(m));
}
memset(vec, 0, sizeof(vec));
for(int i = n; i >= 1; --i)
{
for(int j = 1; j <= m; ++j)
if(mat[i][j] == 0)
vec[j]++;
else vec[j] = 0;
maxDown[i] = max(maxDown[i + 1], work(m));
}
memset(vec, 0, sizeof(vec));
for(int j = 1; j <= m; ++j)
{
for(int i = 1; i <= n; ++i)
if(mat[i][j] == 0)
vec[i]++;
else vec[i] = 0;
maxLeft[j] = max(maxLeft[j - 1], work(n));
}
memset(vec, 0, sizeof(vec));
for(int j = m; j >= 1; --j)
{
for(int i = 1; i <= n; ++i)
if(mat[i][j] == 0)
vec[i]++;
else vec[i] = 0;
maxRight[j] = max(maxRight[j + 1], work(n));
}
int rez = 0;
for(int i = 1; i <= n; ++i)
rez = max(rez, maxUp[i] + maxDown[i + 1]);
for(int j = 1; j <= m; ++j)
rez = max(rez, maxLeft[j] + maxRight[j + 1]);
fout << rez << '\n';
return 0;
}