Pagini recente » Cod sursa (job #2147142) | Cod sursa (job #1997300) | Cod sursa (job #1246333) | Cod sursa (job #483513) | Cod sursa (job #1859172)
#include <stdio.h>
#include <stdlib.h>
#define MAXN 300
int v[1 + MAXN][1 + MAXN];
int w[1 + MAXN][1 + MAXN];
int h[1 + MAXN][1 + MAXN];
int maxs[1 + MAXN][1 + MAXN];
int maxlu[1 + MAXN];
int maxld[1 + MAXN];
int maxcl[1 + MAXN];
int maxcr[1 + MAXN];
struct limit{
int left, right;
}l[1 + MAXN][1 + MAXN];
struct st{
int val;
int pos;
}stack[1 + MAXN];
int last;
inline void create(int v[][1 + MAXN], int n, int m, int maxv[]){
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
h[i][j] = v[i][j] * (h[i - 1][j] + v[i][j]);
for(int i = 1; i <= n; i++){
maxv[i] = 0;
last = 0;
stack[last].pos = 0;
for(int j = 1; j <= m; j++){
while(last && stack[last].val >= h[i][j])
last--;
l[i][j].left = stack[last].pos;
stack[++last].val = h[i][j];
stack[last].pos = j;
}
last = 0;
stack[last].pos = m + 1;
for(int j = m; j >= 1; j--){
while(last && stack[last].val >= h[i][j])
last--;
l[i][j].right = stack[last].pos;
stack[++last].val = h[i][j];
stack[last].pos = j;
maxs[i][j] = v[i][j] * h[i][j] * (l[i][j].right - l[i][j].left - 1);
if(maxs[i][j] > maxv[i])
maxv[i] = maxs[i][j];
}
if(maxv[i - 1] > maxv[i])
maxv[i] = maxv[i - 1];
}
}
int main(){
FILE*fi,*fo;
fi=fopen("bmatrix.in","r");
fo=fopen("bmatrix.out","w");
int n, m;
fscanf(fi,"%d%d", &n, &m);
fgetc(fi);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
v[i][j] = fgetc(fi);
v[i][j] -= '0';
v[i][j] = 1 - v[i][j];
}
fgetc(fi);
}
create(v, n, m, maxlu);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
w[i][j] = v[n - i + 1][j];
create(w, n, m, maxld);
int ans = 0;
for(int i = 1; i <= n; i++){
if(maxlu[i] + maxld[n - i] > ans)
ans = maxlu[i] + maxld[n - i];
}
for(int i = 1; i <= m; i++)
for(int j = 1; j <= n; j++)
w[i][j] = v[j][i];
create(w, m, n, maxcl);
for(int i = 1; i <= m; i++)
for(int j = 1; j <= n; j++)
w[i][j] = v[j][m - i + 1];
create(w, m, n, maxcr);
for(int i = 1; i <= m; i++){
if(maxcl[i] + maxcr[m - i] > ans)
ans = maxcl[i] + maxcr[m - i];
}
fprintf(fo,"%d", ans);
fclose(fi);
fclose(fo);
return 0;
}