Pagini recente » Cod sursa (job #2471304) | Cod sursa (job #1320370) | Cod sursa (job #644292) | Cod sursa (job #1754274) | Cod sursa (job #2356642)
#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;
const int NMAX = 205;
int n, m;
char s[NMAX];
bool a[NMAX][NMAX], b[NMAX][NMAX];
int dUp[NMAX][NMAX], dDown[NMAX][NMAX];
int maxUp[NMAX], maxDown[NMAX];
int stg[NMAX], drp[NMAX], st[NMAX], top;
int dpUp[NMAX], dpDown[NMAX];
int best;
void Init()
{
memset(dUp, 0, sizeof(dUp));
memset(dDown, 0, sizeof(dDown));
for (int i = 1;i <= n;++i)
for (int j = 1;j <= m;++j)
{
if (a[i][j] == true)
dUp[i][j] = 0;
else
dUp[i][j] = dUp[i - 1][j] + 1;
}
for (int i = n;i >= 1;--i)
for (int j = 1;j <= m;++j)
{
if (a[i][j] == true)
dDown[i][j] = 0;
else
dDown[i][j] = dDown[i + 1][j] + 1;
}
for (int i = 0;i <= n + 1;++i)
dDown[i][0] = dDown[i][m + 1] = dUp[i][0] = dUp[i][m + 1] = -1;
for (int i = 0;i <= m + 1;++i)
dDown[0][i] = dDown[n + 1][i] = dUp[0][i] = dUp[n + 1][i] = -1;
}
void Rotate()
{
for (int i = 1;i <= n;++i)
for (int j = 1;j <= m;++j)
b[j][n - i + 1] = a[i][j];
swap(n, m);
memset(a, 0, sizeof(a));
for (int i = 1;i <= n;++i)
for (int j = 1;j <= m;++j)
a[i][j] = b[i][j];
}
void CreateStg(int line, bool ok)
{
top = 0;
st[top] = 0;
for (int i = 1;i <= m;++i)
{
if (ok == true)
while (top > 0 && dUp[line][i] <= dUp[line][st[top]])
--top;
else
while (top > 0 && dDown[line][i] <= dDown[line][st[top]])
--top;
stg[i] = i - st[top];
st[++top] = i;
}
}
void CreateDrp(int line, bool ok)
{
top = 0;
st[top] = m + 1;
for (int i = m;i >= 1;--i)
{
if (ok == true)
while (top > 0 && dUp[line][i] <= dUp[line][st[top]])
--top;
else
while (top > 0 && dDown[line][i] <= dDown[line][st[top]])
--top;
drp[i] = st[top] - i;
st[++top] = i;
}
}
int main()
{
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
fin >> n >> m;
for (int i = 1;i <= n;++i)
{
fin >> (s + 1);
for (int j = 1;j <= m;++j)
a[i][j] = (s[j] == '1');
}
Init();
int bestUp, bestDown;
for (int i = 1;i < n;++i)
{
bestUp = bestDown = 0;
CreateStg(i, true);
CreateDrp(i, true);
for (int j = 1;j <= m;++j)
bestUp = max(bestUp, dUp[i][j] * (stg[j] + drp[j] - 1));
dpUp[i] = bestUp;
CreateStg(i + 1, false);
CreateDrp(i + 1, false);
for (int j = 1;j <= m;++j)
bestDown = max(bestDown, dDown[i][j] * (stg[j] + drp[j] - 1));
dpDown[i] = bestDown;
}
for (int i = 1;i < n;++i)
dpUp[i] = max(dpUp[i - 1], dpUp[i]);
for (int i = n;i > 1;--i)
dpDown[i] = max(dpDown[i + 1], dpDown[i]);
for (int i = 1;i < n;++i)
best = max(best, dpDown[i + 1] + dpUp[i]);
Rotate();
Init();
for (int i = 1;i < n;++i)
{
bestUp = bestDown = 0;
CreateStg(i, true);
CreateDrp(i, true);
for (int j = 1;j <= m;++j)
bestUp = max(bestUp, dUp[i][j] * (stg[j] + drp[j] - 1));
dpUp[i] = bestUp;
CreateStg(i + 1, false);
CreateDrp(i + 1, false);
for (int j = 1;j <= m;++j)
bestDown = max(bestDown, dDown[i][j] * (stg[j] + drp[j] - 1));
dpDown[i] = bestDown;
}
for (int i = 1;i < n;++i)
dpUp[i] = max(dpUp[i - 1], dpUp[i]);
for (int i = n;i > 1;--i)
dpDown[i] = max(dpDown[i + 1], dpDown[i]);
for (int i = 1;i < n;++i)
best = max(best, dpDown[i + 1] + dpUp[i]);
fout << best << "\n";
fin.close();
fout.close();
return 0;
}