시간 제한1초메모리 제한128 MB
행렬에서 행과 열을 회전시키고 각 행과 열을 한 번씩 음수로 뒤집을 수 있을 때 얻을 수 있는 전체 원소 합의 최댓값을 구합니다.
R개의 행과 C개의 열로 이루어진 행렬이 주어진다. 모든 원소의 절댓값은 10^4 이하이다. 다음 연산들을 원하는 만큼 수행할 수 있다.
| 연산 | 표기 | 예시 |
|---|---|---|
| 행렬의 i번째 행을 오른쪽으로 k칸 회전한다. | rotR i k | rotR 3 1 \(\begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \\ 10 & 11 & 12 \end{pmatrix}\rightarrow \begin{pmatrix} 1&2&3 \\ 4&5&6 \\ 9&7&8\\10&11&12 \end{pmatrix} \) |
| 행렬의 j번째 열을 아래로 k칸 회전한다. | rotS j k | rotS 3 2 \(\begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \\ 10 & 11 & 12 \end{pmatrix}\rightarrow \begin{pmatrix} 1&2&9 \\ 4&5&12 \\ 7&8&3\\10&11&6 \end{pmatrix} \) |
| i번째 행의 모든 원소에 -1을 곱한다. 단, 그 행의 어떤 원소도 이전에 곱해진 적이 없을 때에만 가능하다. | negR i | negR 2 \(\begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \\ 10 & 11 & 12 \end{pmatrix}\rightarrow \begin{pmatrix} 1 & 2 & 3 \\ -4 & -5 & -6 \\ 7 & 8 & 9 \\ 10 & 11 & 12 \end{pmatrix}\) |
| j번째 열의 모든 원소에 -1을 곱한다. 단, 그 열의 어떤 원소도 이전에 곱해진 적이 없을 때에만 가능하다. | negS j | negS 1 \(\begin{pmatrix} 1 & 2 & 3 \\ 0&0&0 \\ 7 & 8 & 9 \\ 10 & 11 & 12 \end{pmatrix}\rightarrow \begin{pmatrix} -1 & 2 & 3 \\ 0 & 0 & 0\\ -7 & 8 & 9 \\ -10 & 11 & 12 \end{pmatrix}\) |
이 연산들을 사용하여 행렬의 모든 원소의 합을 최대로 만들어라.
첫째 줄에 두 정수 R과 C (1 <= R, C <= 100)가 주어지며, 각각 행과 열의 개수이다.
이어지는 R개의 줄에는 각각 C개의 정수가 주어진다. 모든 정수의 절댓값은 10^4 미만이다.
연산을 모두 수행한 뒤 얻을 수 있는 행렬의 모든 원소의 합의 최댓값을 정수 하나로 출력한다.
예제 1
3 4 1 -2 5 200 -8 0 -4 -10 11 4 0 100
345
예제 2
3 3 8 -2 7 1 0 -3 -4 -8 3
34