Pagini recente » Cod sursa (job #974957) | Cod sursa (job #3266930) | Cod sursa (job #273234) | Cod sursa (job #3243620) | Cod sursa (job #2839913)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
int n, m, sus[205][205], jos[205][205], st[205], dr[205], dpsus[205], dpjos[205], v[205];
char a[205][205], inv[205][205];
int ans;
stack < pair < int , int > > L;
void read()
{
fin >> n >> m;
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= m; j ++)
{
fin >> a[i][j];
inv[j][i] = a[i][j];
}
}
}
void sum(char c[205][205])
{
for(int j = 1; j <= m; j ++) // fac sum pe col
{
for(int i = 1; i <= n; i ++)
{
if(c[i][j] == '0')
sus[i][j] = sus[i - 1][j] + 1;
else sus[i][j] = 0;
}
for(int i = n; i >= 1; i --)
{
if(c[i][j] == '0')
jos[i][j] = jos[i + 1][j] + 1;
else jos[i][j] = 0;
}
}
}
int maxim()
{
int ma = 0;
while(!L.empty())
L.pop();
L.push(make_pair(-1, 0));
for(int i = 1; i <= m; i ++)
{
while(!L.empty() && v[i] <= L.top().first)
L.pop();
st[i] = i - L.top().second - 1;
L.push(make_pair(v[i], i));
}
while(!L.empty())
L.pop();
L.push(make_pair(-1, m + 1));
for(int i = m; i >= 1; i --)
{
while(!L.empty() && v[i] <= L.top().first)
L.pop();
dr[i] = L.top().second - i - 1;
L.push(make_pair(v[i], i));
}
for(int i = 1; i <= m; i ++)
{
ma = max(ma, (dr[i] + st[i] + 1) * v[i]);
}
return ma;
}
void solve()
{
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= m; j ++)
{
v[j] = sus[i][j];
}
dpsus[i] = max(dpsus[i - 1], maxim());
}
for(int i = n; i >= 1; i --)
{
for(int j = 1; j <= m; j ++)
{
v[j] = jos[i][j];
}
dpjos[i] = max(dpjos[i + 1], maxim());
}
for(int i = 1; i <= n; i ++)
{
ans = max(ans, dpsus[i] + dpjos[i + 1]);
}
for(int i = 1; i <= n; i ++)
dpsus[i] = dpjos[i] = 0;
}
int main()
{
read();
sum(a);
solve();
swap(n, m);
sum(inv);
solve();
fout << ans;
return 0;
}