Pagini recente » Cod sursa (job #3295524) | Cod sursa (job #374289) | Cod sursa (job #2380428) | Cod sursa (job #1468638)
# include <bits/stdc++.h>
using namespace std;
ifstream fi("bmatrix.in");
ofstream fo("bmatrix.out");
char c[205][205];
int dp[2][205][205];
int d[205];
int d1[205];
int d2[205];
int n,m;
//e - maxx the best
void go(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));
}
}
int main(void)
{
fi>>n>>m;
for (int i = 1;i <= n;++i) fi>>(c[i]+1);
int ans = 0;
go(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]);
go(1);
for (int i = 1;i <= n;++i)
for (int j = 1;j <= m;++j)
ans = max(ans,dp[0][i][j] + dp[1][n - i][j]);
return fo << ans << '\n',0;
}