Rhombus

Observation 1: the scary rhombus is just a Manhattan ball

For a center $(x,y)$, the rhombus of size $k$ consists exactly of the cells

$$|i-x|+|j-y|\le k-1.$$

So the function we need to maximize is

$$f(x,y)=\sum_{|i-x|+|j-y|\le k-1} a_{i,j}.$$

Brute-forcing that sum for every center is hopeless: there are up to $10^6$ centers and each rhombus can contain $\Theta(k^2)$ cells. That’s dead on arrival.

Observation 2: rotate the board

This is one of those problems where geometry stops being obnoxious the moment you rotate it.

Define transformed coordinates

$$U=i+j-1,\qquad V=i-j+m.$$

The shifts are only there to keep indices positive.

For a fixed center $(x,y)$, define

$$U_0=x+y-1,\qquad V_0=x-y+m.$$

Now let

$$p=i-x,\qquad q=j-y.$$

Then

$$U-U_0=p+q,\qquad V-V_0=p-q.$$

And here comes the key identity:

$$\max\bigl(|p+q|,|p-q|\bigr)=|p|+|q|.$$

Why? If $pq\ge 0$, then $|p+q|=|p|+|q|$; otherwise $|p-q|=|p|+|q|$. Cute and lethal.

Therefore,

$$|i-x|+|j-y|\le k-1 \iff \max\bigl(|U-U_0|,|V-V_0|\bigr)\le k-1$$

which is the same as

$$|U-U_0|\le k-1 \quad\text{and}\quad |V-V_0|\le k-1.$$

So the rhombus becomes an axis-aligned square in the rotated coordinate system. Nice. The geometry has officially given up.

Observation 3: build a rotated grid

Create a grid $b$ indexed by $(U,V)$ and put

$$b[U][V]=a_{i,j}$$

for the unique cell $(i,j)$ that maps there.

Some $(U,V)$ positions do not correspond to any original cell because of parity. That’s totally fine: leave them as $0$. Then summing over a rectangle in the rotated grid still gives exactly the sum over the rhombus in the original grid.

The range of both $U$ and $V$ is at most $1$ to $n+m-1$, so the rotated grid is only about $2000\times 2000$.

Observation 4: 2D prefix sums do the boring work

Build the 2D prefix sum of $b$:

$$pref[u][v]=\sum_{i\le u,\,j\le v} b[i][j].$$

Then any rectangle sum is

$$S(x_1,y_1,x_2,y_2)=pref[x_2][y_2]-pref[x_1-1][y_2]-pref[x_2][y_1-1]+pref[x_1-1][y_1-1].$$

For center $(x,y)$, the needed rhombus sum is just the square

$$[U_0-k+1,\,U_0+k-1]\times[V_0-k+1,\,V_0+k-1].$$

So each candidate center is evaluated in $O(1)$.

Then brute-force all valid centers:

$$k\le x\le n-k+1,\qquad k\le y\le m-k+1.$$

Keep the one with maximum sum.

Correctness sketch

Each original cell $(i,j)$ contributes to exactly one rotated cell $(U,V)$. For a fixed center $(x,y)$), the condition of belonging to the rhombus is

$$|i-x|+|j-y|\le k-1.$$

By the identity above, this is equivalent to

$$|U-U_0|\le k-1 \quad\text{and}\quad |V-V_0|\le k-1,$$

which is exactly membership in the queried rectangle. Therefore the rectangle sum in rotated coordinates equals the rhombus sum in the original grid. Since we evaluate every valid center and pick the maximum, the output is correct.

Complexity

Let $S=n+m$.

• Filling the rotated grid: $O(nm)$
• Building 2D prefix sums: $O(S^2)$
• Checking all centers: $O(nm)$

So the total complexity is

$$O((n+m)^2+nm),$$

with memory

$$O((n+m)^2).$$

With $n,m\le 1000$, this is easily fast enough.

Also, yes, the statement says the numbers are non-negative. Cute. We don’t even need that.