Pagini recente » Cod sursa (job #1933773) | Cod sursa (job #1510865) | Cod sursa (job #1400782) | Cod sursa (job #2147081) | Cod sursa (job #2228408)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
const int Nmax = 205;
int n, m, ans;
int a[Nmax][Nmax], b[Nmax][Nmax], sume1[Nmax][Nmax], sume2[Nmax][Nmax];
int lin[Nmax], lin1[Nmax], lin2[Nmax], stg[Nmax], drp[Nmax];
stack<int> st;
inline int Dreptunghi_max()
{
stg[1] = 1;
st.push(1);
for(int i = 2; i <= m; i++)
{
stg[i] = 1;
while(!st.empty() && lin[i] <= lin[st.top()])
{
stg[i] += stg[st.top()];
st.pop();
}
st.push(i);
}
while(!st.empty())
st.pop();
drp[m] = 1;
st.push(m);
for(int i = m - 1; i >= 1; i--)
{
drp[i] = 1;
while(!st.empty() && lin[i] <= lin[st.top()])
{
drp[i] += drp[st.top()];
st.pop();
}
st.push(i);
}
while(!st.empty())
st.pop();
int dr_max = 0;
for(int i = 1; i <= m; i++)
dr_max = max(dr_max, (stg[i] + drp[i] - 1) * lin[i]);
return dr_max;
}
void Rezolvare(int a[Nmax][Nmax])
{
for(int i = 1; i <= n; i++)
lin1[i] = lin2[i] = 0;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
if(a[i][j] == 0)sume1[i][j] = sume1[i - 1][j] + 1;
else sume1[i][j] = 0;
for(int i = n; i >= 1; i--)
for(int j = 1; j <= m; j++)
if(a[i][j] == 0)sume2[i][j] = sume2[i + 1][j] + 1;
else sume2[i][j] = 0;
int dr;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
lin[j] = sume1[i][j];
dr = Dreptunghi_max();
lin1[i] = max(lin1[i-1], dr);
}
for(int i = n; i >= 1; i--)
{
for(int j = 1; j <= m; j++)
lin[j] = sume2[i][j];
dr = Dreptunghi_max();
lin2[i] = max(lin2[i+1], dr);
}
for(int i = 1; i <= n; i++)
ans = max(ans, lin1[i] + lin2[i + 1]);
}
int main()
{
fin >> n >> m;
char ch;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
fin >> ch;
b[j][i] = a[i][j] = ch - '0';
}
Rezolvare(a);
swap(n, m);
Rezolvare(b);
fout << ans << "\n";
fin.close();
fout.close();
return 0;
}