Pagini recente » Cod sursa (job #2591495) | Cod sursa (job #1086196) | Cod sursa (job #2607841) | Cod sursa (job #3286701) | Cod sursa (job #1512391)
#include <cstdio>
#include <algorithm>
#include <stack>
#define NMAX 225
using namespace std;
int n, m, ans, dp[4][NMAX], prec[NMAX], prec1[NMAX], prec2[NMAX];
char mat[NMAX][NMAX];
void solve1(const int &f)
{
stack <int> stiva;
for(int i = 1; i<= m; ++i) prec[i] = 0;
for(int i = 1; i<= n; ++i)
{
for(int j = 1; j<= m; ++j)
{
if(mat[i][j] == '1') prec[j] = i;
}
while(!stiva.empty()) stiva.pop();
for(int j = 1; j<= m; ++j)
{
while(!stiva.empty() && prec[stiva.top()] <= prec[j]) stiva.pop();
prec1[j] = ((stiva.empty())?0:stiva.top());
stiva.push(j);
}
while(!stiva.empty()) stiva.pop();
for(int j = m; j; --j)
{
while(!stiva.empty() && prec[stiva.top()] <= prec[j]) stiva.pop();
prec2[j] = ((stiva.empty()) ? m+1:stiva.top());
stiva.push(j);
}
dp[f][i] = dp[f][i-1];
for(int j = 1; j<= m; ++j)
dp[f][i] = max(dp[f][i], (i - prec[j]) * (prec2[j] - prec1[j] - 1));
}
}
void solve2(const int &f)
{
stack <int> stiva;
for(int i = 1; i<= n; ++i) prec[i] = 0;
for(int j = 1; j<= m; ++j)
{
for(int i = 1; i <= n; ++i)
{
if(mat[i][j] == '1') prec[i] = j;
}
while(!stiva.empty()) stiva.pop();
for(int i = 1; i<= n; ++i)
{
while(!stiva.empty() && prec[stiva.top()] <= prec[i]) stiva.pop();
prec1[i] = ((stiva.empty()) ? 0 : stiva.top());
stiva.push(i);
}
while(!stiva.empty()) stiva.pop();
for(int i = n; i; --i)
{
while(!stiva.empty() && prec[stiva.top()] <= prec[i]) stiva.pop();
prec2[i] = ((stiva.empty()) ? n + 1:stiva.top());
stiva.push(i);
}
dp[f][j] = dp[f][j-1];
for(int i = 1; i<= n; ++i)
dp[f][j] = max(dp[f][j], (j - prec[i]) * (prec2[i] - prec1[i] - 1));
}
}
void apel()
{
solve1(0);
for(int i = 1; i<= n/2; ++i) swap(mat[i], mat[n-i+1]);
solve1(1);
for(int i = 1; i<= n/2; ++i) swap(mat[i], mat[n-i+1]);
solve2(2);
for(int i = 1; i<= n; ++i)
for(int j = 1; j<= m/2; ++j) swap(mat[i][j], mat[i][m-j+1]);
solve2(3);
}
void reconstituire()
{
for(int i = 1; i< n; ++i)
{
ans = max(ans, dp[0][i] + dp[1][n-i]);
//printf("%d\n", dp[0][i] + dp[1][n-i]);
}
//printf("check\n");
for(int i = 1; i< m; ++i)
{
ans = max(ans, dp[2][i] + dp[3][m-i]);
//printf("%d\n", dp[2][i] + dp[3][m-i]);
}
}
int main()
{
freopen("bmatrix.in", "r", stdin);
freopen("bmatrix.out", "w", stdout);
scanf("%d %d", &n, &m);
for(int i = 1; i<= n; ++i) scanf("%s", mat[i]+1);
// for(int i = 1; i<= n; ++i)
// for(int j = 1; j<= m; ++j)
// mat[i][j] -= '0';
apel();
reconstituire();
printf("%d\n", ans);
return 0;
}