연습문제

레이저 게임

난이도
Lv. 5
제출
67 명
참가자
27 명
정답률
50.00 %
지원 언어
C
C++
Java
Python
Rust
언어별 시간/메모리
언어별 시간/메모리 표
언어 시간 메모리
Python 5초 1024MB
Java 3초 1024MB
C++ 1초 1024MB
C 1초 1024MB
Rust 1초 1024MB

코드런 나라에서 레이저 게임이 열립니다. 이 게임은 2차원 격자 형태의 보드판에서 세 명의 플레이어가 한 팀이 되어 진행합니다. 보드판의 각 칸에는 정수가 적혀 있으며, 세 명의 플레이어는 협력하여 최고 점수를 얻어야 합니다. 플레이어들은 순서로 아래와 같은 규칙에 따라 행동합니다.

플레이어 : 가로 또는 세로 방향 중 하나를 선택해 원하는 범위에 레이저를 발사합니다. 가 발사한 레이저가 지나간 모든 칸의 값은 로 변합니다.

플레이어 : 가 선택한 방향과 다른 방향에서(가 가로를 선택했다면 세로, 세로를 선택했다면 가로) 원하는 범위에 레이저를 발사합니다. 가 발사한 레이저가 지나간 칸의 값은 배가 됩니다.

플레이어 : 의 행동으로 변경된 보드판을 기준으로 특정 직사각형을 선택합니다. 이 직사각형 안의 모든 숫자의 합이 세 명의 플레이어가 협력해서 얻은 최종 점수가 됩니다.

단, 는 각각 한 개 이상의 행 또는 열에 레이저를 발사해야 하며 는 한 개 이상의 격자 칸으로 이루어진 직사각형을 선택해야 합니다.


아래는 격자에서 가 가로 방향을 선택해 [2 ~ 3] 행에 레이저를 발사하고 가 세로 방향으로 [3 ~ 4]열에 레이저를 발사한 후 열에서 열까지 격자에 해당하는 직사각형을 선택한 예시입니다. 이 경우 최종 점수는 입니다.

보드판이 주어졌을 때 세 명의 플레이어가 협력하여 얻을 수 있는 최대 점수를 출력하세요.

제약조건

[문제 제약 조건]

[조건 1]

[조건 2] 보드판에 적혀 있는 정수


[서브 태스크별 제약 조건]

Subtask1 (31점):

Subtask2 (20점):

Subtask3 (49점): 문제 조건 외에 별도의 제한이 없습니다.

입력형식

첫째 줄에 보드판의 길이를 나타내는 정수 N이 주어집니다.

다음 N개의 줄에 걸쳐 보드판에 적혀 있는 정수값 N개가 공백을 사이에 두고 주어집니다.

출력형식

세 명의 플레이어가 협업을 해서 얻을 수 있는 최대 점수를 출력합니다.

입력예제1

3 -1 -1 -1 4 -1 1 1 -1 4

출력예제1

24

플레이어 가 세로를 선택해서 [2 ~ 2]열에 레이저를 발사하고, 플레이어 는 가로를 선택해서 [2 ~ 3]행에 레이저를 발사하고, 플레이어 는 2 ~ 3행 전체에 해당하는 직사각형을 선택하면 최댓값인 를 얻을 수 있습니다.

입력예제2

3 -2 -3 -2 -1 -2 -1 0 2 2

출력예제2

20

플레이어 가 가로를 선택해서 [1 ~ 2]행에 레이저를 발사하고, 플레이어 는 세로를 선택해서 [1 ~ 3]열에 레이저를 발사하고, 플레이어 는 전체 직사각형을 선택하면 최댓값인 을 얻을 수 있습니다.

입력예제3

2 3 3 3 3

출력예제3

16

플레이어 가 레이저를 발사하면 점수에 손해를 보지만, 반드시 레이저를 발사해야 합니다. 따라서 가 가로를 선택해서 [1 ~ 1]행에 레이저를 발사하고, 플레이어 는 세로를 선택해서 [1 ~ 2]열에 레이저를 발사하고, 플레이어 는 전체 직사각형을 선택하면 최댓값인 을 얻을 수 있습니다.