Pagini recente » Cod sursa (job #2368881) | Cod sursa (job #3221326) | Cod sursa (job #2837858) | Cod sursa (job #1069925) | Cod sursa (job #2370024)
#include <fstream>
#include <cstring>
#include <stack>
using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
const int NMAX = 205;
int N, M, ans;
char s[NMAX][NMAX];
int heights[NMAX];
int bestUp[NMAX]; ///cel mai bun dreptunghi care e peste linia i
int bestDown[NMAX]; ///cel mai bun dreptunghi care e pe si sub linia i
int bestLeft[NMAX]; ///cel mai bun dreptunghi care e inaintea coloanei i
int bestRight[NMAX]; ///cel mai bun dreptunghi care e pe si dupa coloana i
int Solve(int D)
{
stack <int> st;
st.push(0);
int maxAreaRect = 0;
for(int i = 1; i <= D + 1; i++)
{
while(st.size() > 1 && heights[i] <= heights[st.top()])
{
int currentHeight = heights[st.top()];
st.pop();
maxAreaRect = max(maxAreaRect, currentHeight * (i - st.top() - 1));
}
st.push(i);
}
return maxAreaRect;
}
int main()
{
fin >> N >> M;
for(int i = 1; i <= N; i++)
fin >> (s[i] + 1);
///bestUp
memset(heights, 0, sizeof(heights));
for(int i = 1; i <= N; i++)
{
for(int j = 1; j <= M; j++)
if(s[i][j] == '0')
heights[j]++;
else
heights[j] = 0;
bestUp[i + 1] = max(bestUp[i], Solve(M));
}
///bestDown
memset(heights, 0, sizeof(heights));
for(int i = N; i >= 1; i--)
{
for(int j = 1; j <= M; j++)
if(s[i][j] == '0')
heights[j]++;
else
heights[j] = 0;
bestDown[i] = max(bestDown[i + 1], Solve(M));
}
///bestLeft
memset(heights, 0, sizeof(heights));
for(int i = 1; i <= M; i++)
{
for(int j = 1; j <= N; j++)
if(s[j][i] == '0')
heights[j]++;
else
heights[j] = 0;
bestLeft[i + 1] = max(bestLeft[i], Solve(N));
}
///bestRight
memset(heights, 0, sizeof(heights));
for(int i = M; i >= 1; i--)
{
for(int j = 1; j <= N; j++)
if(s[j][i] == '0')
heights[j]++;
else
heights[j] = 0;
bestRight[i] = max(bestRight[i + 1], Solve(N));
}
///Up-Down
for(int i = 1; i <= N; i++)
ans = max(ans, bestUp[i] + bestDown[i]);
///Left-Right
for(int i = 1; i <= M; i++)
ans = max(ans, bestLeft[i] + bestRight[i]);
fout << ans << '\n';
return 0;
}