sk14cj   1년 전

Omar는 사탕을 매우 좋아하지만, 대부분의 사탕은 몸에 좋지 않습니다. 그래서 부모님은 각 사탕마다 점수를 매기는 방법을 생각해냈습니다. 점수는 정수이며, 점수가 높을수록 더 건강한 사탕임을 의미합니다.

어느 날 Omar가 부모님과 함께 사탕을 사러 갔는데, 가게에서는 사탕이 N×M 크기의 2차원 그리드 형태로 진열되어 있었습니다. 그리드는 위에서부터 1행부터 N행까지 번호가 매겨져 있고, 왼쪽에서부터 1열부터 M열까지 번호가 매겨져 있습니다. 그리드의 각 칸에는 사탕이 하나씩 놓여 있습니다.

가게에는 특이한 규칙이 있습니다. 첫 번째 행을 제외한 모든 사탕은 바로 위 칸에 있는 사탕보다 더 건강하고, 첫 번째 열을 제외한 모든 사탕은 바로 왼쪽 칸에 있는 사탕보다 더 건강하다는 점입니다. 여기서 “더 건강”하다는 것은 점수가 더 높음을 의미합니다.

또 다른 규칙으로, 사탕을 구매할 때는 그리드에서 어떤 부분 직사각형(sub-rectangle)을 골라 그 안에 있는 사탕을 전부 사야 한다는 것입니다.

Omar의 부모님은 이 그리드에서 가능한 부분 직사각형 중에서 사탕 점수의 합이 최대가 되는 곳을 선택하고 싶어 합니다.

예를 들어, 아래 그림의 예시 그리드를 살펴봅시다:

-4  -2  -1
-3  -2   3
 1   4   5

이 그리드에서 선택할 수 있는 부분 직사각형의 예로 다음과 같은 것들이 있습니다.

  • [-2, -1, 2, 3]

  • [-4, -2, -1]

  • [2, 3, 4, 5]

마지막 경우의 부분 직사각형은 점수의 합이 14로, 이 그리드에서 얻을 수 있는 최대 점수입니다. 반면 [1, 2, 3, 4, 5]나 [-2, -1, 2]는 이 그리드에서 연속된 직사각형 모양을 이루지 않으므로 올바른 부분 직사각형 선택이 아닙니다.

이제 주어진 그리드에서 비어 있지 않은 부분 직사각형 중 사탕 점수의 합이 가장 큰 값을 찾아야 합니다.

입력

프로그램은 하나 이상의 테스트 케이스를 입력으로 받습니다.
입력의 첫 번째 줄에는 테스트 케이스의 개수를 나타내는 정수 \( T \) (1 ≤ T ≤ 100)이 주어집니다.

그 후 테스트 케이스마다, 첫 줄에 정수 \( N \)과 \( M \) (1 ≤ N, M ≤ 1,000)이 공백으로 구분되어 주어집니다. 이는 사탕 그리드의 크기를 나타냅니다.
이어서 \( N \)개의 줄이 주어지며, 각 줄에는 공백으로 구분된 \( M \)개의 정수가 있어 각 행의 사탕 점수를 나타냅니다.

주어진 그리드는 위에서 언급한 조건(첫 행을 제외한 모든 칸은 위 칸보다 점수가 높고, 첫 열을 제외한 모든 칸은 왼 칸보다 점수가 높음)을 만족합니다. 또한 그리드에 포함된 각 정수의 범위는 -2,000보다 작지 않고 2,000보다 크지 않습니다.

출력

각 테스트 케이스마다, 얻을 수 있는 최대 부분 직사각형 점수 합을 나타내는 정수를 한 줄에 하나씩 출력합니다.

댓글을 작성하려면 로그인해야 합니다.