Pagini recente » Cod sursa (job #92221) | Cod sursa (job #1151835) | Cod sursa (job #1470359) | Cod sursa (job #3294491) | Cod sursa (job #1112045)
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <stack>
#include <algorithm>
using namespace std;
const int NMAX = 210, INF = 0x3f3f3f3f;
int N, M, Mat[NMAX][NMAX], Up[NMAX][NMAX], Down[NMAX][NMAX], Left[NMAX], Right[NMAX];
int MaxUp[NMAX], MaxDown[NMAX], Ans, Aux[NMAX][NMAX];
char S[NMAX][NMAX];
void RotateMatrix()
{
int Line = 1, Col = 1;
for(int i = 1; i <= N; ++ i, Line = 1, ++ Col)
for(int j = 1; j <= M; ++ j, ++ Line)
{
Aux[Line][Col] = Mat[i][j];
Mat[i][j] = Up[i][j] = Down[i][j] = 0;
}
swap(N, M);
for(int i = 1; i <= N; ++ i)
for(int j = 1; j <= M; ++ j)
Mat[i][j] = Aux[i][j];
}
void Solve()
{
for(int i = 1; i <= N; ++ i)
MaxUp[i] = MaxDown[i] = 0;
for(int i = 1; i <= N; ++ i)
for(int j = 1; j <= M; ++ j)
Up[i][j] = (1 - Mat[i][j]) * (Up[i - 1][j] + 1);
for(int i = N; i; -- i)
for(int j = 1; j <= M; ++ j)
Down[i][j] = (1 - Mat[i][j]) * (Down[i + 1][j] + 1);
for(int i = 1; i <= N; ++ i)
{
stack<int> S;
Up[i][0] = Up[i][M + 1] = Down[i][0] = Down[i][M + 1] = -INF;
S.push(0);
for(int j = 1; j <= M; ++ j)
{
while(!S.empty() && Up[i][S.top()] >= Up[i][j]) S.pop();
Left[j] = S.top() + 1;
S.push(j);
}
while(!S.empty()) S.pop();
S.push(M + 1);
for(int j = M; j; -- j)
{
while(!S.empty() && Up[i][S.top()] >= Up[i][j]) S.pop();
Right[j] = S.top() - 1;
S.push(j);
}
for(int j = 1; j <= M; ++ j)
MaxUp[i] = max(MaxUp[i], Up[i][j] * (Right[j] - Left[j] + 1));
MaxUp[i] = max(MaxUp[i], MaxUp[i - 1]);
while(!S.empty()) S.pop();
S.push(0);
for(int j = 1; j <= M; ++ j)
{
while(!S.empty() && Down[i][S.top()] >= Down[i][j]) S.pop();
Left[j] = S.top() + 1;
S.push(j);
}
while(!S.empty()) S.pop();
S.push(M + 1);
for(int j = M; j; -- j)
{
while(!S.empty() && Down[i][S.top()] >= Down[i][j]) S.pop();
Right[j] = S.top() - 1;
S.push(j);
}
for(int j = 1; j <= M; ++ j)
MaxDown[i] = max(MaxDown[i], Down[i][j] * (Right[j] - Left[j] + 1));
}
for(int i = 1; i < N; ++ i)
Ans = max(Ans, MaxUp[i] + MaxDown[i + 1]);
}
int main()
{
freopen("bmatrix.in", "r", stdin);
freopen("bmatrix.out", "w", stdout);
scanf("%i %i\n", &N, &M);
for(int i = 1; i <= N; ++ i)
{
gets(S[i] + 1);
for(int j = 1; j <= M; ++ j)
Mat[i][j] = S[i][j] - '0';
}
Solve();
RotateMatrix();
Solve();
printf("%i\n", Ans);
}