P4012 Deep-Sea Robot Problem

The submarine of a deep-sea resource exploration team will arrive at the ocean floor for scientific investigation. There are multiple deep-sea robots inside the submarine. After reaching the seafloor, the robots will leave the submarine and move toward their predetermined targets. While moving, the robots must collect biological specimens along the way. Each specimen along the route is collected by the first robot that encounters it. The value of specimens on each prescribed path (i.e., each grid edge) is known, and each specimen can be collected at most once. In this problem, each robot may move only to the north or to the east from its current position. Multiple robots may occupy the same position at the same time. The movable positions of the robots are represented by a $P \times Q$ grid. The southwest corner has coordinates $(0,0)$, and the northeast corner has coordinates $(Q,P)$.  Given the starting positions and destination positions of each robot, as well as the specimen values on each grid edge, compute the optimal movement plan that maximizes the total value of collected specimens after all robots reach their destinations.

The first line contains the number of starting locations $a$ and the number of destination locations $b$. The second line contains the values of $P$ and $Q$. The next $P+1$ lines each contain $Q$ positive integers. In the $i$-th line (0-indexed), the $j$-th (0-indexed) integer gives the specimen value on the edge from $(i,j)$ to $(i,j+1)$. The next $Q+1$ lines each contain $P$ positive integers. In the $i$-th line (0-indexed), the $j$-th (0-indexed) integer gives the specimen value on the edge from $(j,i)$ to $(j+1,i)$. The next $a$ lines each contain three positive integers $k, x, y$, indicating that there are $k$ robots starting from position $(x,y)$. The next $b$ lines each contain three positive integers $r, x, y$, indicating that there are $r$ robots that may choose position $(x,y)$ as a destination.

Output the maximum total value of collected specimens.

$1 \leq P, Q \leq 15$. $1 \leq a \leq 4$. $1 \leq b \leq 6$. Translated by ChatGPT 5