Pagini recente » Cod sursa (job #1507644) | Cod sursa (job #2103119) | Cod sursa (job #1271628) | Cod sursa (job #2840284) | Cod sursa (job #1468645)
# include <bits/stdc++.h>
using namespace std;
ifstream fi("bmatrix.in");
ofstream fo("bmatrix.out");
char c[205][205];
int dp[4][205][205];
int d[205];
int d1[205];
int d2[205];
int n,m;
//e - maxx the best
void go01(int ok)
{
stack < int > s;
for (int i = 1;i <= m;++i) d[i] = 0;
for (int i = 1;i <= n;++i)
{
for (int j = 1;j <= m;++j)
if (c[i][j] == '1') d[j] = i;
while (!s.empty()) s.pop();
for (int j = 1;j <= m;++j)
{
while (!s.empty() && d[s.top()] <= d[j]) s.pop();
d1[j] = (s.empty() ? 0:s.top());
s.push(j);
}
while (!s.empty()) s.pop();
for (int j = m;j;--j)
{
while (!s.empty() && d[s.top()] <= d[j]) s.pop();
d2[j] = (s.empty() ? m+1:s.top());
s.push(j);
}
for (int j = 1;j <= m;++j)
dp[ok][i][j] = max(0,(i - d[j]) * (d2[j] - d1[j] - 1));
}
}
void go23(int ok)
{
stack < int > s;
for (int i = 1;i <= n;++i) d[i] = 0;
for (int j = 1;j <= m;++j)
{
for (int i = 1;i <= n;++i)
if (c[i][j] == '1') d[i] = j;
while (!s.empty()) s.pop();
for (int i = 1;i <= n;++i)
{
while (!s.empty() && d[s.top()] <= d[i]) s.pop();
d1[i] = (s.empty() ? 0:s.top());
s.push(i);
}
while (!s.empty()) s.pop();
for (int i = n;i;--i)
{
while (!s.empty() && d[s.top()] <= d[i]) s.pop();
d2[i] = (s.empty() ? n + 1:s.top());
s.push(i);
}
for (int i = 1;i <= n;++i)
dp[ok][i][j] = max(0,(j - d[i]) * (d2[i] - d1[i] - 1));
}
}
int main(void)
{
fi>>n>>m;
for (int i = 1;i <= n;++i) fi>>(c[i]+1);
int ans = 0;
go01(0);
for (int i = 1;i <= n/2;++i)
for (int j = 1;j <= m;++j) swap(c[i][j],c[n-i+1][j]);
go01(1);
for (int i = 1;i <= n/2;++i)
for (int j = 1;j <= m;++j) swap(c[i][j],c[n-i+1][j]);
go23(2);
for (int i = 1;i <= n;++i)
for (int j = 1;j <= m/2;++j) swap(c[i][j],c[i][m-j+1]);
go23(3);
for (int i = 1;i <= n;++i)
for (int j = 1;j <= m;++j)
ans = max(ans,max(dp[0][i][j] + dp[1][n - i][j],dp[2][i][j] + dp[3][i][m - j]));
return fo << ans << '\n',0;
}