SPOJ 274 Johnny and the Watermelon Plantation（TLE）

O(n^3)的时间复杂度，改了半天交了二三十遍，TLE到死，实在没办法了……
跪求指点！！！
  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <cstring>
  4 #include <algorithm>
  5 
  6 using namespace std;
  7 
  8 const int MAXN = 1010;
  9 const int INF = 1 << 30;
 10 
 11 int mat[MAXN][MAXN];
 12 int SubSum[MAXN][MAXN];
 13 int tempS[MAXN];
 14 int N, K;
 15 int maxI, maxJ;
 16 int hang[MAXN], cntH;
 17 int lie[MAXN], cntL;
 18 
 19 //预处理左上角[1,1]右下角[i,j]的所有矩阵和
 20 void init()
 21 {
 22     memset( SubSum, 0, sizeof(SubSum) );
 23     for ( int i = 1; i <= maxI; ++i )
 24     {
 25         int tmps = 0;
 26         for ( int j = 1; j <= maxJ; ++j )
 27         {
 28             tmps += mat[i][j];
 29             SubSum[i][j] = SubSum[i - 1][j] + tmps;
 30         }
 31     }
 32     return;
 33 }
 34 
 35 void solved()
 36 {
 37     int ans = INF;
 38     for ( int i = 0; i < cntH; ++i ) //枚举矩形上边界
 39     for ( int j = i; j < cntH; ++j )  //枚举矩形下边界
 40     {
 41         int stL = hang[i], edL = hang[j];
 42         tempS[0] = 0;
 43         int st = 1;
 44         //扫描法，参考刘汝佳训练指南p.48 LA 2678
 45         for ( int m = 1; m <= cntL; ++m )
 46         {
 47             int k = lie[m - 1];
 48             tempS[m] = SubSum[edL][k] - SubSum[edL][k-1] - SubSum[stL-1][k] + SubSum[stL-1][k-1];
 49             tempS[m] += tempS[m - 1];
 50             if ( tempS[st - 1] > tempS[m] - K ) continue;
 51             while ( tempS[st] <= tempS[m] - K ) ++st;
 52             ans = min( ans, ( lie[m - 1] - lie[st - 1] ) * ( edL - stL ) );
 53         }
 54     }
 55     printf( "%d
", ans );
 56     return;
 57 }
 58 
 59 int main()
 60 {
 61     //freopen( "in.txt", "r", stdin );
 62     int T;
 63     scanf( "%d", &T );
 64     while ( T-- )
 65     {
 66         memset( mat, 0, sizeof(mat) );
 67         scanf( "%d%d", &N, &K );
 68         maxI = 0;
 69         maxJ = 0;
 70         cntL = 0, cntH = 0;
 71         bool flag = false;
 72         for ( int i = 0; i < N; ++i )
 73         {
 74             int x, y, f;
 75             scanf("%d%d%d", &x, &y, &f );
 76             hang[cntH++] = x;  //行列离散化
 77             lie[cntL++] = y;
 78             maxI = max( maxI, x );
 79             maxJ = max( maxJ, y );
 80             mat[x][y] = f;
 81             if ( f >= K )  //特殊情况，只覆盖一个点
 82             {
 83                 flag = true;
 84             }
 85         }
 86 
 87         if ( N == 1 || flag )
 88         {
 89             puts("0");
 90             continue;
 91         }
 92 
 93         sort( hang, hang + cntH );
 94         sort( lie, lie + cntL );
 95         cntH = unique( hang, hang + cntH ) - hang;
 96         cntL = unique( lie, lie + cntL ) - lie;
 97 
 98         init();
 99         solved();
100     }
101     return 0;
102 }