Just as Problem D, consider the following DP (Dynamic Programming):

\(DP[t][x][y] = \) The maximum sum of size of Snukes that Takahashi captures until he reaches at the coordinates \((x, y)\) at time \(t\)

Then the transition will be:
\(DP[t][x][y]=\max\{DP[t'][x'][y']\mid y'\leq y,\ |x-x'|+y-y'\leq t-t'\}+\text{the size of Snuke he can capture if he is at the coordinates }(x, y)\text{ at time }t.\)

The second condition statement in the max can be transformed as:
\(|x-x'|+y-y'\leq t-t' \Longleftrightarrow x-x'+y-y'\leq t-t' \text{ and } -(x-x')+y-y'\leq t-t',\)

which can be further be deformed as:
\(x-x'+y-y'\leq t-t' \Longleftrightarrow t'-x'-y'\leq t-x-y,\)
\(-(x-x')+y-y'\leq t-t' \Longleftrightarrow t'+x'-y'\leq t+x-y.\)

Here, by \(a=t-x-y, \ b=t+x-y\) we can convert variables as \((t,x,y)\mapsto(a,b,y)\) so that
\(DP[a][b][y]=\max\{DP[a'][b'][y']\mid a'\leq a,\ b'\leq b,\ y'\leq y\}+\text{the size of Snuke he can capture if he is at the coordinates }(x, y)\text{ at time }t,\)
thus converting the domain of the max in a simple form.

It is sufficient to record the DP table only for \((a,b,y)\) on which Snuke appears. Therefore, by scanning the plane with respect to \(y\), the problem can be solved if two-dimensional max queries can be processed fast enough. Since each query can be processed in an \(O((\log N)^2)\) time by two-dimensional segment tree (segtree on segtree) where only necessary nodes are created, or divide-and-conquer, so the problem can be solved in a total of \(O(N(\log N)^2)\) time.

Sample code (C++): 2D Binary Indexed Tree (Fenwick Tree on Fenwick Tree)

About two-dimensional segment tree

Consider the following problem.

Process \(Q\) queries of the following two kinds:

• set query: place a point of weight \(w\) at \((x,y)\).
• get query: find the maximum weight of points in the region \([L,R]\times[D,U]\).

By scanning the queries beforehand and doing coordinate compression, we can assume that the coordinates are in the range of \([0,Q]\).
This problem can be solved with a two-dimensional segment tree. Each node of a two-dimensional segment tree holds a segment tree. That is, while each node of a one-dimensional segment tree holds “the maximum value in the segment \([L,R]\),” that of a two-dimensional one stores “a segment tree that is capable of obtaining the maximum value in the region \([L,R]×[*,*]\).”
Naively, we need to maintain \(Q\) segment trees of size \(Q\), for a total spacial complexity of \(O(Q^2)\), but we may only create nodes that contains non-unit values so that the spacial cost is reduced to \(O(Q(\log Q)^2)\).
Since a set query updates \(O(\log Q)\) segment trees, such a query can be processed in an \(O((\log Q)^2)\) time. Similarly, a get query requires to find maximum values on \(O(\log Q)\) segment trees, for a total of \(O((\log Q)^2)\) time.

About divide and conquer

Consider the following problem.

Process \(Q\) queries of the following two kinds:

• set query: place a point of weight \(w\) at \((x,y)\).
• get query: find the maximum weight of points in the region \([0,R]\times[0,U]\).

In this problem, if all set queries are before all get queries, the problem can be solved in a total of \(O(Q\log Q)\) time by scanning queries beforehand, compressing coordinates, and plane scanning. So let us divide the query into the first and second half, considering the following divide-and-conquer:

• 1. Process the queries in the first half (recursively)
• 2. Process the get queries in the second half against the set queries in the first half
• 3. Process the queries in the second half (recursively), assuming that those in the first do not exist

The answers for the get queries in the first half are obtained in step 1, and those for the second are obtained by combining the result in steps 2 and 3.

Denoting by \(T(Q)\) the time required to process \(Q\) queries, we have \(T(Q)=2T(Q/2)+O(Q\log Q)\), so \(T(Q)=O(Q(\log Q)^2)\).