Pagini recente » Cod sursa (job #2187950) | Cod sursa (job #2634584) | Cod sursa (job #1606625) | Cod sursa (job #645837) | Cod sursa (job #2839703)
#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; ///poate ramane val de dinainte
}
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 ++) /// merg pe coloane
{
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 ++) ///pt fiecare el de pe linie calculez aria pe intervalul st - dr
{
// if((dr[i] + st[i] + 1) * v[i] >= ma)
// ma = (dr[i] + st[i] + 1) * v[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[i] = jos[i][j];
}
dpjos[i] = max(dpjos[i + 1], maxim());
}
for(int i = 1; i <= n; i ++)
{
// if(ans <= (dpsus[i] + dpjos[i + 1]))
// {
// //fout << dpsus[i] << " " << dpjos[i + 1] << endl;
// ans = dpsus[i] + dpjos[i + 1];
// }
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;
}