Pagini recente » Cod sursa (job #1996446) | Cod sursa (job #977069)
Cod sursa(job #977069)
#include <fstream>
#include <stack>
using namespace std;
/**
Line[i] = aria maxima a unui dreptunghi care se sprijina in jos pe linia i
Line2[i] = aria maxima a unui dreptunghi care se sprijina in sus pe linia i
PartialMax[i] = max(Line[1], Line[2]... Line[i])
PartialMax2[i] = max(Line2[i], Line2[i+1]... Line2[n])
sol = max(PartialMax[i] + PartialMax2[i+1] | i = 1..n-1);
apoi intorc matricea la 90 de grade si fac iar
*/
int n, m, sol;
char a[210][210];
int suma[210][210], suma2[210][210];
int Line[210], Line2[210], PartialMax[210], PartialMax2[210];
/**
suma[i][j] = 0 daca a[i][j] = 1
suma[i][j] = numarul de 0 consecutivi de deasupra elementului (i, j)
suma2[i][j] = 0 daca a[i][j] = 1
suma2[i][j] = numarul de 0 consecutivi de sub elementul (i, j)
*/
inline int max(int x, int y)
{
return x>y?x:y;
}
inline void Read()
{
ifstream f ("bmatrix.in");
f>>n>>m;
int i;
for (i=1; i<=n; i++)
f>>(a[i] + 1);
f.close();
}
inline void Precalc()
{
int i, j;
for (i=1; i<=n; i++)
for (j=1; j<=m; j++)
{
if (a[i][j] == '0')
suma[i][j] = suma[i-1][j] + 1;
else
suma[i][j] = 0;
}
for (i=n; i; i--)
for (j=m; j; j--)
{
if (a[i][j] == '0')
suma2[i][j] = suma2[i+1][j] + 1;
else
suma2[i][j] = 0;
}
}
inline int Arie(int v[])
{
int i;
stack <int> st;
int left[210], right[210], aux;
/// avand histograma in vectorul v
/// right[i] retine cea mai apropiata pozitie din dreapta lui i a.i. v[right[i]] < v[i]
/// left[i] retine cea mai apropiata pozitie din stanga lui i a.i. v[left[i]] < v[i]
for (i=1; i<=m; i++)
{
while (!st.empty() && v[i] < v[st.top()])
{
aux = st.top();
st.pop();
right[aux] = i;
}
st.push(i);
}
while (!st.empty())
{
aux = st.top();
st.pop();
right[aux] = m+1;
}
for (i=m; i; i--)
{
while (!st.empty() && v[i] < v[st.top()])
{
aux = st.top();
st.pop();
left[aux] = i;
}
st.push(i);
}
while (!st.empty())
{
aux = st.top();
st.pop();
left[aux] = 0;
}
int ret = 0;
for (i=1; i<=m; i++)
ret = max(ret, v[i] * (right[i] - left[i] - 1));
return ret;
}
inline void Solve()
{
Precalc();
int i;
for (i = 1; i <= n; i++)
{
Line[i] = Arie(suma[i]);
Line2[i] = Arie(suma2[i]);
}
for (i=1; i<=n; i++)
PartialMax[i] = max(PartialMax[i-1], Line[i]);
for(i=n; i; i--)
PartialMax2[i] = max(PartialMax2[i+1], Line2[i]);
for (i=1; i<n; i++)
sol = max(sol, PartialMax[i] + PartialMax2[i+1]);
}
inline void ReInit()
{
int i, j;
for (i=1; i<=n; i++)
for (j=1; j<=m; j++)
suma[i][j] = suma2[i][j] = 0;
for (i=1; i<=n; i++)
Line[i] = Line2[i] = PartialMax[i] = PartialMax2[i] = 0;
}
inline void Rotate90()
{
int i, j;
char aux[210][210];
for (i=1; i<=n; i++)
for (j=1; j<=m; j++)
{
aux[j][i] = a[i][j];
a[i][j] = 0;
}
for (i=1; i<=m; i++)
for (j=1; j<=n; j++)
a[i][j] = aux[i][j];
swap(n, m);
}
inline void Write()
{
ofstream g("bmatrix.out");
g<<sol<<"\n";
g.close();
}
int main()
{
Read();
Solve();
ReInit();
Rotate90();
Solve();
Write();
return 0;
}