UVa983 Localized Summing for Blurring

問題
http://uva.onlinejudge.org/external/9/983.html

概要
N×N の正方行列が与えられる。全ての M×M の部分行列において、各値の和を出力せよ。またそれらの合計も出力せよ。合計は 64bit signed integer に収まるものとする。

制約
N <= 1000

解法
（普通の）二次元累積和。終点が決まっているので、2重ループで解ける。（4重ループではない）

反省
本番ははじめから二次元累積和の案が出ていたが、4重ループだと思い込んで考えを詰められなかった。

#include <bits/stdc++.h>
 
using namespace std;
 
#define rep(i,n) for(int i=0; i<(n); i++)
const int MAX = 1000;
 
int sum[MAX+10][MAX+10];
 
int main() {
   
  int N, M;
  bool blank = false;
  while(scanf("%d%d", &N, &M) != EOF) {
    if(blank) puts("");
    blank = true;
     
    rep(i, N) rep(j, N) {
      scanf("%d", &sum[i][j]);
      if(i) sum[i][j] += sum[i-1][j];
      if(j) sum[i][j] += sum[i][j-1];
      if(i&&j) sum[i][j] -= sum[i-1][j-1];
    }
     
    int64_t total = 0;
    rep(i, N-M+1) {
      rep(j, N-M+1) {
        int curr = sum[i+M-1][j+M-1];
        if(i) curr -= sum[i-1][j+M-1];
        if(j) curr -= sum[i+M-1][j-1];
        if(i&&j) curr += sum[i-1][j-1];
        printf("%d\n", curr);
        total += curr;
      }
    }
    printf("%lld\n", total);
  }
   
  return 0;
}