1532. The Heaviest Window of a Given Shape
An R by C grid is given together with a window height h and a window width
w. Among all h by w windows that fit entirely inside the grid, find the
one whose values add up to the most. Print that total and the 1-based row and
column of the window's TOP-LEFT cell. On a tie, print the smallest row, and
among those the smallest column.
1 2 3 4 h = 2, w = 3
5 6 7 8 -> 54 2 2 the window 6 7 8 / 10 11 12
9 10 11 12
1 9 3 h = 1, w = 1 -> 9 1 2
4 5 6
1 1 1 1 h = 2, w = 2 -> 4 1 1 every window ties, so the
1 1 1 1 earliest position wins
1 1 1 1
## What most people try first
Adding up each window directly. There are (R - h + 1)(C - w + 1) positions
and each costs h * w additions, which at R = C = 1000 and
h = w = 500 is 251001 * 250000, about 6 * 10^10 additions.
The second reflex is to slide the window and adjust, adding the incoming column and removing the outgoing one. That works and is fiddly in two dimensions, with a separate rule for moving down a row. The corner-total table does the same job in one formula.
## The corner-total table
Build P with P[i][j] equal to the total of everything from (1,1) to
(i,j), sized (R+1) by (C+1) with a border of zeros:
P[i][j] = g[i][j] + P[i-1][j] + P[i][j-1] - P[i-1][j-1]
and then any rectangle is four lookups:
total(r1,c1,r2,c2) = P[r2][c2] - P[r1-1][c2] - P[r2][c1-1] + P[r1-1][c1-1]
That is the structure of problem 729, which answers arbitrary rectangles handed to it in the input. Here the rectangles are not given: they are every window of one FIXED shape, and the answer is a maximum over them rather than a list.
## Why the last term is added back
Removing the strip above and the strip to the left removes the block that is
both above AND left twice, so it has to be returned once. The term is zero
whenever the rectangle touches the top or left edge, so the mistake is
invisible on every window at position (1,1) and visible everywhere else. The
h = 1, w = 1 example, whose answer sits at column 2, is the smallest case that
catches it.
## The loop bounds
The window's top-left row runs from 1 to R - h + 1 and its column from 1 to
C - w + 1. Both ends matter: stopping at R - h misses the last row of
positions, and going to R reads outside the grid. The test whose best window
is in the last available row exists for the first of those.
## Do not swap h and w
h is a number of ROWS and w a number of COLUMNS. On a square window they
are interchangeable and on any other they are not, which is why the samples use
2 by 3 and 1 by 1 rather than 2 by 2.
## Overflow
A window can hold 10^6 cells of magnitude 10^9, so a total reaches
10^15, far past the 2147483647 a signed 32 bit integer holds. Both the
table and the running best must be 64 bit. Note the full table entry for the
whole grid is bounded by the same 10^15, which is comfortable inside a signed
64 bit integer.
## Cost
O(R C) to build the table and O(R C) to scan the positions, with
O(R C) memory.
Constraints - `1 ≤ R ≤ 1000` - `1 ≤ C ≤ 1000` - `1 ≤ h ≤ R` - `1 ≤ w ≤ C` - `-10^9 ≤ each value ≤ 10^9` - `R` and `C` are independent, and so are `h` and `w`
Input
The first line contains four integers R, C, h and w.
Each of the next R lines contains C integers.
Output
Print one line holding three integers separated by single spaces: the largest window total, then the 1-based row and the 1-based column of that window's top-left cell, breaking ties by smallest row and then smallest column.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.