Pagini recente » Cod sursa (job #1190366) | Cod sursa (job #2600508) | Cod sursa (job #1644376) | Cod sursa (job #969321) | Cod sursa (job #2134474)
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <string.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 + 1; j++){
while(last && stack[last].val > h[i][j]){
l[i][stack[last].pos].right = j;
last--;
}
stack[++last].val = h[i][j];
stack[last].pos = j;
}
last = 0;
stack[last].pos = m + 1;
for(int j = m; j >= 0; j--){
while(last && stack[last].val > h[i][j]){
l[i][stack[last].pos].left = j;
last--;
}
stack[++last].val = h[i][j];
stack[last].pos = j;
}
for(int j = 1; j <= m; 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);
memset(w, 0, sizeof(w));
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; 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];
}
memset(w, 0, sizeof(w));
for(int i = 1; i <= m; i++)
for(int j = 1; j <= n; j++)
w[i][n - j + 1] = v[j][i];
create(w, m, n, maxcl);
memset(w, 0, sizeof(w));
for(int i = 1; i <= m; i++)
for(int j = 1; j <= n; j++)
w[m - i + 1][j] = v[j][i];
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;
}