730. The Total Within Reach of Each Cell

For every cell of an R by C grid, print the total of all cells within k rows AND k columns of it. Near an edge the square is CLIPPED to the grid rather than wrapping or being skipped.

grid 1 2 3 k = 1 12 21 16 4 5 6 -> 27 45 33 7 8 9 24 39 28

The top-left answer is 1+2+4+5 = 12, because only four cells lie inside the grid.

## One table, then one query per cell

Build the same corner-total table as problem 729. Then each cell is a single rectangle query, so the whole grid costs O(R C) rather than O(R C k^2).

With R = C = 1000 and k = 500, summing the CLIPPED area of every cell's window gives 750500 * 750500 = 563250250000 additions for the direct version, about 5.6 * 10^11. Note that the clipping must be included in that count: the unclipped (2k+1)^2 per cell would overstate it and a bare k^2 R C would understate it by more than half.

## The clipping is the problem

The square around (r, c) runs from r-k to r+k and c-k to c+k, and near an edge those fall outside the grid. Clamp each of the four edges INDEPENDENTLY:

r1 = max(1, r - k) r2 = min(R, r + k) c1 = max(1, c - k) c2 = min(C, c + k)

Then use the ordinary query. What must NOT happen is sliding the square back inside the grid to keep its size: the statement says clipped, so a corner cell covers a smaller region, not a shifted one.

That distinction is the whole difference between this and a fixed-size window, and it is the thing to read carefully off the statement.

## Why every cell is still one query

After clamping, r1 <= r2 and c1 <= c2 always hold, because r itself is inside the grid and so lies between them. The rectangle is never empty and no cell needs a special case.

## When k swallows the grid

A k at or above both R and C makes every answer the total of the whole grid. The clamps handle it with no extra code, and it is the cheapest check that they are written correctly.

## Relationship with problem 729

729 answers arbitrary rectangles given in the input. This answers one fixed-shape rectangle per cell, computed from the cell. Same table, same four terms; only where the corners come from changes.

## Overflow

10^6 cells of 10^4 total 10^10.

## Cost

Time O(R C). Space O(R C).

Constraints - `1 ≤ R, C ≤ 1000` - `0 ≤ k ≤ 1000` - `-10^4 ≤ each value ≤ 10^4`