Pagini recente » Cod sursa (job #2294943) | Cod sursa (job #1260901) | Cod sursa (job #3254428) | Cod sursa (job #2726043) | Cod sursa (job #1819150)
#include <cstdio>
using namespace std;
FILE *f, *g;
int n, m;
int k;
int rez;
int stk[201], dr;
int h[201];
bool a[201][201];
int left[201], right[201];
int l1_1[201][201];
int l1_2[201][201];
int l2_1[201][201];
int l2_2[201][201];
int dr_up[201];
int dr_dn[201];
int dr_lf[201];
int dr_rg[201];
inline int mxa(int a, int b)
{
return (a > b ? a : b);
}
inline int mna(int a, int b)
{
return (a < b ? a : b);
}
void readFile()
{
f = fopen("bmatrix.in", "r");
fscanf(f, "%d%d\n", &n, &m);
int i, j;
char c;
for(i = 1; i <= n; i ++)
{
for(j = 1; j <= m; j ++)
fscanf(f, "%c", &c), a[i][j] = (c - '0');
fscanf(f, "%c", &c);
}
}
int skyline(int m, int v[])
{
int i, j, mx = 0;
for(i = 1; i <= m; i ++)
h[i] = v[i];
dr = 0;
stk[dr] = 0;
for(j = 1; j <= m; j ++)
{
while(dr != 0 && h[j] <= h[stk[dr]])
dr --;
stk[++ dr] = j;
left[j] = stk[dr - 1];
}
dr = 0;
stk[dr] = m + 1;
for(j = m; j >= 1; j --)
{
while(dr != 0 && h[j] <= h[stk[dr]])
dr --;
stk[++ dr] = j;
right[j] = stk[dr - 1];
}
for(j = 1; j <= m; j ++)
mx = mxa(mx, h[j] * (right[j] - 1 - left[j]));
return mx;
}
void elements0()
{
int i, j;
/// Precalculam matricile l1_1, l2_1, l1_2, l2_2
/// l1_1[i][j] = nr. de elemente '0' deasupra lui (i, j)
/// l2_1[j][i] = nr. de elemente '0' in stanga lui (i, j)
/// l1_2[i][j] = nr. de elemente '0' sub (i, j)
/// l2_2[j][i] = nr. de elemente '0' in dreapta lui (i, j)
for (i = 1; i <= n; i ++)
{
for (j = 1; j <= m; j ++)
{
l1_1[i][j] = (a[i][j] == 0 ) * (l1_1[i - 1][j] + 1);
l2_1[j][i] = (a[i][j] == 0 ) * (l2_1[j - 1][i] + 1);
}
}
for (i = n; i >= 1; i --)
{
for (j = m; j >= 1; j --)
{
l1_2[i][j] = (a[i][j] == 0) * (l1_2[i + 1][j] + 1);
l2_2[j][i] = (a[i][j] == 0) * (l2_2[j + 1][i] + 1);
}
}
}
void maxArie()
{
int i, j;
/// Precalculam matricile dr
/// dr_...[i] = aria maxima a unui dreptunghi [deasupra/sub/in stanga/in dreapta] [liniei/coloanei] i (inclusiv i)
for (i = 1; i <= n; i ++)
dr_up[i] = mxa(dr_up[i - 1], skyline(m, l1_1[i]));
for (i = 1; i <= m; i ++)
dr_lf[i] = mxa(dr_lf[i - 1], skyline(n, l2_1[i]));
for (i = n; i >= 1; i --)
dr_dn[i] = mxa(dr_dn[i + 1], skyline(m, l1_2[i]));
for (i = m; i >= 1; i --)
dr_rg[i] = mxa(dr_rg[i + 1], skyline(n, l2_2[i]));
}
void solve()
{
int i, j;
elements0();
maxArie();
for ( i = 1; i <= n; i ++ )
rez = mxa( rez, dr_up[i] + dr_dn[i + 1] );
for ( i = 1; i <= m; i ++ )
rez = mxa( rez, dr_lf[i] + dr_rg[i + 1] );
}
void printFile()
{
g = fopen("bmatrix.out", "w");
fprintf(g, "%d\n", rez);
fclose(g);
}
int main()
{
readFile();
solve();
printFile();
return 0;
}