luogu#P8409. [COCI 2009/2010 #5] CHUCK

[COCI 2009/2010 #5] CHUCK

题目描述

给你一个 RRCC 列的矩阵 aaai,j104|a_{i,j}| \le 10^4。请使用若干次下述操作(次数尽量少),使得矩阵中 ijai,j\sum_i \sum_j a_{i,j} 尽可能大。

操作 示例
rotR i k 将第 ii 行的元素循环右移 kk $\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 将第 jj 列的元素循环下移 kk $\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 将第 ii 行的元素全部乘以 -1 。 该操作当且仅当该行任何一个元素均未乘以 -1 时有效 $\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 将第 jj 列的元素全部乘以 -1。 该操作当且仅当该列任何一个元素均未乘以 -1 时有效 $\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)$

输入格式

第一行:r,cr,c。 接下来 rr 行:矩阵 aa

输出格式

第一行包含两个整数,第一个整数为 ijai,j\sum_i \sum_j a_{i,j} 的最大值,第二个数为操作数量 tt。 接下来 tt 行,每行包含一组操作。

3 4
1 -2 5 200
-8 0 -4 -10
11 4 0 100
345 2
rotS 2 1
negR 2
3 3
8 -2 7
1 0 -3
-4 -8 3
34 4
rotR 1 1
rotS 3 1
negR 2
negR 3

提示

1R,C1001 \le R,C \le 100Ai,js104|A_{i,j}|s \le 10^4

评分标准

若你求了个错误的最大和,或是执行的操作中有无效的,该测试点不得分,否则:

t5RCt \le 5 \cdot RC,你将得到该点的所有分数;

5RC<T<1055\cdot RC<T<10^5,你将得到该点 50%50\% 的分数;

t>105t > 10^5,你将得不到该点的任何分数。

本题分值按 COCI 原题设置,满分 130130