P6234 [eJOI 2019] T-shaped Covering

If you have played Tetris, you should have seen the following shape:  We call it a ***T-shaped tetromino***. Its **center** is marked by $\times$. Manca drew a rectangular grid with $m$ rows and $n$ columns. Rows are numbered from $0$ to $m-1$, and columns are numbered from $0$ to $n-1$. She marked some cells in the grid as ***special cells***. Then, she wants her friend Nika to help her place T-shaped tetrominoes according to the following rules: - The number of special cells is the same as the number of T-shaped tetrominoes, and the center of each T-shaped tetromino must be on a special cell in the grid. - T-shaped tetrominoes must not overlap. - All parts of all tetrominoes must lie inside the grid. Note that a T-shaped tetromino has four orientations: $\bot \top \vdash \dashv$. If no arrangement exists, output `No`. Otherwise, find an arrangement that maximizes the sum of the numbers in the covered cells, and output this maximum value.

The first line contains two integers $m,n$, representing the number of rows and the number of columns. The next $m$ lines each contain $n$ integers. The $j$-th number in the $i$-th line (indexed from $0$) represents the value $a_{i,j}$ in the cell at row $i$ and column $j$. The next line contains one integer $k$, representing the number of special cells. The next $k$ lines each contain two integers $r_i,c_i$, representing the position of the $i$-th special cell.

If an arrangement exists, output the maximum possible sum of the numbers in the covered cells. Otherwise, output `No`.

#### Explanation of Sample Input/Output 1 One optimal arrangement is as follows: - The tetromino centered at $(1,1)$ is oriented as $\dashv$. - The tetromino centered at $(2,2)$ is oriented as $\vdash$. - The tetromino centered at $(3,4)$ is oriented as $\bot$. -------------------------- #### Constraints and Notes **This problem uses bundled testdata and has 7 subtasks.** - Subtask 1 (5 points): $k\le 10^3$, and it is guaranteed that for all $i\ne j$, $\max(|r_i-r_j|,|c_i-c_j|)>2$. - Subtask 2 (10 points): $k\le 10^3$, and it is guaranteed that for all $i\ne j$, if $\max(|r_i-r_j|,|c_i-c_j|)\le 2$, then $(r_i,c_i)$ and $(r_j,c_j)$ share an edge. - Subtask 3 (10 points): $k\le 10^3$, and it is guaranteed that for all $i\ne j$, $\max(|r_i-r_j|,|c_i-c_j|)\ne 2$. - Subtask 4 (10 points): All special cells are in the same row. - Subtask 5 (15 points): $k\le 10$. - Subtask 6 (20 points): $k\le 10^3$. - Subtask 7 (30 points): No additional constraints. For all testdata: $1\le k\le nm\le 10^6$, $a_{ij}\in[0,10^3]$, $r_i\in[0,m)$, $c_i\in[0,n)$. --------------------------- #### Notes The original problem is from: [eJOI2019](https://www.ejoi2019.si) Problem C. [T - Covering](https://www.ejoi2019.si/static/media/uploads/tasks/covering-isc(1).pdf). The translation is from: [LibreOJ](https://loj.ac/problem/3197)。 Translated by ChatGPT 5