Aoki uses his white stamp to paint white the squares which Takahashi painted black. The squares that are once painted black but then “overpainted” white form a rectangular region.
Even if \(h_1 < h_2\), Aoki cannot “overpaint” more than \(h_1\) from black to white, so if \(h_1 < h_2\), we can safely replace \(h_2\) with the same value to \(h_1\) without changing the answer to the problem. Similarly, if \(w_1 < w_2\), then we can safely replace \(w_2\) with the same value to \(w_1\) without changing the answer.
Therefore, we hereinafter assume that \(h_1 \geq h_2\) and \(w_1 \geq w_2\).

Under this assumption, Aoki may choose a rectangle to press his white stamp so that it does not stick out from the rectangle to which Takahashi painted black.
Obviously, it is not optimal for Aoki to choose the rectangle to press his white stamp sticking out from the rectangle painted black, so there is no problem in assuming that “Aoki always presses the stamp so that it does not stick out from the rectangular region to which Takahashi pressed his stamp.”
Formally, we assume that “if Takahashi pressed his stamp to the rectangle whose top-left square is \((i_T, j_T)\), then Aoki always presses his stamp to the rectangle whose top-left square is \((i_A, j_A)\) so that it holds that \(i_T \leq i_A \leq i_T+h_1-h_2\) and \(j _T\leq j_A \leq j_T + w_1-w_2\).

First, we will describe some precalculations required to find the answer for this problem.

Precalculation

(a) \(\mathrm{sum}[\ast][\ast]\): the two-dimensional cumulative sums of \(A_{i, j}\)

First, we find the two-dimensional cumulative sum \(\mathrm{sum}[\ast][\ast]\) of \(A_{i, j}\). That is, we compute

\(\mathrm{sum}[i][j] := \displaystyle\sum_{i' = 0}^i \displaystyle\sum_{j'=0}^j A_{i', j'}\)

for every pair of integers \((i,j)\) such that \(0 \leq i \leq H\) and \(0 \leq j \leq W\).
\(\mathrm{sum}[\ast][\ast]\) can be computed for each pair of integers \((i, j)\) such that \(1 \leq i \leq H\) and \(1 \leq j \leq W\) by the following relation for example:

\(\mathrm{sum}[i][j] = \mathrm{sum}[i-1][j] + \mathrm{sum}[i][j-1] - \mathrm{sum}[i-1][j-1] + A_{i, j}\)

in a total of \(\mathrm{O}(HW)\) time (Here, the expression above assume that if \(i = 0\) or \(j = 0\) then \(A_{i, j} := 0\)).

(b) \(\mathrm{Taka}[\ast][\ast]\) and \(\mathrm{Aoki}[\ast][\ast]\): The sum of \(A_{i, j}\) in the rectangular region that Takahashi and Aoki may choose to press their stamp to

Let \(\mathrm{Taka}[i_T][j_T] \) be “the sum of integers written in the rectangular region, when Takahashi presses his stamp to the rectangle whose top-left square is \((i_T, j_T)\).”
In other words, for every pair of integers \((i_T, j_T)\) such that \(1 \leq i_T \leq H-h_1+1\) and \(1 \leq j_T \leq W-w_1+1\), we define \(\mathrm{Taka}[i_T][j_T]\) by

\(\mathrm{Taka}[i_T][j_T] := \displaystyle \sum_{i = i_T}^{i_T+h_1-1} \displaystyle\sum_{j = j_T}^{j_T+h_1-1} A_{i, j} \).

Similarly, for Aoki, we define \(\mathrm{Aoki}[i_A][j_A]\) as “the sum of integers written in the rectangular region, when Aoki presses his stamp to the rectangle whose top-left square is \((i_A, j_A)\).”
In other words, for every pair of integers \((i_A, j_A)\) such that \(1 \leq i_A \leq H-h_2+1\) and \(1 \leq j_A \leq W-w_2+1\), we define \(\mathrm{Aoki}[i_A][j_A]\) by

\(\mathrm{Aoki}[i_A][j_A] := \displaystyle \sum_{i = i_A}^{i_A+h_2-1} \displaystyle\sum_{j = j_A}^{j_A+h_2-1} A_{i, j} \).

\(\mathrm{Taka}[\ast][\ast]\) and \(\mathrm{Aoki}[\ast][\ast]\) can be computed by making use of the two-dimensional cumulative sums \(\mathrm{sum}[\ast][\ast]\) in a total of \(\mathrm{O}(HW)\) time.

How to find the answer for the original problem

We will describe how to compute the answer for the original problem using the precalculated \(\mathrm{Taka}[\ast][\ast]\) and \(\mathrm{Aoki}[\ast][\ast]\).

