폴짝 게임

면접 대비

시간 제한1초메모리 제한256 MB

요약
N x M 격자의 1행에서 시작해 맨해튼 거리 D 이내의 더 큰 행으로 점프하며 두 칸의 값을 곱해 점수에 더할 때, N행에 도착했을 때 얻을 수 있는 최대 점수를 구한다.
난이도

보통10점 중 7점

유형
동적 계획법, 구현, 수학
정답자
아직 제출이 없습니다

문제

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

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

  • 1번 행에 있는 원하는 칸을 하나 정하여 해당 칸에서 시작합니다.
  • N번 행에 있는 임의의 칸에 도착하면 게임이 끝납니다.
  • 칸에서 칸으로 이동하려면 행의 번호가 증가하는 칸으로만 이동할 수 있으며 칸 사이의 거리가 D이하여야 합니다. 즉, R행 C열에서 P행 Q열로 이동하려면 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 ≤ i ≤ N) 번째 행에 있는 정수 ai,1, ai,2, ..., ai,m (-100 ≤ ai,j ≤ 100) 이 순서대로 주어집니다.

출력

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

예제3

  1. 예제 1

    입력
    4 3 2
3 -5 4
2 0 0
1 -3 1
-2 9 1
    예상 출력
    21

  2. 예제 2

    입력
    2 2 2
100 100
-100 -100
    예상 출력
    -10000

  3. 예제 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
    예상 출력
    4