Pagini recente » Cod sursa (job #2978050) | Cod sursa (job #285127) | Cod sursa (job #1783454) | Cod sursa (job #1682243) | Cod sursa (job #826193)
Cod sursa(job #826193)
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <iostream>
#include <fstream>
#include <string>
#include <set>
#include <map>
#include <deque>
#include <bitset>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <tr1/unordered_map>
#include <algorithm>
#include <iomanip>
#include <cctype>
#include <ctime>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define leftSon (node << 1)
#define rightSon ((node << 1) + 1)
#define nmax 210
int Up[nmax][nmax], Down[nmax][nmax], Left[nmax], Right[nmax], N, M, mat[nmax][nmax], AnsUp[nmax], AnsDown[nmax];
stack<int> St;
int ans;
char S[1000];
void Go()
{
int i, j;
memset(Up, 0, sizeof(Up));
memset(Down, 0, sizeof(Down));
memset(AnsUp, 0, sizeof(AnsUp));
memset(AnsDown, 0, sizeof(AnsDown));
for(i = 1; i <= N; i++)
for(j = 1; j <= M; j++)
if(mat[i][j] == 0)
Up[i][j] = Up[i - 1][j] + 1;
else
Up[i][j] = 0;
for(i = N; i; i--)
for(j = 1; j <= M; j++)
if(mat[i][j] == 0)
Down[i][j] = Down[i + 1][j] + 1;
else
Down[i][j] = 0;
for(i = 1; i <= N; i++)
{
for(j = 1; j <= M; j++)
{
while(!St.empty() && Up[i][St.top()] >= Up[i][j]) Right[St.top()] = j - 1, St.pop();
if(St.empty()) Left[j] = 1;
else Left[j] = St.top() + 1;
St.push(j);
}
while(!St.empty()) Right[St.top()] = M, St.pop();
int crt = 0;
for(j = 1; j <= M; j++)
crt = max(crt, Up[i][j] * (Right[j] - Left[j] + 1));
AnsUp[i] = max(AnsUp[i - 1], crt);
for(j = 1; j <= M; j++)
{
while(!St.empty() && Down[i][St.top()] >= Down[i][j]) Right[St.top()] = j - 1, St.pop();
if(St.empty()) Left[j] = 1;
else Left[j] = St.top() + 1;
St.push(j);
}
while(!St.empty()) Right[St.top()] = M, St.pop();
crt = 0;
for(j = 1; j <= M; j++)
crt = max(crt, Down[i][j] * (Right[j] - Left[j] + 1));
AnsDown[i] = max(AnsDown[i + 1], crt);
}
for(i = 1; i < N; i++) ans = max(ans, AnsUp[i] + AnsDown[i + 1]);
}
int main()
{
freopen("bmatrix.in", "r", stdin);
freopen("bmatrix.out", "w", stdout);
int i, j;
scanf("%i %i\n", &N, &M);
for(i = 1; i <= N; i++)
{
gets(S);
for(j = 0; j < M; j++) mat[i][j + 1] = S[j] - '0';
}
Go();
int aux[nmax][nmax];
memcpy(aux, mat, sizeof(aux));
for(i = 1; i <= N; i++)
for(j = 1; j <= M; j++)
mat[j][i] = aux[i][j];
int auxx = N;
N = M;
M = auxx;
Go();
printf("%i\n", ans);
return 0;
}