When the top-left square \((i_T, j_T)\) to which Takahashi presses his stamp is fixed, what is the optimal score as the result of Aoki’s optimal strategy?
First, after Takahashi presses his stamp, the sum of integers written on the squares painted black becomes \(\mathrm{Taka}[i_T][j_T]\).
Then, after Aoki presses his tamp, the sum of integers written on the squares painted black becomes \(\mathrm{Taka}[i_T][j_T] - \mathrm{Aoki}[i_A][j_A]\). Here, since Aoki presses his stamp to minimize this value (and not to stick out Takahashi’s black rectangle), so “the optimal score \(\mathrm{score}[i_T][j_T]\) as the result of Aoki’s optimal strategy after Takahashi presses his stamp to the rectangle whose top-left square is \((i_T, j_T)\)” can be expressed as

\(\mathrm{score}[i_T][j_T] = \mathrm{Taka}[i_T][j_T] - \displaystyle\max_{\substack{i_T \leq i_A \leq i_T+h_1-h_2\\ j _T\leq j_A \leq j_T+w_1-w_2}} \mathrm{Aoki}[i_A][j_A]\).

In the actual game, Takahashi tries to maximize this value when choosing Square \((i_T, j_T)\), so the answer for the original problem is “the maximum value of \(\mathrm{score}[i_T][j_T]\) over all possible Squares \((i_T, j_T)\) that Takahashi can choose.”
Namely, if we could compute \(\mathrm{score}[i_T][j_T]\) for all Squares \((i_T, j_T)\) such that \(1 \leq i_T \leq H-h_1+1\) and \(1 \leq j_T \leq W-w_1+1\), we can obtain the answer to the problem as the maximum of these values.

Among the values required to compute \(\mathrm{score}[i_T][j_T]\), we have already obtained \(\mathrm{Taka}[\ast][\ast]\), so what we want is

\(M[i_T][j_T] := \displaystyle\max_{\substack{i_T \leq i_A \leq i_T+h_1-h_2\\ j _T\leq j_A \leq j_T+w_1-w_2}} \mathrm{Aoki}[i_A][j_A]\)

for every Square \((i_T, j_T)\) such that \(1 \leq i_T \leq H-h_1+1\) and \(1 \leq j_T \leq W-w_1+1\). So we will describe how to find these values fast enough.

・How to find \(M[\ast][\ast]\) fast enough?

Intuitively, \(M[i][j]\) is the minimum value of the elements \(\mathrm{Aoki}[\ast][\ast]\) in the rectangular region whose top-left square is \((i, j)\) and bottom-right square is \((i+h_1-h_2, j+w_1-w_2)\).
In order to find this value, we will compute for each row of \(\mathrm{Aoki}[\ast][\ast]\) the maximum value horizontally to construct a two-dimensional array \(M'[\ast][\ast]\), and then find for each column of this two-dimensional array \(M'[\ast][\ast]\) the maximum value vertically.

Specifically, for \(i = 1, 2, \ldots, H\), we first compute \(M'[i][\ast]\) by:

\(M'[i][j] := \displaystyle\max_{ j \leq j' \leq j + w_1-w_2} \mathrm{Aoki}[i][j'], \,\,\text{for}\,\,j = 1,2,\ldots, W-w_1+1\)

Then, we use this value to find for each \(j = 1, 2, \ldots, W - w_1+1\) the values \(M[\ast][j]\) by:

\(M[i][j] = \displaystyle\max_{i \leq i' \leq i+h_1-h_2} \Big(\displaystyle\max_{ j \leq j' \leq j+w_1-w_2} \mathrm{Aoki}[i'][j']\Big) = \displaystyle\max_{i \leq i' \leq i+h_1-h_2} M'[i'][j], \,\,\text{for}\,\,i = 1, 2, \ldots, H-h_1+1\)

Here, in order to compute \(M'[i][\ast]\) from \(\mathrm{Aoki}[i][\ast]\) fast enough for each \(i = 1, 2, \ldots, H\), one may use:

• “Sliding Window Minimum” technique using double-ended queues;
• Sliding Window Aggregation (SWAG);
• Segment Tree;
• Sparse Table.

One can use the same way to find \(M[\ast][j]\) from \(M'[\ast][j]\) for each \(j = 1, 2, \ldots, W-w_1+1\) fast enough too.

Therefore, this problem can be solved in a total of \(\mathrm{O}(HW)\) or \(\mathrm{O}(HW(\log H + \log W))\) time.

About “Sliding Window Minimum”

Given an array \(A[0], ..., A[N-1]\) of length \(N\) and a parameter \(K\), how to replace the values of \(A[i]\) with current \(\min \{ A[i], ..., A[\min(i+K, N-1)] \}\)?

If \(K = 1\), it is easy.

for(i=0;i+1<N;i++) A[i] = min(A[i], A[i+1]);

If \(K = 7\), since all non-negative integers less than or equal to \(7\) can be represented as the sum of subset of \(\{ 1, 2, 4 \}\), we can do as follows:

for(i=0;i+1<N;i++) A[i] = min(A[i], A[i+1]);
for(i=0;i+2<N;i++) A[i] = min(A[i], A[i+2]);
for(i=0;i+4<N;i++) A[i] = min(A[i], A[i+4]);

Generally, we can do in the similar way:

while(K > 0){
	int d = (K + 1) / 2;
	for(i=0;i+d<N;i++) A[i] = min(A[i], A[i+d]);
	K -= d;
}