HDU 1559 - 最大子矩阵

 1 /*
 2 ID:esxgx1
 3 LANG:C++
 4 PROG:hdu1559
 5 */
 6 #include <cstdio>
 7 #include <cstring>
 8 #include <iostream>
 9 #include <algorithm>
10 using namespace std;
11 
12 int m[1007][1007];
13 long long sumx[1007], sumy[1007];
14 long long sum[1007][1007];
15 
16 int main(void)
17 {
18     #ifndef ONLINE_JUDGE
19     freopen("in.txt", "r", stdin);
20     #endif
21 
22     int T;
23     int M, N, X, Y;
24     scanf("%d", &T);
25     while(T) {
26         scanf("%d%d%d%d", &M, &N, &X, &Y);
27         memset(sumx, 0, sizeof(sumy));
28         memset(sum, 0, sizeof(sum));
29         for(int i=0; i<M; ++i) {
30             sumy[i] = 0;
31             for(int j=0; j<N; ++j) {
32                 scanf("%d", &m[i][j]);
33                 sumy[i] += m[i][j], sumx[j] += m[i][j];
34                 sum[i+1][j+1] += sum[i][j] + sumy[i] + sumx[j] - m[i][j];
35 
36             }
37         }
38         long long maxx = -0x3f3f3f3f3f3f3f3fLL;
39         for(int i=X-1; i<M; ++i) {
40             for(int j=Y-1; j<N; ++j) {
41                 #define i    i+1
42                 #define j    j+1
43                 if (maxx < sum[i][j] - sum[i-X][j] - sum[i][j-Y] + sum[i-X][j-Y])
44                     maxx = sum[i][j] - sum[i-X][j] - sum[i][j-Y] + sum[i-X][j-Y];
45                 #undef i
46                 #undef j
47             }
48         }
49         printf("%I64d\n", maxx);
50         --T;
51     }
52     return 0;
53 }