Cod sursa(job #876719)
Utilizator | Data | 12 februarie 2013 00:53:28 | |
---|---|---|---|
Problema | BMatrix | Scor | 44 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 6.54 kb |
#include <iostream>
#include <fstream>
using namespace std;
int n, m, b[210][210], sol, b1[210][210];
char a[210][210], a1[210][210];
struct stiva
{
int x, poz;
};
stiva st[256];
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 int Amaxc(int x1, int y1, int x2, int y2)
{
int vf;
int i, j, val, maxim=0, poz, x;
for (i=x1; i<=x2; i++)
{
val = 0;
vf = 0;
for (j=y1; j<=y2; j++)
{
if (b[i][j])
{
x = b[i][j];
if (st[vf].x > x)
{
while (st[vf].x > x)
{
val = max (val, x * (j - st[vf].poz + 1));
vf--;
}
vf++;
st[vf].x = x;
st[vf].poz = j;
}
else
if (st[vf].x < x)
{
vf++;
st[vf].x = x;
st[vf].poz = j;
}
}
else
{
while (vf>0)
{
val = max (val, st[vf].x * (j - st[vf].poz));
vf--;
}
vf = 0;
}
}
while (vf>0)
{
val = max (val, st[vf].x * (y2 - st[vf].poz + 1));
vf--;
}
maxim = max (maxim, val);
val = 0;
vf = 0;
for (j=y2; j>=y1; j--)
{
if (b[i][j])
{
x = b[i][j];
if (st[vf].x > x)
{
while (st[vf].x > x)
{
val = max (val, x * (st[vf].poz - j + 1));
vf--;
}
vf++;
st[vf].x = x;
st[vf].poz = j;
}
else
if (st[vf].x < x)
{
vf++;
st[vf].x = x;
st[vf].poz = j;
}
}
else
{
while (vf>0)
{
val = max (val, st[vf].x * (st[vf].poz - j));
vf--;
}
vf = 0;
}
}
while (vf>0)
{
val = max (val, st[vf].x * (st[vf].poz - y1 + 1)); //
vf--;
}
maxim = max (maxim, val);
}
return maxim;
}
inline int Amaxl(int x1, int y1, int x2, int y2)
{
int vf;
int i, j, val, maxim=0, poz, x;
for (j=y1; j<=y2; j++)
if (b[x1-1][j])
{
for (i=x1; b[i][j] && i<=x2; i++)
b1[i][j] = b[i][j] - b[x1-1][j];
for (; i<=n; i++)
b1[i][j] = b[i][j];
}
else
for (i=x1; i<=x2; i++)
b1[i][j] = b[i][j];
for (i=x1; i<=x2; i++)
{
val = 0;
vf = 0;
for (j=y1; j<=y2; j++)
{
if (b1[i][j])
{
x = b1[i][j];
if (st[vf].x > x)
{
while (st[vf].x > x)
{
val = max (val, x * (j - st[vf].poz + 1)); ////// st[vf].x
vf--;
}
vf++;
st[vf].x = x;
st[vf].poz = j;
}
else
if (st[vf].x < x)
{
vf++;
st[vf].x = x;
st[vf].poz = j;
}
}
else
{
while (vf>0)
{
val = max (val, st[vf].x * (j - st[vf].poz));
vf--;
}
vf = 0;
}
}
while (vf>0)
{
val = max (val, st[vf].x * (y2 - st[vf].poz + 1));
vf--;
}
maxim = max (maxim, val);
val = 0;
vf = 0;
for (j=y2; j>=y1; j--)
{
if (b1[i][j])
{
x = b1[i][j];
if (st[vf].x > x)
{
while (st[vf].x > x)
{
val = max (val, x * (st[vf].poz - j + 1));
vf--;
}
vf++;
st[vf].x = x;
st[vf].poz = j;
}
else
if (st[vf].x < x)
{
vf++;
st[vf].x = x;
st[vf].poz = j;
}
}
else
{
while (vf>0)
{
val = max (val, st[vf].x * (st[vf].poz - j));
vf--;
}
vf = 0;
}
}
while (vf>0)
{
val = max (val, st[vf].x * (st[vf].poz - y1 + 1)); //
vf--;
}
maxim = max (maxim, val);
}
return maxim;
}
inline void Transp()
{
int i, j;
for (i=1; i<=n; i++)
for (j=1; j<=m; j++)
a1[j][i] = a[i][j], b[i][j] = 0;
swap(n, m);
for (i=1; i<=n; i++)
for (j=1; j<=m; j++)
{
if (a1[i][j] == '0')
b[i][j] = b[i-1][j] + 1;
}
}
inline void Solve()
{
int i, j, val1, val2;
for (i=1; i<=n; i++)
for (j=1; j<=m; j++)
if (a[i][j] == '0')
b[i][j] = b[i-1][j] + 1;
int linie, coloana;
for (coloana = 1; coloana < m; coloana++)
{
val1 = Amaxc(1, 1, n, coloana);
val2 = Amaxc(1, coloana+1, n, m);
sol = max(sol, val1 + val2);
}
Transp();
for (coloana = 1; coloana < m; coloana++)
{
val1 = Amaxc(1, 1, n, coloana);
val2 = Amaxc(1, coloana+1, n, m);
sol = max(sol, val1 + val2);
}
}
inline void Write()
{
ofstream g("bmatrix.out");
g<<sol<<"\n";
g.close();
}
int main()
{
Read();
Solve();
Write();
return 0;
}