UVa 983

after looking into other's solution, I found again the array need compression

origin:

    1 2 2 1
    1 0 2 2
    0 2 3 3
    1 2 1 3

after 1st compression: (column)

    1 3 5 6
    1 1 3 5
    0 2 5 8
    1 3 4 7

after 2nd compression: (row)

    1 3 5   6
    2 4 8   11
    2 6 13 19
    3 9 17 26

now mat[i][j] represents the sum of elements from mat[0][0] to mat[i][j]

hence to calculate the sum from mat[i0][j0] to mat[i1][j1]

we need to exclude some rows (mat[0][0]-mat[i0-1][j1]), some columns(mat[0][0]-mat[i1][j0-1])

of course, if we exclude rows and columns at the same time, mat[i0][j0] is excluded twice.

so add back it...

/* UVas */
/*****************************************************************************/
#define ull unsigned long long
int n, m, ce=0;
int mat[1000][1000];
ull calc(int i0, int j0, int i1, int j1) {
    int r=mat[i1][j1];
    if(j0>=1) r-=mat[i1][j0-1];
    if(i0>=1) r-=mat[i0-1][j1];
    if(i0>=1&&j0>=1) r+=mat[i0-1][j0-1];
    return r;
}
int main(void) {
    while (scanf("%d %d", &n, &m)>0) {
        if (ce) printf("\n");
        for (int i=0; i<n; i++)
            for (int j=0; j<n; j++)
                scanf("%d", &mat[i][j]);
        for (int i=0; i<n; i++)
            for (int j=1; j<n; j++)
                mat[i][j]+=mat[i][j-1];
        for (int i=0; i<n; i++)
            for (int j=1; j<n; j++)
                mat[j][i]+=mat[j-1][i];
        ull r=0, c=0;
        for (int i=0; i<n-m+1; i++)
            for (int j=0; j<n-m+1; j++) {
                c=calc(i, j, i+m-1, j+m-1);
                r+=c;
                printf("%llu\n", c);
            }
        printf("%llu\n", r);
        ce++;
    }
}
/*****************************************************************************/