P8409 [COCI 2009/2010 #5] CHUCK

You are given a matrix $a$ with $R$ rows and $C$ columns, where $|a_{i,j}| \le 10^4$. Please use the following operations (as few times as possible) to make $\sum_i \sum_j a_{i,j}$ as large as possible. | Operation | Example | | | :---: | :---: | :---: | | `rotR i k` cyclically shifts the elements of row $i$ to the right by $k$ positions | $\left(\begin{array}{ccc}1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \\ 10 & 11 & 12\end{array}\right)$ | $\xrightarrow{\operatorname{rotR} 3\ 1}\left(\begin{array}{ccc}1 & 2 & 3 \\ 4 & 5 & 6 \\ 9 & 7 & 8 \\ 10 & 11 & 12\end{array}\right)$ | | `rotS j k` cyclically shifts the elements of column $j$ downward by $k$ positions | $\left(\begin{array}{ccc}1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \\ 10 & 11 & 12\end{array}\right)$ | $\xrightarrow{\text { rotS } 3\ 2}\left(\begin{array}{ccc}1 & 2 & 9 \\ 4 & 5 & 12 \\ 7 & 8 & 3 \\ 10 & 11 & 6\end{array}\right)$ | | `negR i` multiplies all elements in row $i$ by $-1$. This operation is valid if and only if none of the elements in that row has been multiplied by $-1$ before | $\left(\begin{array}{ccc}1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \\ 10 & 11 & 12\end{array}\right)$ | $\xrightarrow{\text { negR } 2}\left(\begin{array}{ccc}1 & 2 & 3 \\ -4 & -5 & -6 \\ 7 & 8 & 9 \\ 10 & 11 & 12\end{array}\right)$ | | `negS j` multiplies all elements in column $j$ by $-1$. This operation is valid if and only if none of the elements in that column has been multiplied by $-1$ before | $\left(\begin{array}{ccc}1 & 2 & 3 \\ 0 & 0 & 0 \\ 7 & 8 & 9 \\ 10 & 11 & 12\end{array}\right)$ | $\xrightarrow{\text { negS } 1}\left(\begin{array}{ccc}-1 & 2 & 3 \\ 0 & 0 & 0 \\ -7 & 8 & 9 \\ -10 & 11 & 12\end{array}\right)$ |

The first line: $r, c$. The next $r$ lines: the matrix $a$.

The first line contains two integers: the first integer is the maximum value of $\sum_i \sum_j a_{i,j}$, and the second integer is the number of operations $t$. The next $t$ lines each contain one operation.

Constraints: $1 \le R,C \le 100$, $|A_{i,j}|s \le 10^4$. #### Scoring If you output an incorrect maximum sum, or any operation you perform is invalid, you will get $0$ points for that test case. Otherwise: If $t \le 5 \cdot RC$, you will get full points for that test case. If $5 \cdot RC < T < 10^5$, you will get $50\%$ of the points for that test case. If $t > 10^5$, you will get $0$ points for that test case. The score of this problem follows the original COCI settings, with a full score of $130$. Translated by ChatGPT 5