UVa 10074

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 #define MAXN 110
 6 
 7 int mat[MAXN][MAXN], sum[MAXN][MAXN];
 8 
 9 int main()
10 {
11 #ifdef LOCAL
12     freopen("in", "r", stdin);
13 #endif
14     int m, n, x;
15     while (scanf("%d%d", &m, &n) && (m || n))
16     {
17         for (int i = 1; i <= m; i++)
18             for (int j = 1; j <= n; j++)
19                 {
20                     scanf("%d", &x);
21                     if (x == 0)  x = 1;
22                     else if (x == 1)  x = -20000;
23                     mat[i][j] = x;
24                 }
25         memset(sum, 0, sizeof(sum));
26         for (int i = 1; i <= m; i++)
27             for (int j = 1; j <= n; j++)
28                 sum[i][j] = mat[i][j] + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1]; 
29         int ans = 0;
30         for (int i = 1; i <= m; i++)
31             for (int j = 1; j <= n; j++)
32                 for (int p = i; p <= m; p++)
33                     for (int q = j; q <= n; q++)
34                     {
35                         int t = sum[p][q] - sum[p][j-1] - sum[i-1][q] + sum[i-1][j-1];
36                         ans = max(ans, t);
37                     }
38         printf("%d
", ans);
39     }
40     return 0;
41 }