Pagini recente » Cod sursa (job #2741598) | Cod sursa (job #1168181) | Cod sursa (job #1702074) | Cod sursa (job #353398) | Cod sursa (job #2240339)
#include <fstream>
#include <cstring>
#include <stack>
using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
int N, M, answer, heights[205];
int upDP[205]; ///cel mai mare dreptunghi care sta pe sau peste linia i
int downDP[205]; ///cel mai mare dreptunghi care sta sub linia i
int leftDP[205]; ///cel mai mare dreptunghi care sta pe sau inaintea coloanei j
int rightDP[205]; ///cel mai mare dreptunghi care sta dupa linia j
char s[205][205];
int Solve(int dim)
{
stack <int> st;
int maxAreaRect = 0;
st.push(0);
for(int i = 1; i <= dim + 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;
fin.get();
for(int i = 1; i <= N; i++)
fin.getline(s[i], sizeof(s[i]));
///upDP
for(int i = 1; i <= N; i++)
{
for(int j = 0; j < M; j++)
heights[j + 1] = (s[i][j] == '1') ? 0 : heights[j + 1] + 1;
upDP[i] = max(Solve(M), upDP[i - 1]);
}
///downDP
memset(heights, 0, sizeof(heights));
for(int i = N - 1; i >= 1; i--)
{
for(int j = 0; j < M; j++)
heights[j + 1] = (s[i + 1][j] == '1') ? 0 : heights[j + 1] + 1;
downDP[i] = max(Solve(M), downDP[i + 1]);
}
///leftDP
memset(heights, 0, sizeof(heights));
for(int j = 0; j < M; j++)
{
for(int i = 1; i <= N; i++)
heights[i] = (s[i][j] == '1') ? 0 : heights[i] + 1;
leftDP[j + 1] = max(Solve(N), leftDP[j]);
}
///rightDP
memset(heights, 0, sizeof(heights));
for(int j = M - 2; j >= 0; j--)
{
for(int i = 1; i <= N; i++)
heights[i] = (s[i][j + 1] == '1') ? 0 : heights[i] + 1;
rightDP[j + 1] = max(Solve(N), rightDP[j + 2]);
}
for(int i = 1; i <= N; i++)
answer = max(answer, upDP[i] + downDP[i]);
for(int i = 1; i <= M; i++)
answer = max(answer, leftDP[i] + rightDP[i]);
fout << answer << '\n';
return 0;
}