시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 153 67 50 43.860%

문제

태균이는 분필과 바닥만 있으면 언제든지 할 수 있는 재미있는 게임을 하나 만들었습니다.

바닥에 N×M 사각 격자를 그린 뒤 각 칸에 정수들을 쓰고 다음의 규칙을 따라 게임을 진행합니다.

  • 1번 행에 있는 원하는 칸을 하나 정하여 해당 칸에서 시작합니다.
  • N번 행에 있는 임의의 칸에 도착하면 게임이 끝납니다.
  • 칸에서 칸으로 이동하려면 행의 번호가 증가하는 칸으로만 이동이 가능하며 칸 사이의 거리가 D이하여야 합니다. 즉, RC열에서 PQ열로 이동하려면 P > R 이며 | P - R | + | Q - C | ≤ D 를 만족해야 합니다.
  • 게임 시작 시 점수의 초기값은 0이며, 칸에서 칸으로 이동할 때 각 칸의 수를 곱하여 현재 점수에 더합니다.

칸에 적힌 수들이 주어지면 게임에서 낼 수 있는 최대 점수를 구해주세요.

입력

첫 번째 줄에 행의 개수 N과 열의 개수 M (2 ≤ N×M ≤ 200,000, 2 ≤ N) 그리고 최대 점프 거리 정수 D (1 ≤ D ≤ 10) 가 주어집니다.

i+1 번째 줄에는 i (1 ≤ iN) 번째 행에 있는 쓰여있는 정수 ai,1, ai,2, ..., ai,m (-100 ≤ ai,j ≤ 100) 이 순서대로 주어집니다.

출력

첫 번째 줄에 게임에서 낼 수 있는 최대 점수를 출력합니다.

예제 입력 1

4 3 2
3 -5 4
2 0 0
1 -3 1
-2 9 1

예제 출력 1

21

1행 2열에서 시작하여 3행 2열로 이동하면 (-5) × (-3) = 15 점을 얻을 수 있습니다.

3행 2열에서 4행 1열로 이동하면 (-3) × (-2) = 6 점을 얻을 수 있습니다.

총 15 + 6 = 21 점을 획득했고 이보다 더 좋은 방법은 없으므로 문제의 정답이 됩니다.

예제 입력 2

2 2 2
100 100
-100 -100

예제 출력 2

-10000

예제 입력 3

6 6 3
1 0 0 0 0 0
0 0 1 0 0 0
0 1 0 0 0 0
0 0 0 1 0 0
0 0 0 0 0 0
0 0 0 0 1 0

예제 출력 3

4

출처

University > 경북대학교 > 2019 Goricon C번

  • 문제를 만든 사람: exqt