2968 「COCI 2010.03.06」CHUCK

**译自 [COCI 2010.03.06](http://hsin.hr/coci/archive/2009_2010/) T6.** ***[CHUCK](http://hsin.hr/coci/archive/2009_2010/contest5_tasks.pdf)*** 给你一个 $R$ 行 $C$ 列的矩阵 $A$，$|A_{i,j}|\leq 10^4$。请使用若干次下述操作（次数尽量少），使得矩阵中 $\sum_i \sum_j A_{i,j}$ 尽可能大。 |操作|示例| |-|-| |$\texttt{rotR i k}$
将第 $i$ 行的元素循环右移 $k$ 位|$\begin{pmatrix}1&2&3\\4&5&6\\7&8&9\\10&11&12\end{pmatrix}\xrightarrow{\large\texttt{ rotR 3 1 }}\begin{pmatrix}1&2&3\\4&5&6\\9&7&8\\10&11&12\end{pmatrix}$ | |$\texttt{rotS j k}$
将第 $j$ 列的元素循环下移 $k$ 位|$\begin{pmatrix}1&2&3\\4&5&6\\7&8&9\\10&11&12\end{pmatrix}\xrightarrow{\large\texttt{ rotS 3 2 }}\begin{pmatrix}1&2&9\\4&5&12\\7&8&3\\10&11&6\end{pmatrix}$ | |$\texttt{negR i}$
将第 $i$ 行的元素全部乘以 $-1$
**该操作当且仅当该行任何一个元素均未乘以 $-1$ 时有效**|$\begin{pmatrix}1&2&3\\4&5&6\\7&8&9\\10&11&12\end{pmatrix}\xrightarrow{\large\texttt{ negR 2 }}\begin{pmatrix}1&2&3\\-4&-5&-6\\7&8&9\\10&11&12\end{pmatrix}$ | |$\texttt{negS j}$
将第 $j$ 列的元素全部乘以 $-1$
**该操作当且仅当该列任何一个元素均未乘以 $-1$ 时有效**|$\begin{pmatrix}1&2&3\\0&0&0\\7&8&9\\10&11&12\end{pmatrix}\xrightarrow{\large\texttt{ negS 1 }}\begin{pmatrix}-1&2&3\\0&0&0\\-7&8&9\\-10&11&12\end{pmatrix}$ |

$1≤R,C≤100,$ $|A_{i,j}|≤10^4$。

评分标准

若你求了个错误的最大和，或是执行的操作中有无效的，该测试点不得分，否则： * 若 $T≤ 5\cdot RC$，你将得到该点的所有分数； * 若 $5\cdot RC10^5$，你将得不到该点的任何分数。