Pagini recente » Cod sursa (job #295) | Cod sursa (job #359685) | Cod sursa (job #85990) | Cod sursa (job #1257229) | Cod sursa (job #1255389)
#include<fstream>
#include<string>
using namespace std;
ifstream in("bmatrix.in");
ofstream out("bmatrix.out");
const int nmax = 206;
string s;
int n, m, rasp, ms[nmax][nmax], maxst[nmax], maxdr[nmax], maxlin[3][nmax];
bool mat[nmax][nmax];
int orizontal()
{
int rez = 0;
for(int i = 1; i<=n; i++)
{
for(int j = 1; j<=m; j++)
{
if(mat[i][j]==0)
{
ms[i][j] = ms[i - 1][j] + 1;
}
else
{
ms[i][j] = 0;
}
}
ms[i][0] = ms[i][m + 1] = -1;
for(int j = 1; j<=m; j++)
{
int h;
for(h = j - 1; ms[i][j]<=ms[i][h];)
{
h = maxst[h];
}
maxst[j] = h;
}
for(int j = m; j>0; j--)
{
int h;
for(h = j + 1; ms[i][j]<=ms[i][h];)
{
h = maxdr[h];
}
maxdr[j] = h;
}
maxlin[1][i] = maxlin[1][i - 1];
for(int j = 1; j<=m; j++)
{
if(ms[i][j] * (maxdr[j] - maxst[j] - 1)>maxlin[1][i])
{
maxlin[1][i] = ms[i][j] * (maxdr[j] - maxst[j] - 1);
}
}
}
for(int i = 0; i<nmax; i++)
for(int j = 0; j<nmax; j++)
ms[i][j] = 0;
for(int i = n; i>=1; i--)
{
for(int j = 1; j<=m; j++)
{
if(mat[i][j]==0)
{
ms[i][j] = ms[i + 1][j] + 1;
}
else
{
ms[i][j] = 0;
}
}
ms[i][0] = ms[i][m + 1] = -1;
for(int j = 1; j<=m; j++)
{
int h;
for(h = j - 1; ms[i][j]<=ms[i][h];)
{
h = maxst[h];
}
maxst[j] = h;
}
for(int j = m; j>0; j--)
{
int h;
for(h = j + 1; ms[i][j]<=ms[i][h];)
{
h = maxdr[h];
}
maxdr[j] = h;
}
maxlin[2][i] = maxlin[2][i + 1];
for(int j = 1; j<=m; j++)
{
if(ms[i][j] * (maxdr[j] - maxst[j] - 1)>maxlin[2][i])
{
maxlin[2][i] = ms[i][j] * (maxdr[j] - maxst[j] - 1);
}
}
}
for(int i = 0; i<nmax; i++)
for(int j = 0; j<nmax; j++)
ms[i][j] = 0;
for(int i = 1; i<=n; i++)
{
if(maxlin[1][i] + maxlin[2][i + 1]>rez)
rez = maxlin[1][i] + maxlin[2][i + 1];
}
for(int i = 1; i<3; i++)
for(int j = 0; j<nmax; j++)
maxlin[i][j] = 0;
return rez;
}
int vertical()
{
int rez = 0;
for(int i = 1; i<=m; i++)
{
for(int j = 1; j<=n; j++)
{
if(mat[j][i]==0)
{
ms[j][i] = ms[j][i - 1] + 1;
}
else
{
ms[j][i] = 0;
}
}
ms[0][i] = ms[m + 1][i] = -1;
for(int j = 1; j<=n; j++)
{
int h;
for(h = j - 1; ms[j][i]<=ms[h][i];)
{
h = maxst[h];
}
maxst[j] = h;
}
for(int j = n; j>0; j--)
{
int h;
for(h = j + 1; ms[j][i]<=ms[h][i];)
{
h = maxdr[h];
}
maxdr[j] = h;
}
maxlin[1][i] = maxlin[1][i - 1];
for(int j = 1; j<=n; j++)
{
if(ms[j][i] * (maxdr[j] - maxst[j] - 1)>maxlin[1][i])
{
maxlin[1][i] = ms[j][i] * (maxdr[j] - maxst[j] - 1);
}
}
}
for(int i = 0; i<nmax; i++)
for(int j = 0; j<nmax; j++)
ms[i][j] = 0;
for(int i = m; i>=1; i--)
{
for(int j = 1; j<=n; j++)
{
if(mat[j][i]==0)
{
ms[j][i] = ms[j][i + 1] + 1;
}
else
{
ms[j][i] = 0;
}
}
ms[0][i] = ms[m + 1][i] = -1;
for(int j = 1; j<=m; j++)
{
int h;
for(h = j - 1; ms[j][i]<=ms[h][i];)
{
h = maxst[h];
}
maxst[j] = h;
}
for(int j = m; j>0; j--)
{
int h;
for(h = j + 1; ms[j][i]<=ms[h][i];)
{
h = maxdr[h];
}
maxdr[j] = h;
}
maxlin[2][i] = maxlin[2][i + 1];
for(int j = 1; j<=m; j++)
{
if(ms[j][i] * (maxdr[j] - maxst[j] - 1)>maxlin[2][i])
{
maxlin[2][i] = ms[j][i] * (maxdr[j] - maxst[j] - 1);
}
}
}
for(int i = 0; i<nmax; i++)
for(int j = 0; j<nmax; j++)
ms[i][j] = 0;
for(int i = 1; i<=m; i++)
{
if(maxlin[1][i] + maxlin[2][i + 1]>rez)
rez = maxlin[1][i] + maxlin[2][i + 1];
}
for(int i = 1; i<3; i++)
for(int j = 0; j<nmax; j++)
maxlin[i][j] = 0;
return rez;
}
int main(){
int player_unu=0;
in>>n>>m;getline(in, s);
for(int i = 1; i<=n; i++)
{
getline(in, s);
for(int j = 0; j<(int)s.size(); j++)
mat[i][j + 1] = s[j] - '0';
}
int a = orizontal(), b = vertical();
out<<max(a, b)<<'\n';
return player_unu;
}