Pagini recente » Cod sursa (job #702237) | Cod sursa (job #1133321) | Cod sursa (job #3201796) | Cod sursa (job #2847391) | Cod sursa (job #187668)
Cod sursa(job #187668)
#include <cstdio>
const int maxn = 201;
const int inf = - (1 << 30);
FILE *in = fopen("bmatrix.in","r"), *out = fopen("bmatrix.out","w");
int n, m;
int a[maxn][maxn];
int b[maxn][maxn];
void read()
{
char buf[maxn + 1];
fscanf(in, "%d %d", &n, &m);
for ( int i = 1; i <= n; ++i )
{
fscanf(in, "%s", buf);
for ( int j = 0; buf[j]; ++j )
if ( buf[j] == '0' )
a[i][j + 1] = 1;
else
a[i][j + 1] = - (1 << 20);
}
}
inline int max(int x, int y)
{
return x > y ? x : y;
}
int getmax(int startx, int starty, int endx, int endy)
{
int maxsum = inf;
for ( int i = 1; i <= n; ++i )
for ( int j = 1; j <= m; ++j )
b[i][j] = 0;
for ( int i = startx; i <= endx; ++i )
for ( int j = starty; j <= endy; ++j )
b[i][j] = b[i][j-1] + a[i][j];
for ( int i = starty; i <= endy; ++i )
for ( int j = i; j <= endy; ++j )
{
int sum = inf;
for ( int k = startx; k <= endx; ++k )
{
int t = b[k][j] - b[k][i-1];
sum = max(sum+t, t);
maxsum = max(maxsum, sum);
}
}
return maxsum;
}
int main()
{
read();
int maxarea = -1;
for ( int i = 1; i < n; ++i )
{
int t1 = getmax(1, 1, i, m);
int t2 = getmax(i+1, 1, n, m);
maxarea = max(maxarea, t1 + t2);
}
for ( int i = 1; i < m; ++i )
{
int t1 = getmax(1, 1, n, i);
int t2 = getmax(1, i+1, n, m);
maxarea = max(maxarea, t1 + t2);
}
fprintf(out, "%d\n", maxarea);
return 0;
}